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

Groups > comp.programming > #5866 > unrolled thread

Splay trees

Back to article view | Back to comp.programming

Contents

  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

#5866 — Splay trees

Anyone here using splay trees?

  https://en.wikipedia.org/wiki/Splay_tree
  https://www.youtube.com/watch?v=G5QIXywcJlY

They are a form of self-balancing binary search tree which is easier to 
program than AVL or Red-Black trees but are only balanced on average. 
The video link below explains one form of them very clearly.

A weird feature of the explanation in the video is to move up to the 
root any node which is accessed even if that node is only found. The 
idea, AIUI, is to use that to help rebalance the tree and to increase 
performance for both spatial and temporal locality.

Naturally, the best rebalancing action would depend on the upcoming 
access pattern but, without trying it, I would have guessed that moving 
a node a step up the tree on each access would be better overall rather 
than moving the node all the way up to the root. Anyone care either to 
agree or to dispute that?

James

[toc] | [next] | [standalone]

#5868

On Wed, 16 Sep 2015 19:32:12 +0100
"James Harris" <james.harris.1@gmail.com> wrote:

> Anyone here using splay trees?
> 
>   https://en.wikipedia.org/wiki/Splay_tree
>   https://www.youtube.com/watch?v=G5QIXywcJlY
> 
> They are a form of self-balancing binary search tree which is easier
> to program than AVL or Red-Black trees but are only balanced on
> average. The video link below explains one form of them very clearly.
> 
> A weird feature of the explanation in the video is to move up to the 
> root any node which is accessed even if that node is only found. The 
> idea, AIUI, is to use that to help rebalance the tree and to increase 
> performance for both spatial and temporal locality.
> 
> Naturally, the best rebalancing action would depend on the upcoming 
> access pattern but, without trying it, I would have guessed that
> moving a node a step up the tree on each access would be better
> overall rather than moving the node all the way up to the root.
> Anyone care either to agree or to dispute that?
> 
> James
> 

When tree is in the form of linked list (in order insert) moving up to
the root has better access performance for sure...

[toc] | [prev] | [next] | [standalone]

#5870

"Melzzzzz" <mel@zzzzz.com> wrote in message 
news:20150916205922.39163e69@maxa-pc...
> On Wed, 16 Sep 2015 19:32:12 +0100
> "James Harris" <james.harris.1@gmail.com> wrote:
>
>> Anyone here using splay trees?
>>
>>   https://en.wikipedia.org/wiki/Splay_tree
>>   https://www.youtube.com/watch?v=G5QIXywcJlY

...

> When tree is in the form of linked list (in order insert) moving up to
> the root has better access performance for sure...

AIUI that would result in a well-balanced tree but it is a special case. 
I suppose a full tree traversal would also benefit from the standard 
splaying of each referenced node right up to the root. In fact, any 
access which is near a previous access would probably benefit from that 
action.

However, for random access having to splay each node up to the root may 
be unnecessarily slow because the tree is being widely restructured each 
time.

I would have thought that splaying a node up just a level or two would 
work fairly well for sequential/local access (though not as well as 
splaying it to the root) but it would work better for random access. It 
would keep the tree balanced but not restructure it each time. Or so it 
seems....

James

[toc] | [prev] | [next] | [standalone]

#5874

On Thu, 17 Sep 2015 17:10:52 +0100
"James Harris" <james.harris.1@gmail.com> wrote:

> "Melzzzzz" <mel@zzzzz.com> wrote in message 
> news:20150916205922.39163e69@maxa-pc...
> > On Wed, 16 Sep 2015 19:32:12 +0100
> > "James Harris" <james.harris.1@gmail.com> wrote:
> >
> >> Anyone here using splay trees?
> >>
> >>   https://en.wikipedia.org/wiki/Splay_tree
> >>   https://www.youtube.com/watch?v=G5QIXywcJlY
> 
> ...
> 
> > When tree is in the form of linked list (in order insert) moving up
> > to the root has better access performance for sure...
> 
> AIUI that would result in a well-balanced tree but it is a special
> case. I suppose a full tree traversal would also benefit from the
> standard splaying of each referenced node right up to the root. In
> fact, any access which is near a previous access would probably
> benefit from that action.
> 
> However, for random access having to splay each node up to the root
> may be unnecessarily slow because the tree is being widely
> restructured each time.

