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

Groups > comp.programming > #5887

Re: Splay trees

Show all headers | View raw

"A. Bolmarcich" <aggedor@earl-grey.cloud9.net> wrote in message 
news:slrnn05qau.h67.aggedor@earl-grey.cloud9.net...
> On 2015-09-22, James Harris <james.harris.1@gmail.com> wrote:
>> Thank you very much for the measured figures. When you say you moved 
>> up
>> one level do you mean that you moved nodes up two levels in the
>> hierarchy, i.e. what might be called a zig-zig or zig-zag pair of
>> rotations? You will see I referred to a "step" up, meaning two levels 
>> of
>> the hierarchy. If the node is one level below the root I would just
>> leave it unchanged rather than doing a zig step.
>
> I moved a found node up one level.  A tree node found by a serach is
> moved to the position in the tree occupied by its parent before the
> search.  For example, given the subtree [ASCII art requiring a
> monospaced font]
>
> Before search for value 18.      After search for value 18.
>           .                               .
>           .                               .
>           .                               .
>           |                               |
>      +---22---+                      +---18---+
>      |        |                      |        |
>  +--18--+    26                     17    +--22--+
>  |      |                                 |      |
> 17     19                                19     26

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.

> where the node with the value 22 is an unspecified depth below the 
> root
> of the tree.  A found node one level below the root would become the
> root.
>
>> If you still have the testing setup in place I wonder if you could
>> compare the times taken for a full traversal of the tree. I would 
>> expect
>> the traditional splay-to-root to be faster than splaying up a step 
>> (two
>> levels) at a time as nearly all accesses would be to adjacent nodes 
>> and
>> splaying to root would bring adjacent nodes up too, but it would be
>> interesting to see how much difference it made to the time.
>
> By traversal, I take you to mean searching for all nodes in a sorted
> order.  (Traversal usually means visiting all the tree nodes by
> following the pointers.  Differently balanced trees with the same data
> should have about the same traversal time, ignoring the effect that
> additional levels of recursions can have with very unblanced trees.)

Yes, I was thinking of visiting each node in turn, if the nodes contain 
enough info to do that.

> Compared to an unbalanced tree, searching for all nodes in a sorted
> order was about 50% faster with a splay tree and about 140% slower for
> a move found node up one level tree.

OK. As mentioned, I think the zig-zig operation would be required in 
order to keep an approximate balance to the tree.

James

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