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

Groups > comp.programming > #5888

Re: Splay trees

Newsgroups comp.programming
From "A. Bolmarcich" <aggedor@earl-grey.cloud9.net>
Subject Re: Splay trees
References <mtccfq$4b3$1@dont-email.me> <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>
Message-ID <slrnn0634e.lah.aggedor@earl-grey.cloud9.net> (permalink)
Date 2015-09-23 15:33 -0500

Show all headers | View raw

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

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.

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