Re: Splay trees

Newsgroups	comp.programming
From	"A. Bolmarcich" <aggedor@earl-grey.cloud9.net>
Subject	Re: Splay trees
References	<mtccfq$4b3$1@dont-email.me>
Message-ID	<slrnn00jcd.gdp.aggedor@earl-grey.cloud9.net> (permalink)
Date	2015-09-21 13:33 -0500

Show all headers | View raw

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.

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