Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5886
| 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> |
| Message-ID | <slrnn05qau.h67.aggedor@earl-grey.cloud9.net> (permalink) |
| Date | 2015-09-23 13:03 -0500 |
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
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.)
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.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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