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

Groups > comp.programming > #5868

Re: Splay trees

From Melzzzzz <mel@zzzzz.com>
Newsgroups comp.programming
Subject Re: Splay trees
Date 2015-09-16 20:59 +0200
Organization albasani.net
Message-ID <20150916205922.39163e69@maxa-pc> (permalink)
References <mtccfq$4b3$1@dont-email.me>

Show all headers | 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...

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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