[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

Splay trees

James Harris

9/16/2015 6:32:00 PM

Anyone here using splay trees?

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

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
16 Answers

Melzzzzz

9/16/2015 6:59:00 PM

0

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/...
> https://www.youtube.com/watch?v=G...
>
> 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...

James Harris

9/17/2015 4:11:00 PM

0

"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/...
>> https://www.youtube.com/watch?v=G...

....

> 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

Chad

9/18/2015 4:33:00 AM

0

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.

James Harris

9/18/2015 10:29:00 AM

0

"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

Melzzzzz

9/18/2015 11:12:00 AM

0

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/...
> >> https://www.youtube.com/watch?v=G...
>
> ...
>
> > 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.

Richard Heathfield

9/18/2015 1:03:00 PM

0

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

Kaz Kylheku

9/18/2015 3:32:00 PM

0

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

Richard Heathfield

9/18/2015 4:30:00 PM

0

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

Chad

9/18/2015 10:59:00 PM

0

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

Melzzzzz

9/18/2015 11:10:00 PM

0

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