Data Structures and Analysis (COMP 410) David Stotts Computer Science Department UNC Chapel Hill Splay Tree Another Balanced BST SPLT: BST with Balance A Splay Tree (SPLT) is another type of balanced BST. Conceptually less complex than AVL tree No need for subtree balance information Easier programming No balance property guiding the balancing Rather we perform a splaying operation at various times to re-arrange the tree No Balance Condition AVL tree has condition that height of two
subtrees must differ by 1 or 0 when it gets to 2, there is imbalance In a splay tree the splaying operation tends to balance the tree somewhat in many cases, but sometime it stretches it a bit Over time when we do a sequence of splays the good will balance out the bad and give us overall acceptable collective behavior Splaying The Basic Idea After we access a node (insert, search) it gets pushed upward to the root by a series of AVL rotations Has the effect of creating locality Once we access a node, if it is deep on a path, then subsequent accesses to that node will find it at or near the root (for a while) Splaying 3 cases of rotation (and symmetries)
Assume Node X is the one that needs to be splayed to the root (zig) Node X has a parent P, no grandparent This means X is almost the tree root it is one level down Use normal AVL single rotation P splay 15 1 0 Path from X back to root is what give the pattern X 15 7 2 9 12 20 25 Splaying 3 cases of rotation (and symmetries) Assume Node X is the one that needs to be splayed to the root
(zig-zig RR) Node X is R-child of a parent P, and P is R-child of grandparent G ( symm. L-L ) 7 splay 17 Path from X back to root is what gives the pattern 10 2 1 G P 13 3 17 9 1 X 2 Splaying 3 cases of rotation (and symmetries) Assume Node X is the one that needs to be splayed to the root
(zig-zag RL) Node X is R-child of parent P, and P is L-child of grandparent G ( symm. L-R ) 7 splay 15 G 2 Path from X back to root is what gives the pattern 1 17 10 3 P 15 9 1 2 2 0 X use double AVL rotation A Reminder
Single AVL rotations Zig R Pattern Node X has a parent P, no grandparent AVL single rotation P X C X P B A A C B Node X has parent P Zig R Example no grandparent P 1 0
X 15 7 2 C 9 12 B find ( 15 ) Means we splay 15 to root Use single AVL 20 15 P 1 0 7 25 A X 3 1 2 C
9 20 25 12 B A 3 1 X is R-child of parent P Zig Zig R Pattern P is R-child of grandparent G X Use the pattern G P P D A X G
B C B A D C Zig-Zig L Example X is L-child of parent P P is L-child of grandparent G X 7 15 P P 1 0 X 7 2 1 A3
12 C 9 B 2 20 25 D 3 1 find ( 7 ) Means we splay 7 to root Use double AVL 1 A 10 9 3 15 G B 2 0
1 C2 25 D 3 1 X is R-child of parent P Zig Zag L Pattern P is L-child of grandparent G AVL double rotation G X P P G D X A A B C
B C D Example: do Zig-Zag L X is R-child of parent P P is L-child of grandparent 9 9 2 5 20 5 A 23 12 2 19 P
P 8 X G G 20 12 8 X 31 19 10 17 B 10 A C 27 3 7 17 B
C 23 31 D find ( 19 ) we splay 19 to root use double AVL 27 D 3 7 Now do a Zig R X is R-child of parent P No grandparent Splay again Now 19 is one level below root rotate left P 9 X 5 2 C 8
P 19 20 12 23 10 17 B 31 19 9 X 20 5 12 2C 8 10 17 B 23 31 27 A
27 3 7 A 3 7 When to Splay? insert Insert BST style, then splay the new node to root Each insert causes new root contains If node is found, splay it to root findMin (Max) Node will be found, splay it to root When to Splay? remove Remove node BST-style Splay parent of removed node to root What do we do if we must remove the root?
remove (alternate, do this) Splay node to be removed to root Remove the root, leaving two disconnected subtrees join these 2 trees by findMax in left subtree, then hand right subtree as right child of new root When to Splay? Remove (what if item is not in tree?) At some node N we realize the item is not in the tree The right (or left) subtree of N is not there, so the item to be removed is not there Then splay the node N, it becomes the new root ADT: Splay Tree SPLT SPLT is a BST with Signature
new: insert: remove: findMin: findMax: contains: get: val: size: empty: splay: BST BST BST BST BST BST BST BST BST BST x Elt x Elt x Elt x Elt
BST splay happens on insert, access, BST remove BST Elt Elt Boolean (searching) BST (return a cell) Elt (get root value) Nat (natural number) Boolean BST (might want this instead of code dupe) SPLT Complexity Splays might lengthen the path for some nodes (temporarily make balance worse) Cannot guarantee O(log N) bound for any single operation
O(N) worst case still holds for insert, find, etc. Has amortized complexity O(log N) Any sequence of M operations takes total time O(M log N) No bad sequences like BST has SPLT Complexity Linked: Time complexity of operations worst insert remove findMin findMax contains get splay empty size val amort amort amort amort amort amort amort O(1) O(1)
O(1) avg O(log O(log O(log O(log O(log O(log O(log n), n), n), n), n), n), n), O(log O(log O(log O(log O(log O(log O(log (keep counter) (root access) n) n) n) n) n) n)
n) SPLT Implementation Linked structure Class SPLTCell { String value; SPLTCell LC; SPLTCell RC; SPLTCell parent; // others like height, etc. // as needed for assignment } Coding it Up X is R-child of parent P P is L-child of grandparent 9 9 2 5 20 5 A 23 12
2 19 P P 8 X G G 20 12 8 X 31 19 10 17 B 10 A C 27
3 7 17 B C 23 31 D find ( 19 ) we splay 19 to root use double AVL 27 D 3 7 X is R-child of parent P P is L-child of grandparent N 9 Splaying 19 to root G
Capture the pattern parts X is node of interest 20 5 2 Coding it Up P A 23 12 8 X 31 19 10 17 B C 27 3 7
D P G N A B C D = = = = = = = X.parent P.parent G.parent P.Lchild X.Lchild X.Rchild G.Rchild Rearrange pattern parts N.Rchild = X X.Lchild = P X.Rchild = G P.Lchild = A P.Rchild = B G.Lchild = C G.Rchild = D
And adjust parent pointers for nodes that move P.parent = X etc. D.Parent = G etc. Coding it Up 9 5 2 N X 19 P 20 12 8 10 A G 17 B C 23 31 27
D 3 7 END Beyond this is just templates Splaying 3 cases of rotation (and symmetries) Assume Node X is the one that needs to be splayed to the root (zig) Node X has a parent, no grandparent This means X is almost the tree root it is one level down Use normal AVL single rotation (zig-zig) Node X is L-child of a parent P, and P is L-child of grandparent G ( or R-R ) (zig-zag) Node X is R-child of parent P, and P is Lchild of grandparent G ( or L-R )
