Unit 3: Data Structures on Trees
․Course contents: ⎯ ⎯
Binary search trees Red-black trees
․Readings: ⎯
Unit 3
Chapters 10 (self reading), 12, 13
Y.-W. Chang
1
Example Chip Floorplans
Pentium 4 PowerPC Unit 3
Y.-W. Chang
2
B*-tree: A Binary Tree Modeling for Floorplans ․ Chang et al., “B*-tree: A new representation for non-slicing ․
floorplans,” ACM/IEEE Design Automation Conference, 2000. Apply the Depth-First Search (DFS) to construct the tree. ⎯ left child: adjacent, bottom-most module on the right. ⎯ right child: nearest module above with the same x-coordinate.
n0 b6
b5 b1
b2 b0
b3 b
n7
b10
4
n8 b9 b8
b11
b7
n2 n5
n11 n9
n3
n10
Compacted floorplan Unit 3
n1
n4
B*-tree Y.-W. Chang
n6
3
B*-tree Based Floorplanner for Complex Designs
12,752 cells, 247 macros 2003年教育部 IC/CAD Contest 定題組特優 (第一名) 2003 ACM/SIGDA University Booth Show (DAC-2003) CPU time = 0.78 min on By Tung-Chieh Chen (陳東傑) SUN Blade 2000 Unit 3
Y.-W. Chang
4
Binary Search Tree ․ Binary-search-tree (BST) property: Let x be a node in a BST. If y is a node in the left subtree of x, then key[y] ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y]. ․ Tree construction: Worst case: O(n2); average case: O(nlgn), where n is the # of nodes. ․ Operations Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete can be performed in O(h) time, where h is the height of the tree. ․ Worst case: h = θ(n); balanced BST: h = θ(lgn). ․ Can we guarantee h = θ(lgn)? Balance search trees!!
Unit 3
Y.-W. Chang
5
Tree Search ․ Operations Search can be performed in O(h) time, where h is the height of the tree. Iterative-Tree-Search(x, k) 1. while x ≠ NIL and k ≠ key[x] 2. do if k < key[x] 3. then x ← left[x] 4. else x ← right[x] 5. return x
Unit 3
Y.-W. Chang
6
Tree Successor Tree-Successor(x) 1. if right[x] ≠ NIL 2. then return Tree-Minimum(right[x]) 3. y ← p[x] 4. while y ≠ NIL and x = right[y] y is the lowest ancestor of x, whose left child is also 5. do x ← y an ancestor of x 6. y ← p[y] 7. return y Tree-Minimum(x) 1. while left[x] ≠ NIL 2. do x ← left[x] 3. return x
y x y x Unit 3
4
Y.-W. Chang
7
Tree Insertion Tree-Insert(T, z) 1. y ← NIL 2. x ← root[T] 3. while x ≠ NIL 4. do y ← x 5. if key[z] < key[x] 6. then x ← left[x] 7. else x ← right[x] 8. p[z] ← y 9. if y = NIL 10. then root[T] ← z 11. else if key[z] < key[y] 12. then left[y] ← z 13. else right[y] ← z
Unit 3
Y.-W. Chang
xy xy 4
x z
8
Deletion in Binary Search Trees ․ Case a: The node to be deleted (z) has no children (i.e., a leaf). ․ Case b: The node to be deleted (z) has only one child. ․ Case c: The node to be deleted (z) has two children.
Unit 3
Y.-W. Chang
9
Tree Deletion Tree-Delete(T, z) 1. if left[z] = NIL or right[z] = NIL 2. then y ← z; 3. else y ← Tree-Successor(z); 4. if left[y] ≠ NIL 5. then x ← left[y]; 6. else x ← right[y]; 7. if x ≠ NIL 8. then p[x] ← p[y]; 9. if p[y] = NIL 10. then root[T] ← x; 11. else if y = left[p[y]] /* y is a left child.*/ 12. then left[p[y]] ← x; 13. else right[p[y]] ← x; 14. if y ≠ z then 15. then key[z] ← key[y]; /* Copy y's satellite data into z.*/ 16. 17. return y Unit 3
Y.-W. Chang
10
Tree Deletion (cont’d) Tree-Delete(T, z) 1. if left[z] = NIL or right[z] = NIL 2. then y ← z; 3. else y ← Tree-Successor(z); 4. if left[y] ≠ NIL 5. then x ← left[y]; 6. else x ← right[y]; 7. If x ≠ NIL 8. then p[x] ← p[y]; 9. if p[y] = NIL 10. then root[T] ← x; 11. else if y = left[p[y]] 12. then left[p[y]] ← x; 13. else right[p[y]] ← x; 14. if y ≠ z then 15. then key[z] ← key[y]; /* Copy y's satellite data into z. */ 16. 17. return y Unit 3
Y.-W. Chang
11
Balanced Search Trees: Red-Black Trees ․ Add color field to nodes of binary trees. ․ Red-black tree properties: 1. 2. 3.
4.
Unit 3
Every node is either red or black. Every leaf (NIL) is black. If a node is red, both its children are black (i.e., no two consecutive reds on a simple path). Every simple path from a node to a descendent leaf contains the same # of black nodes.
Y.-W. Chang
12
Black Height ․ Black height of node x, bh(x): # of blacks on path to leaf, not counting x. ․ Theorem: A red-black tree with n internal nodes has height at most 2lg(n+1). ⎯
⎯
Unit 3
Strategy: First bound the # of nodes in any subtree, then bound the height of any subtree. Claim 1: Any subtree rooted at x has ≥ 2bh(x) - 1 internal nodes. Proof by induction: bh(x) = 0 → x is a NIL (leaf) node. Assume the claim is true for all trees with black height < bh(x). If x is red, both subtrees have black height bh(x) - 1. If x is black, both subtrees have black height at least bh(x)-1. Thus, # of internal nodes in any subtree rooted at x is nx ≥ (2bh(x)-1 - 1) + (2bh(x)-1 - 1) + 1 ≥ 2bh(x) - 1.
Y.-W. Chang
13
Black Height (cont'd)
․Let h be the height of the red-black tree. ⎯
⎯
Claim 2: bh(root) ≥ h/2. (i.e., at least half the nodes on any single path from the root to leaf must be black.) By Property 3: ≤ h/2 nodes on that path are red. At root, n ≥ 2bh(root) - 1 ≥ 2h/2 - 1 ⇒ h ≤ 2 lg(n+1).
․Thus, red-black trees are balanced. (Height is at most twice optimal.) ․Corollary: Search, Minimum, Maximum, Predecessor, Successor take O(lgn) time. ․How about Delete and Insert? ⎯
Unit 3
Need to maintain the red-black tree properties!
Y.-W. Chang
14
Rotations
․Left/right rotations: The basic restructuring step for binary search trees. ․Rotation is a local operation changing O(1) pointers. ․In-order property preservation: An in-order search tree before a rotation stays an in-order one. ⎯ ⎯
Unit 3
In-order:
The property of a binary search tree still holds!!
Y.-W. Chang
15
Left Rotation Left-Rotate(T, x) 1. y ← right[x]; /* Set y.*/ 2. right[x] ← left[y]; /* Turn y's left subtree into x's right subtree.*/ 3. if left[y] ≠ NIL 4. then p[left[y]] ← x; 5. p[y] ← p[x]; /* Link x's parent to y.*/ 6. if p[x] = NIL 7. then root[T] ← y; 8. else if x = left[p[x]] /* x is a left child */ 9. then left[p[x]] ← y; 10. else right[p[x]] ← y; 11. left[y] ← x; /* Put x on y's left.*/ 12. p[x] ← y
Unit 3
Y.-W. Chang
16
Insertion
․Every insertion takes place at a leaf; this changes a black NIL pointer to a node with two black NIL pointers. ․To preserve the black height of the tree, the new node is set to red. ⎯
If the new parent is black, then we are done; otherwise, we must restructure (Property 3 violation)!!
․How to fix two reds in a row? Check uncle's color! ⎯
Unit 3
If the uncle is red, reversing the relatives' colors either solves the problem or pushes it one-level higher.
Y.-W. Chang
17
Insertion: Black Uncle
․How to fix two reds in a row? Check uncle's color! ⎯
⎯
Unit 3
If the uncle is black (all nodes around the new node and its parent must be black), rotate right about the grandparent. Change some nodes' colors to make the black height the same as before.
Y.-W. Chang
18
Insertion: Pseudocode
Unit 3
RB-Insert(T, x) 1. Tree-Insert(T, x); 2. color[x] ← RED; 3. while x ≠ root[T] and color[p[x]] = RED 4. do if p[x] = left[p[p[x]]] 5. then y ← right[p[p[x]]]; 6. if color[y] = RED /* uncle's color is red */ 7. then /* Case 1 */ 8. color[p[x]] ← BLACK; 9. color[y] ← BLACK; 10. color[p[p[x]]] ← RED; 11. x ← p[p[x]]; 12. else if x = right[p[x]] /* uncle's color is black */ 13. then /* Case 2*/ 14. x ← p[x]; 15. Left-Rotate(T,x); 16. color[p[x]] ← BLACK; /* Case 3*/ 17. color[p[p[x]]] ← RED; 18. Right-Rotate(T, p[p[x]]); 19. else (same as then clause with “right” and “left” exchanged) 20. color[root[T]] ← BLACK; Y.-W. Chang
19
Insertion: Example
left rotate
Unit 3
Y.-W. Chang
20
Deletion in Binary Search Trees Revisited ․ Case a: The node to be deleted has no children (i.e., a leaf). ․ Case b: The node to be deleted has only one child. ․ Case c: The node to be deleted has two children.
Unit 3
Y.-W. Chang
21
Deletion in Red-Black Trees
․If y (the spiced out node) is black, call RBDelete-Fixup (line 17) to fix the black height. (z: the deleted node; x: y's sole child)
Unit 3
RB-Delete(T,z) 1. if left[z] = nil[T] or right[z] = nil[T] then 2. y ← z; 3. else y ← Tree-Successor(z); 4. if left[y] ≠ nil[T] then 5. x ← left[y]; 6. else x ← right[y]; 7. p[x] ← p[y]; 8. if p[y] = nil[T] then 9. root[T] ← x; 10.else if y = left[p[y]] then left[p[y]] ← x; 11. 12. else right[p[y]] ← x; 13. if y ≠ z then 14. key[z] ← key[y]; 15 /* Copy y's satellite data, too. */ 16. if color[y] = BLACK then 17. RB-Delete-Fixup(T,x); 18. return y Y.-W. Chang
22
Deletion Color Fixup
․If y is black, we must give each of its descendants
another black ancestor ⇒ push y's blackness onto its child x. ․If an appropriate node is red, simply color it black; must restructure, otherwise. ⎯
⎯ ⎯
Black NIL becomes doubly black. Red becomes black. Black becomes doubly black.
․Goal: Recolor and restructure the tree so as to get rid of doubly black. ․Key: Move the extra black up the tree until ⎯ ⎯ ⎯
Unit 3
x points to a red node, simply color it black. x points to the root, the extra black can simply be removed. Suitable rotations and recolorings can be performed. Y.-W. Chang
23
Four Cases for Color Fixup ․ Case 1: The doubly black node x has a red sibling w. ․ Case 2: x has a black sibling and two black nephews. ․ Case 3: x has a black sibling, and its left nephew is red and its right nephew is black. ․ Case 4: x has a black sibling, and its right nephew is red (left nephew can be any color). ․ The # of black nodes in each path is preserved. ․ At most 3 rotations are done; only case 2 can be repeated. B A
Unit 3
Y.-W. Chang
24
Case 1 for Color Fixup
․Case 1: The doubly black node x has a red sibling w. ․One left rotation around p[x] and constant # of color changes are done. ․The # of black nodes in each path is preserved. ․Converts into case 2, 3, or 4.
Unit 3
Y.-W. Chang
25
Case 2 for Color Fixup
․Case 2: x has a black sibling and two black nephews. ․Take off one black from x and and its sibling, push one black up to p[x], and repeat the while loop with p[x] as the new node x. ․The # of black nodes in each path is preserved. ․Perform constant # of color changes and repeat at most O(h) times. (No rotation!!) B
Unit 3
Y.-W. Chang
26
Case 3 for Color Fixup
․Case 3: x has a black sibling, and its left nephew is red and its right nephew is black. ․Perform a right rotation on x’s sibling and constant # of color changes. ․The # of black nodes in each path is preserved. ․Convert into case 4.
Unit 3
Y.-W. Chang
27
Case 4 for Color Fixup
․Case 4: x has a black sibling, and its right nephew is red (left nephew can be any color). ․Performs a left rotation on p[x] and constant # of color changes => remove the doubly black on x. ․The # of black nodes in each path is preserved. ․Make x as the root and terminate the while loop.
Unit 3
Y.-W. Chang
28
Color Fixup for Deletion RB-Delete-Fixup(T,x) 1. while x ≠ root[T] and color[x] = BLACK do 2. if x=left[p[x]] then 3. w ← right[p[x]]; 4. if color[w] = RED then 5. color[w] ← BLACK; /* Case 1 */ 6. color[p[x]] ← RED; /* Case 1 */ 7. Left-Rotate(T, p[x]); /* Case 1 */ 8. w ← right[p[x]]; /* Case 1 */ 9. If color[left[w]] = BLACK and color[right[w]] = BLACK then 10. color[w] ← RED; /* Case 2*/ 11. x ← p[x]; /* Case 2 */ 12. else if color[right[w]] = BLACK then 13. color[left[w]] ← BLACK; /* Case 3*/ 14. color[w] ← RED; /* Case 3*/ 15. Right-Rotate(T, w); /* Case 3*/ 16. w ← right[p[x]]; /* Case 3*/ 17. color[w] ← color[p[x]]; /* Case 4*/ 18. color[p[x]] ← BLACK; /* Case 4*/ 19. color[right[w]] ← BLACK; /* Case 4*/ 20. Left-Rotate(T, p[x]); /* Case 4*/ 21. x ← root[T]; 22. else (same as then clause with "right" and "left" exchanged) 23. color[x] ← BLACK; Unit 3
Y.-W. Chang
29
Conclusion: Red-Black Trees
․Red-black trees are balanced binary search trees. ․All dictionary operations (Minimum, Maximum, Search, Successor, Predecessor, Insert, Delete) can be performed in O(lgn) time. ․At most 3 rotations are done to rebalance.
Unit 3
Y.-W. Chang
30
Example Floorplans Revisited
Pentium 4 PowerPC Unit 3
Y.-W. Chang
31
Slicing Tree ․ Otten, “Automatic floorplan design,” ACM/IEEE Design Automation Conference, 1982. ․ Binary-tree structure for slicing floorplans. ⎯ An internal node denotes a vertical or a horizontal cut. ⎯ A leaf denotes a module. V H
b3
b1
H 1
2 b4 b2
V
V b6
3
b5 b7
6
A slicing floorplan Unit 3
H
7 4
5
A slicing tree Y.-W. Chang
32
B*-tree Revisited ․ Chang et al., “B*-tree: A new representation for non-slicing ․
floorplans,” ACM/IEEE Design Automation Conference, 2000. Apply the Depth-First Search (DFS) to construct the tree. ⎯ left child: adjacent, bottom-most module on the right. ⎯ right child: nearest module above with the same x-coordinate.
n0 b6
b5 b1
b2 b0
b3 b
n7
b10
4
n8 b9 b8
b11
b7
n2 n5
n11 n9
n3
n10
Compacted floorplan Unit 3
n1
n4
B*-tree Y.-W. Chang
n6
33
Cost Evaluation: Packing
․ x-coordinates can be determined by the tree structure. ⎯ ⎯
Left child: the lowest, adjacent block on the right (xj = xi + wi). Right child: the first block above, with the same x-coordinate (xj = xi).
․ y-coordinates? b5 b b11
n0
b6 b3
b2
b10
n7
b4
n1
n8
x1=x0 b00
n2 n5
b9 b8
b11
n11 n9
n3
n6
b7 (x0,y0)
w0 Unit 3
x7=x0+w0 Y.-W. Chang
n10
n4 34
Computing y-coordinates
․Reduce the complexity of computing a y-coordinate to amortized O(1) time. horizontal contour vertical contour b10
b1 b3 b
4
b0
b9 b8
b11 b7
Unit 3
Y.-W. Chang
35
Perturbations
․Example perturbations Op1: rotate a module Op2: delete & insert a module Op3: swap 2 modules
⎯ ⎯ ⎯
2
2 4 1 13 15
4
7
1
12 3
11
13
5
1
12 7
11 10
13
6 5
15 9
9
12 3
10
11
9 14
14
14
8
8
Unit 3
7
Op2(11, 5)
6
15
10
4
3
Op3(7, 3)
6 5
2
Y.-W. Chang
8
36
B*-trees for Large-Scale Designs
9800 modules, dead space = 3.44%, CPU time = 256 min on SUN Ultra 60
Unit 3
Y.-W. Chang
12,752 cells, 247 macros CPU time = 0.78 min on SUN Blade 2000 37
B*-trees for Analog Circuit Design ․ The best analog layout placement tool by Balasa et al. (ICCAD2002, ASP-DAC-2003 best paper nomination) based on RB B*trees
Unit 3
Y.-W. Chang
38
Floorplan Quality Comparison ․ B*-tree is the best representation for packing reported in a recent survey (Chan, Adya, Markov, ISPD-05) ․ B*-tree citations: more than 100 citations in ACM/IEEE papers since its publication at DAC-2K (> 70% of floorplanning papers) ․ B*-tree code is available at http://eda.ee.ntu.edu.tw/research.htm/ MCNC SP Q-Seq O-tree CBL Slicing TCG Ckts (Japan) (Japan) (USA) (China) (USA) (Ours) 1995 2002 1999 2001 2005 DAC 2001
TCG-S (Ours) DAC 2002
CS B*-tree (Ours) (Ours) TVLSI DAC 2003 2000
apte
48.12
46.92
47.1
NA
46.92
46.92
46.92
46.92
46.92
xerox
20.69
19.93
20.1
20.96
20.20
19.83
19.796
19.83
19.796
hp
9.93
9.03
9.21
NA
9.03
8.947
8.947
8.947
8.947
ami33
1.22
1.194
1.25
1.20
1.183
1.20
1.185
1.18
1.168
ami49
38.84
36.75
37.6
38.58
36.24
36.77
36.4
36.24
36.4
Best chip areas are in red (mm2) Unit 3
Y.-W. Chang
39