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

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