Elemental Design Patterns - Computer Science

Elemental Design Patterns - Computer Science

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 )

Recently Viewed Presentations

  • Medicines Manufacturing in the UK 2017 Medicines Manufacturing

    Medicines Manufacturing in the UK 2017 Medicines Manufacturing

    Small molecule manufacturing is an example where the UK capabilities can become world leading. Improved productivity through continuous processing and processing analytical technology offer opportunities
  • Koloidi I Makromolekuli

    Koloidi I Makromolekuli

    KOLOIDI I MAKROMOLEKULI Sistemi u kojima je jedna ili više supstancija u većoj ili manjoj meri usitnjena i ravnomerno raspoređena u okružujućoj sredini, su disperzni sistemi.
  • Tying it all together: the major causes of wwi

    Tying it all together: the major causes of wwi

    In order to fuel this idea of national superiority, European powers built up their militaries, looked to expand their empires, and sought exuberant amounts of wealth/resources. Also fueled by propaganda, literature, and other mass media. All this chest-pounding led to...
  • Global Strategy to Improve Agricultural and Rural Statistics

    Global Strategy to Improve Agricultural and Rural Statistics

    However, staff turnover may hinder the work, because of the absence of trained data collectors and the discontinuity of data collection. The use of technological tools facilitates the work of data collectors and supports routine data collections frameworks.
  • The Role of Money in Macroeconomics

    The Role of Money in Macroeconomics

    Precautionary Motive. Speculative Motive . REAL AND NOMINAL MONEY BALANCES. Nominal money demand. The demand for money in monetary units. Real money demand. Number of units of purchasing power that the public wishes to hold in the form of money...
  • The Epic as a quest.

    The Epic as a quest.

    An Elegiac Poem A mournful, melancholy, or plaintive poem Especially a funeral song or lament for the dead Traditional 3 Stages of Loss Greif and sorrow Praise and admiration Consolation and solace Epic or Elegy Conventions of Genre The Epic...
  • 2011-2012 FIMC-VI Webinar Series PowerPoint for the Teacher

    2011-2012 FIMC-VI Webinar Series PowerPoint for the Teacher

    Missouri Battleship. Pearl Harbor, December 7. th, 1941. Alicia and Al visited Pearl Harbor to celebrate their 25th wedding anniversary in July of 2011. ... An Excel Spreadsheet will open with sample data included. You change the data to reflect...
  • The Aeneid An Introduction - LVV-4U1 Classical Civilizations

    The Aeneid An Introduction - LVV-4U1 Classical Civilizations

    Myth had stopped being realistic and historical and had in fact become the complete opposite, used mainly by tragedians as 'exemplum', to demonstrate their ideals [1] [2] Otis, p2 Although the Aeneid has the Odyssey and the Iliad as its...