Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5876

Re: Splay trees

Show all headers | View raw

On 2015-09-18, Richard Heathfield <rjh@cpax.org.uk> wrote:
> On 18/09/15 12:12, Melzzzzz wrote:
>
>> Splay tree is not good choice for random access, anyway.
>
> It depends what you mean by "random", really.
>
> Generally, when we say "random access", we don't actually mean it. We 
> mean "arbitrary access" - that is, data-driven access.

Richard, it is this: when we say "random access" it is simply a phrase
that we invented out of the need to have a contrast with "sequential access".

Sequential access is a situation whereby we must visit all of the predecessors
of the elements of a sequence before obtaining the one we want.

Random access is any retrieval situation in which ... that isn't the case.

A binary search tree requires us to visit only some small number of
elements unrelated to the one we want (which can be any mixture of predecessors
or successors). If it is properly balanced, it qualifies as "not sequential
access", and thus random access. Of course, it can be horribly unbalanced
so that it reduces precisely to sequential access.

> In a perfectly balanced binary tree, a good few of those postcodes are 
> going to be in the very bottom branches of the tree. In a splay tree, 
> they will quickly be brought close to the root, where they will (more or 
> less) stay, thus resulting in significantly quicker searches.

Also, the main point, really, is not that the splay tree brings frequently
accessed items toward the root (which undeniably does shave cycles
when there is locality of reference) but that this continuous "hemming
up of the skirt" of the splay tree prevents it from becoming unbalanced,
so that even if an infrequently-accessed element is suddenly retrieved,
it will not require an exhaustive traversal resembles, or is in fact,
a sequential access.

It's a nice structure: self-balancing, and optimized for locality of
reference.

> So a splay tree can actually be an excellent choice for random access. 
> There is no substitute, however, for Knowing Your Data, and choosing 
> data structures and algorithms that are an appropriate match for the 
> characteristics of your data.

Sure there is a substitute. Just like butter has margarine, "Knowing Your Data"
has "Not Knowing Your Data", and using data structures and algorithms that are
all round good performers, though not necessarily the best.

(I'm not so sure which substitute is analogous to butter and which to
margarine.)

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-16 19:32 +0100
  Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-16 20:59 +0200
    Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-17 17:10 +0100
      Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-18 13:12 +0200
        Re: Splay trees Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 14:03 +0100
          Re: Splay trees Kaz Kylheku <kaz@kylheku.com> - 2015-09-18 15:32 +0000
            Re: Splay trees Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 17:30 +0100
          Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-19 01:10 +0200
  Splay trees Chad <cdalten@gmail.com> - 2015-09-17 21:32 -0700
    Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-18 11:28 +0100
      Re: Splay trees Chad <cdalten@gmail.com> - 2015-09-18 15:59 -0700
  Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-21 13:33 -0500
    Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-22 18:41 +0100
      Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-23 13:03 -0500
        Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-23 19:20 +0100
          Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-23 15:33 -0500
            Re: Splay trees James Harris <james.harris.1@gmail.com> - 2015-09-25 13:29 +0100

csiph-web