CMSC 341 Splay Tree Diagrams Bottom Up Splaying These diagrams show the rotations necessary for Bottom Up splaying Note that these diagrams illustrate the rotations necessary whenever the node to be splayed is a left child Symmetric rotations are performed when the node is a right child 8 3 2007 UMBC CMSC 341 Splay Diagrams 2 Bottom Up Single Rotation 8 3 2007 UMBC CMSC 341 Splay Diagrams 3 Bottom Up Zig Zig 8 3 2007 UMBC CMSC 341 Splay Diagrams 4 Bottom Up Zig Zag G G A X B X A P D P B C C D X G A 8 3 2007 P B C D UMBC CMSC 341 Splay Diagrams 5 Top Down Splaying These diagrams illustrate the reorganization of the splay tree as we follow the left link from a node Note that symmetric reorganization of the tree occurs when the right link is followed 8 3 2007 UMBC CMSC 341 Splay Diagrams 6 Top Down Zig X L R L R Y X Y XR YL YL 8 3 2007 Yr XR Yr UMBC CMSC 341 Splay Diagrams 7 Top Down Zig Zig X L Y R L R Z Y XR Z ZL X Zr YR YR ZL 8 3 2007 XR Zr UMBC CMSC 341 Splay Diagrams 8 Top Down Zig Zag X L Y L R Y XR YL X YL Z ZL 8 3 2007 R Z ZL Zr UMBC CMSC 341 Splay Diagrams XR Zr 9
View Full Document
Unlocking...