Splay tree is not good choice for random access, anyway.
 

[toc] | [prev] | [next] | [standalone]

#5875

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.

Consider, for example, a tree that uses a postcode (or zipcode, if you 
prefer) as its key. Let's say, for the sake of argument, that we don't 
envisage creating or deleting any postcodes before going-home time, so 
we're only concerned about retrieval.

There are around 1.7 million post codes in the UK. So we can readily see 
that a perfectly balanced binary search tree will have a depth of 
ceil(log2(1700000)), i.e. 21. But if most of our customers are local, we 
are likely to need only a few hundred postcodes that we access 
frequently (but randomly!), with the rest of the postcodes being used 
hardly at all - just an occasional long-distance customer.

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.

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.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5876

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.)

[toc] | [prev] | [next] | [standalone]

#5877

On 18/09/15 16:32, Kaz Kylheku wrote:
> 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".

Yes, I know, but I felt it worth clarifying because, to at least some 
people, the word "random" does convey the idea of, well, rand() 
(although yes I know, that isn't random either!).

> 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.

Agreed.

<snip>

> 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,

You see? I learned something, which is nice.

<snip>

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5879

On Fri, 18 Sep 2015 14:03:07 +0100
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.

Of course. I think that I understood James pretty well. ;)

[toc] | [prev] | [next] | [standalone]

#5872

The only time I used splay trees was when I worked as a Software Engineer at Kodak in Emeryville a few years ago. Eventually then company went bankrupt and I found greener grass working as a Software Engineer for salesforce.com in San Francisco. 

[toc] | [prev] | [next] | [standalone]

#5873

"Chad" <cdalten@gmail.com> wrote in message 
news:b17ab0f1-b157-46ac-aec0-243b4dfcfad9@googlegroups.com...
> The only time I used splay trees was when I worked as a Software 
> Engineer at Kodak in Emeryville a few years ago. Eventually then 
> company went bankrupt

Do you mean to imply any connection between them using splay trees and 
going bankrupt? Here we all thought it was the advent of digital 
cameras.

:-)

James

[toc] | [prev] | [next] | [standalone]

#5878

James, no. I think it was a series of idiotic decisions made by the executives that caused the firm to go bankrupt.

[toc] | [prev] | [next] | [standalone]

#5883

On 2015-09-16, James Harris <james.harris.1@gmail.com> wrote:
>
> Naturally, the best rebalancing action would depend on the upcoming 
> access pattern but, without trying it, I would have guessed that moving 
> a node a step up the tree on each access would be better overall rather 
> than moving the node all the way up to the root. Anyone care either to 
> agree or to dispute that?
>
Moving a tree node up one level instead of to the root could have 
both performance pluses and minuses.  The results with some simple 
modifications to code that I have for a splay tree is that for random 
values, searching was 13% faster for the single level change, but the 
resulting tree had a 20% greater average node depth.

On the plus side, it is likely that fewer instructions were executed 
to restructure the tree.  Moving a tree node to the root can involve 
restructing the tree at many places on the path between the previous 
root and where the node was in the tree.  Moving a tree node up only 
one level involves restructing the tree at only one place.

On the minus side, the resulting tree was more unbalanced.

Splay trees were designed to improve the performance of clustered 
searches, not the random searches that I did.  In the test I did, 
compared to an unbalanced tree, the single level change tree search 
was 68% slower and the resulting tree had a 35% greater average node 
depth.

[toc] | [prev] | [next] | [standalone]

#5885

