Re: Splay trees

From	James Harris <james.harris.1@gmail.com>
Newsgroups	comp.programming
Subject	Re: Splay trees
Date	2015-09-25 13:29 +0100
Organization	A noiseless patient Spider
Message-ID	<mu3ejv$oid$1@dont-email.me> (permalink)
References	(1 earlier) <slrnn00jcd.gdp.aggedor@earl-grey.cloud9.net> <mts3o0$t0j$1@dont-email.me> <slrnn05qau.h67.aggedor@earl-grey.cloud9.net> <mtuqe6$bi2$1@dont-email.me> <slrnn0634e.lah.aggedor@earl-grey.cloud9.net>

Show all headers | View raw

On 23/09/2015 21:33, A. Bolmarcich wrote:
> On 2015-09-23, James Harris <james.harris.1@gmail.com> wrote:
>>
>> Thanks, very clear! Unfortunately, AIUI, the two-level move up is needed
>> when you have a left child of a left child or a right child of a right
>> child (so needing a zig-zig operation). If the zig-zig double-level move
>> up is not done then I believe that the tree will become unbalanced.
>
> Splay trees are unbalanced.

They are not guaranteed to be perfectly balanced but I thought the 
splaying operations were designed to achieve a degree of balance. 
However, ...

 > If searches are done for all of the nodes
> in node value order, the resulting tree will have a linear form, with
> each node having at most one child.

Yes, sad but true. I checked and agree that a full traverse of a splay 
tree will leave it linear. That's assuming one splays to the root each 
time. Another reason to splay up just one or two levels, perhaps.

> With an AVL balanced tree, there are conditions in which balance is
> maintained by doing what is called a single rotation and there are
> conditions in which balance is maintained by doing what is called a
> double rotation.  At least those are the terms I learned many years
> ago.

Agreed.

James

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