Scribd
Upload
31 views18 pages

S Play Trees

This document discusses splay trees, which are self-adjusting binary search trees (BSTs) that provide amortized O(log n) time for operations by splaying nodes. Splaying involves rotating nodes along the access path to the root to improve future access times. Specifically, it describes: 1) Problems with standard BSTs where sequences of operations can take O(n) time due to unbalanced trees. 2) How splay trees guarantee amortized O(log n) time for sequences of M operations through splaying accessed nodes. 3) The splaying process involves rotations to push the accessed node to the root, improving future access to it and nodes along the path.

Uploaded by

saiteja1234
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
31 views18 pages

S Play Trees

This document discusses splay trees, which are self-adjusting binary search trees (BSTs) that provide amortized O(log n) time for operations by splaying nodes. Splaying involves rotating nodes along the access path to the root to improve future access times. Specifically, it describes: 1) Problems with standard BSTs where sequences of operations can take O(n) time due to unbalanced trees. 2) How splay trees guarantee amortized O(log n) time for sequences of M operations through splaying accessed nodes. 3) The splaying process involves rotations to push the accessed node to the root, improving future access to it and nodes along the path.

Uploaded by

saiteja1234
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 18

CMSC 341

Splay Trees

Problems with BSTs


Because the shape of a BST is determined by the order that
data is inserted, we run the risk of trees that are essentially
lists
21
12
32
37
20 24

15

40
55
56
77
95

12/14/2014

BST Sequence of Operations


Worst case for a single BST operation can be O( N )
Not so bad if this happens only occasionally
BUT...its not uncommon for an entire sequence of bad
operations to occur. In this case, a sequence of M operations
take O (M*N) time and the time for the sequence of operations
becomes noticeable.

12/14/2014

Splay Tree Sequence of Operations


Splay trees guarantee that a sequence of M operations takes
at most O( M * lg N ) time.
We say that the splay tree has amortized running time of
O( lg N ) cost per operation. Over a long sequence of
operations, some may take more than lg N time, some will
take less.
Does not preclude the possibility that any particular
operation is still O( N ) in the worst case.
Therefore, amortized O( lg N ) not as good as worst case
O( lg N)
But, the effect is the same there is no bad sequence of
operations or bad input sequences
12/14/2014

Splay Trees
If any particular operation is O( N ) and we still want
amortized O( lg N ) performance, then whenever a node is
accessed it must be moved. Otherwise its access time is
always O( N ).
The basic idea of the splay tree is that every time a node is
accessed, it is pushed to the root by a series of tree
rotations. This series of tree rotations is knowing as
splaying.

If the node being splayed is deep, many nodes on the path to


that node are also deep and by restructuring the tree, we
make access to all of those nodes cheaper in the future.
12/14/2014

Basic Single Rotation in a BST

Rotating k1 around k2

Assuming that the tree on the left is a BST, how can we


verify that the tree on the right is still a valid BST?

Note that the rotation can be performed in either direction.


12/14/2014

Splay Operation
To splay node x, traverse up the tree from node x to root,
rotating along the way until x is the root
Each rotation
If x is root, do nothing.
If x has no grandparent, rotate x about its parent
If x has a grandparent,
if x and its parent are both left children or both right children,
rotate the parent about the grandparent, then rotate x about its
parent
if x and its parent are opposite type children (one left and the
other right), rotate x about its parent, then rotate x about its
new parent (former grandparent)
12/14/2014

Node has no grandparent

12/14/2014

Node and Parent are Same Side


Zig-Zig

Rotate P around G, then X around P


12/14/2014

Node and Parent are Different Sides


Zig-Zag

Rotate X around P, then X around G


12/14/2014

10

Operations in Splay Trees


insert
first insert as in normal binary search tree
then splay inserted node
if there is a duplicate, the node holding the duplicate
element is splayed
find/contains
search for node
if found, splay it; otherwise splay last node accessed on
the search path

12/14/2014

11

Operations on Splay Trees (cont)


remove
splay element to be removed
if the element to be deleted is not in the tree, the node last
visited on the search path is splayed

disconnect left and right subtrees from root


do one or both of:
splay max item in TL (then TL has no right child)
splay min item in TR (then TR has no left child)

connect other subtree to empty child of root

12/14/2014

12

Exercise - find( 65 )
50
40

20

60

43

70
65

16

63

12/14/2014

66

13

Exercise - remove( 25 )
50
40

20
16

60

43

70
65

25

63

12/14/2014

66

14

Insertion in order into a Splay Tree

In a BST, building a tree from N sorted elements was O( N2 )


What is the performance of building a splay tree from N
sorted elements?
12/14/2014

15

An extreme example of splaying


Title:
splay .zig_zag.eps
Creator:
f ig2dev Vers ion 3.2 Patchlev el 0-beta2
Prev iew:
This EPS picture was not sav ed
with a prev iew inc luded in it.
Comment:
This EPS picture will print to a
PostSc ript printer, but not to
other ty pes of printers.

12/14/2014

16

Splay Tree Code


The splaying operation is performed up the tree from the
node to the root.
How do we traverse up the tree?
How do we know if X and P are both left/right children or
are different children?
How do we know if X has a grandparent?
What disadvantages are there to this technique?

12/14/2014

17

Top-Down Splay Trees


Rather than write code that traverses both up and down the
tree, top-down splay trees only traverse down the tree.
On the way down, rotations are performed and the tree is
split into three parts depending on the access path (zig, zigzig, zig-zag) taken
X, the node currently being accessed
Left all nodes less than X
Right all nodes greater than X
As we traverse down the tree, X, Left, and Right are
reassembled
This method is faster in practice, uses only O( 1 ) extra
space and still retains O( lg N ) amortized running time.
12/14/2014

18

You might also like