"A. Bolmarcich" <aggedor@earl-grey.cloud9.net> wrote in message 
news:slrnn00jcd.gdp.aggedor@earl-grey.cloud9.net...
> On 2015-09-16, James Harris <james.harris.1@gmail.com> wrote:
>>
>> Naturally, the best rebalancing action would depend on the upcoming
>> access pattern but, without trying it, I would have guessed that 
>> moving
>> a node a step up the tree on each access would be better overall 
>> rather
>> than moving the node all the way up to the root. Anyone care either 
>> to
>> agree or to dispute that?
>>
> Moving a tree node up one level instead of to the root could have
> both performance pluses and minuses.  The results with some simple
> modifications to code that I have for a splay tree is that for random
> values, searching was 13% faster for the single level change, but the
> resulting tree had a 20% greater average node depth.

Thank you very much for the measured figures. When you say you moved up 
one level do you mean that you moved nodes up two levels in the 
hierarchy, i.e. what might be called a zig-zig or zig-zag pair of 
rotations? You will see I referred to a "step" up, meaning two levels of 
the hierarchy. If the node is one level below the root I would just 
leave it unchanged rather than doing a zig step.

> On the plus side, it is likely that fewer instructions were executed
> to restructure the tree.  Moving a tree node to the root can involve
> restructing the tree at many places on the path between the previous
> root and where the node was in the tree.  Moving a tree node up only
> one level involves restructing the tree at only one place.
>
> On the minus side, the resulting tree was more unbalanced.
>
> Splay trees were designed to improve the performance of clustered
> searches, not the random searches that I did.  In the test I did,
> compared to an unbalanced tree, the single level change tree search
> was 68% slower and the resulting tree had a 35% greater average node
> depth.

I was thinking of how the tree behaved over time. I don't know that a 
comparison with an unbalanced tree is a fair one.

If you still have the testing setup in place I wonder if you could 
compare the times taken for a full traversal of the tree. I would expect 
the traditional splay-to-root to be faster than splaying up a step (two 
levels) at a time as nearly all accesses would be to adjacent nodes and 
splaying to root would bring adjacent nodes up too, but it would be 
interesting to see how much difference it made to the time.

James

[toc] | [prev] | [next] | [standalone]

#5886

On 2015-09-22, James Harris <james.harris.1@gmail.com> wrote:
> Thank you very much for the measured figures. When you say you moved up 
> one level do you mean that you moved nodes up two levels in the 
> hierarchy, i.e. what might be called a zig-zig or zig-zag pair of 
> rotations? You will see I referred to a "step" up, meaning two levels of 
> the hierarchy. If the node is one level below the root I would just 
> leave it unchanged rather than doing a zig step.

I moved a found node up one level.  A tree node found by a serach is
moved to the position in the tree occupied by its parent before the 
search.  For example, given the subtree [ASCII art requiring a
monospaced font]

Before search for value 18.      After search for value 18.
           .                               .
           .                               .
           .                               .
           |                               |
      +---22---+                      +---18---+
      |        |                      |        |
  +--18--+    26                     17    +--22--+
  |      |                                 |      |
 17     19                                19     26

where the node with the value 22 is an unspecified depth below the root 
of the tree.  A found node one level below the root would become the 
root.

> If you still have the testing setup in place I wonder if you could 
> compare the times taken for a full traversal of the tree. I would expect 
> the traditional splay-to-root to be faster than splaying up a step (two 
> levels) at a time as nearly all accesses would be to adjacent nodes and 
> splaying to root would bring adjacent nodes up too, but it would be 
> interesting to see how much difference it made to the time.

By traversal, I take you to mean searching for all nodes in a sorted 
order.  (Traversal usually means visiting all the tree nodes by 
following the pointers.  Differently balanced trees with the same data 
should have about the same traversal time, ignoring the effect that 
additional levels of recursions can have with very unblanced trees.)

Compared to an unbalanced tree, searching for all nodes in a sorted 
order was about 50% faster with a splay tree and about 140% slower for 
a move found node up one level tree.

[toc] | [prev] | [next] | [standalone]

#5887

