Re: Splay trees

Path	csiph.com!news.mixmin.net!news.albasani.net!.POSTED!not-for-mail
From	Melzzzzz <mel@zzzzz.com>
Newsgroups	comp.programming
Subject	Re: Splay trees
Date	Wed, 16 Sep 2015 20:59:22 +0200
Organization	albasani.net
Lines	29
Message-ID	<20150916205922.39163e69@maxa-pc> (permalink)
References	<mtccfq$4b3$1@dont-email.me>
Mime-Version	1.0
Content-Type	text/plain; charset=US-ASCII
Content-Transfer-Encoding	7bit
X-Trace	news.albasani.net C6oi3s3oJ7VGx6HTVAY4xvEe/+9N3lMT2QfaeAGX8Pk7h9rJ+h7DHaMUwJnfM4EPjmq7TAhMDVwPRCzGlk4R4w==
NNTP-Posting-Date	Wed, 16 Sep 2015 18:59:22 +0000 (UTC)
Injection-Info	news.albasani.net; logging-data="S7XkAPDxgZ47kMh3r6SriQjcRC2MUqEGoQDT4YKX1AAIDIsar9BxnWkZf0sgK48EJ6/vfN96mK0O7fpPrWvthv3WM71yfMhhHR1cdVwBOFDEJq6m+OgIKWZTMP7Paif6"; mail-complaints-to="abuse@albasani.net"
X-Newsreader	Claws Mail 3.12.0 (GTK+ 2.24.28; x86_64-unknown-linux-gnu)
Cancel-Lock	sha1:2lKveXXamvzhshVvffN0ge2MORw=
Xref	csiph.com comp.programming:5868

Show key headers only | View raw

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

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