Splay trees

From	"James Harris" <james.harris.1@gmail.com>
Newsgroups	comp.programming
Subject	Splay trees
Date	2015-09-16 19:32 +0100
Organization	A noiseless patient Spider
Message-ID	<mtccfq$4b3$1@dont-email.me> (permalink)

Show all headers | View raw

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

Back to comp.programming | Previous | Next — 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