"A. Bolmarcich" <aggedor@earl-grey.cloud9.net> wrote in message 
news:slrnn05qau.h67.aggedor@earl-grey.cloud9.net...
> On 2015-09-22, James Harris <james.harris.1@gmail.com> wrote:
>> Thank you very much for the measured figures. When you say you moved 
>> up
>> one level do you mean that you moved nodes up two levels in the
>> hierarchy, i.e. what might be called a zig-zig or zig-zag pair of
>> rotations? You will see I referred to a "step" up, meaning two levels 
>> of
>> the hierarchy. If the node is one level below the root I would just
>> leave it unchanged rather than doing a zig step.
>
> I moved a found node up one level.  A tree node found by a serach is
> moved to the position in the tree occupied by its parent before the
> search.  For example, given the subtree [ASCII art requiring a
> monospaced font]
>
> Before search for value 18.      After search for value 18.
>           .                               .
>           .                               .
>           .                               .
>           |                               |
>      +---22---+                      +---18---+
>      |        |                      |        |
>  +--18--+    26                     17    +--22--+
>  |      |                                 |      |
> 17     19                                19     26

Thanks, very clear! Unfortunately, AIUI, the two-level move up is needed 
when you have a left child of a left child or a right child of a right 
child (so needing a zig-zig operation). If the zig-zig double-level move 
up is not done then I believe that the tree will become unbalanced.

> where the node with the value 22 is an unspecified depth below the 
> root
> of the tree.  A found node one level below the root would become the
> root.
>
>> If you still have the testing setup in place I wonder if you could
>> compare the times taken for a full traversal of the tree. I would 
>> expect
>> the traditional splay-to-root to be faster than splaying up a step 
>> (two
>> levels) at a time as nearly all accesses would be to adjacent nodes 
>> and
>> splaying to root would bring adjacent nodes up too, but it would be
>> interesting to see how much difference it made to the time.
>
> By traversal, I take you to mean searching for all nodes in a sorted
> order.  (Traversal usually means visiting all the tree nodes by
> following the pointers.  Differently balanced trees with the same data
> should have about the same traversal time, ignoring the effect that
> additional levels of recursions can have with very unblanced trees.)

Yes, I was thinking of visiting each node in turn, if the nodes contain 
enough info to do that.

> Compared to an unbalanced tree, searching for all nodes in a sorted
> order was about 50% faster with a splay tree and about 140% slower for
> a move found node up one level tree.

OK. As mentioned, I think the zig-zig operation would be required in 
order to keep an approximate balance to the tree.

James

[toc] | [prev] | [next] | [standalone]

#5888

On 2015-09-23, James Harris <james.harris.1@gmail.com> wrote:
>
> Thanks, very clear! Unfortunately, AIUI, the two-level move up is needed 
> when you have a left child of a left child or a right child of a right 
> child (so needing a zig-zig operation). If the zig-zig double-level move 
> up is not done then I believe that the tree will become unbalanced.

Splay trees are unbalanced.  If searches are done for all of the nodes 
in node value order, the resulting tree will have a linear form, with 
each node having at most one child.

With an AVL balanced tree, there are conditions in which balance is 
maintained by doing what is called a single rotation and there are 
conditions in which balance is maintained by doing what is called a 
double rotation.  At least those are the terms I learned many years 
ago.

[toc] | [prev] | [next] | [standalone]

#5893

On 23/09/2015 21:33, A. Bolmarcich wrote:
> On 2015-09-23, James Harris <james.harris.1@gmail.com> wrote:
>>
>> Thanks, very clear! Unfortunately, AIUI, the two-level move up is needed
>> when you have a left child of a left child or a right child of a right
>> child (so needing a zig-zig operation). If the zig-zig double-level move
>> up is not done then I believe that the tree will become unbalanced.
>
> Splay trees are unbalanced.

They are not guaranteed to be perfectly balanced but I thought the 
splaying operations were designed to achieve a degree of balance. 
However, ...

 > If searches are done for all of the nodes
> in node value order, the resulting tree will have a linear form, with
> each node having at most one child.

Yes, sad but true. I checked and agree that a full traverse of a splay 
tree will leave it linear. That's assuming one splays to the root each 
time. Another reason to splay up just one or two levels, perhaps.

> With an AVL balanced tree, there are conditions in which balance is
> maintained by doing what is called a single rotation and there are
> conditions in which balance is maintained by doing what is called a
> double rotation.  At least those are the terms I learned many years
> ago.

Agreed.

James

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web