Java Reference
In-Depth Information
figure 22.1
Rotate-to-root
strategy applied when
node 3 is accessed
4
4
3
2
5
3
5
2
4
1
3
2
1
5
1
figure 22.2
Insertion of 4 using
the rotate-to-root
strategy
3
3
4
2
2
4
3
1
1
2
1
figure 22.3
Sequential access of
items takes quadratic
time
4
1
2
3
4
3
4
1
4
2
4
3
2
3
3
1
2
1
2
1
the basic bottom-up splay tree
22.2
Achieving logarithmic amortized cost seems impossible because, when we
move an item to the root via rotations, other items are pushed deeper. Seem-
ingly, that would always result in some very deep nodes if no balancing
information is maintained. Amazingly, we can apply a simple fix to the
rotate-to-root strategy that allows the logarithmic amortized bound to be
obtained. Implementation of this slightly more complicated rotate-to-root
method called
splaying
leads to the basic
bottom-up splay tree.
In a basic
bottom-
up splay tree,
items
are rotated to the
root by using a
slightly more com-
plicated method
than that used for a
simple rotate-to-
root strategy.
Search WWH ::
Custom Search