程序代写代做代考 AVL C algorithm B tree COMP251: Red-black trees

COMP251: Red-black trees
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Cormen et al., 2002) Based on slides from D. Plaisted (UNC)

Red-black trees: Overview
• Red-black trees are a variation of binary search
trees to ensure that the tree is balanced.
– Height is O(lg n), where n is the number of nodes.
• Operations take O(lg n) time in the worst case.
• Invented by R. Bayer (1972).
• Modern definition by L.J. Guibas & R. Sedgewick (1978).

Red-black Tree
• Binary search tree + 1 bit per node: the
attribute color, which is either red or black. • All other attributes of BSTs are inherited:
– key, left, right, and parent.
• All empty trees (leaves) are colored black.
– Note: We can use a single sentinel, nil, for all the leaves of red-black tree T, with color[nil] = black. The root’s parent is also nil[T ].

Red-black (RB) Properties
1. Every node is either red or black.
2. The root is black.
3. All leaves (nil) are black.
4. If a node is red, then its children are black (i.e. no 2 consecutive red nodes).
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes (i.e. same black height).

Red-black Tree – Example
26
17
41
47 Nil
Nil Nil
Nil
Nil
30 Nil
38
50
Note: every internal node has two children, even though nil leaves are not usually shown.
Nil
Nil

Height of a Red-black Tree • Height of a node:
– h(x) = number of edges in the longest path to a leaf. • Black-height of a node x, bh(x):
– bh(x) = number of black nodes (including nil[T ]) on the path from x to leaf, not counting x.
• Black-height of a red-black tree is the black-height of its root.
– wBy RB Property 5, black height is well defined.

Height of a Red-black Tree
h=4 bh=2
41
17
26
h=1 bh=1
h=3 bh=2
h=2 bh=1
Nil
#edges in a longest path to a leaf. Nil
Nil
• Heighth(x):
• Black-height bh(x):
h=2 bh=1
30
h=1 bh=1
Nil
47 Nil h=1
38
bh=1 50 Nil Nil
# black nodes on path from x to leaf, not counting x.
Nil
• Property:bh(x)≤h(x)≤2bh(x)

Bound on RB Tree Height
Lemma 1: Any node x with height h(x) has a black-height bh(x) ≥ h(x)/2.
Proof: By RB property 4, ≤ h / 2 nodes on the path from the node to a leaf are red. Hence ≥ h/2 are black.n
26
17
41
Nil
Nil
30 Nil
47
38
50
Nil
Nil
Nil Nil

Bound on RB Tree Height
Lemma 2: The subtree rooted at any node x contains 3 2bh(x) – 1 internal nodes.
Proof: By induction on height of x.
• BaseCase: Heighth(x)=0ÞxisaleafÞbh(x)=0.
Subtree has 3 20–1 = 0 nodes. • Induction Step:
– Each child of x has height h(x) – 1 and black-height either bh(x) (child is red) or bh(x) – 1 (child is black).
– By ind. hyp., each child has 3 2bh(x)– 1 – 1 internal nodes.
– Subtreerootedatxhas 32Ÿ(2bh(x)–1 –1)+1 = 2bh(x) – 1 internal nodes.n

Bound on RB Tree Height
Lemma 1: Any node x with height h(x) has a black-height bh(x) ≥ h(x)/2.
Lemma 2: The subtree rooted at any node x has 3 2bh(x)–1 internal nodes.
Lemma 3: A red-black tree with n internal nodes has height at most 2 lg(n+1).
Proof:
• Bylemma2,n32bh –1,
• Bylemma1,bh3h/2,thusn32h/2 –1. • Þ h£2lg(n+1).

Insertion in RB Trees
• Insertion must preserve all red-black properties.
• Should an inserted node be colored Red? Black?
• Basic steps:
– Use BST Tree-Insert to insert a node x into T.
• Procedure RB-Insert(x). – Color the node x red.
– Fix the new tree by (1) re-coloring nodes, and (2) performing rotation to preserve RB tree property.
• Procedure RB-Insert-Fixup.

Insertion
Regular BST insert + color assignment + fixup.
RB-Insert(T, z) Contd.
14. left[z] ¬ nil[T]
15. right[z] ¬ nil[T]
16. color[z] ¬ RED
17. RB-Insert-Fixup (T, z)
RB-Insert(T, z)
1.
2.
3.
4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
y ¬ nil[T]
x ¬ root[T] while x 1 nil[T]
do y ¬ x
if key[z] < key[x] then x ¬ left[x] else x ¬ right[x] p[z] ¬ y if y = nil[T] then root[T] ¬ z else if key[z] < key[y] then left[y]¬z else right[y] ¬ z Insert RB Tree – Example 7 3 18 Nil Nil 10 Nil Nil 20 8 11 Nil 22 Nil Nil Nil Nil Insert RB Tree – Example 7 3 18 Nil Nil 10 Nil 20 15 Nil Nil 8 11 Nil Nil 22 Nil Nil Nil Insert(T,15) Insert RB Tree – Example 7 3 18 Nil Nil 10 Nil 20 15 Nil Nil 8 11 Nil Nil 22 Nil Nil Nil Recolor 10, 8 &11 Insert RB Tree – Example 7 3 18 Nil Nil 10 Nil 20 15 Nil Nil 8 11 Nil Nil 22 Nil Nil Nil Right rotate at 18 Insert RB Tree – Example 7 3 10 Nil Nil 8 Nil 18 15 Nil Nil 11 Nil 20 Nil Nil Nil 22 Parent & child with conflict are now aligned with the root. Nil Insert RB Tree – Example 7 3 10 Nil Nil 8 Nil 18 15 Nil Nil 11 Nil 20 Nil Nil Nil 22 Left rotate at 7 Nil Insert RB Tree – Example 10 7 3 8 11 18 15 20 Nil Nil Nil Nil Nil Nil Nil Nil Nil 22 Nil Insert RB Tree – Example 10 7 18 15 3 8 11 20 Nil Nil Nil Nil Nil Nil Nil Nil Nil 22 Recolor 10 & 7 (root must be black!) Nil Insertion – Fixup RB-Insert-Fixup (T, z) 1. 2. 3. 4. 5. 6. 7. 8. while color[p[z]] = RED do if p[z] = left[p[p[z]]] then y ¬ right[p[p[z]]] if color[y] = RED then color[p[z]] ¬ BLACK // Case 1 color[y] ¬ BLACK color[p[p[z]]] ¬ RED z ¬ p[p[z]] // Case 1 // Case 1 // Case 1 Insertion – Fixup RB-Insert-Fixup(T, z) (Contd.) // Case 2 // Case 2 else if z = right[p[z]] // color[y] 1 RED 9. 10. 11. 12. 13. 14. 15. 16. 17. color[root[T ]] ¬ BLACK then z ¬ p[z] LEFT-ROTATE(T, z) color[p[z]] ¬ BLACK color[p[p[z]]] ¬ RED RIGHT-ROTATE(T, p[p[z]]) // Case 3 else (if p[z] = right[p[p[z]]])(same as 10-14 with “right” and “left” exchanged) // Case 3 // Case 3 Case 1 – uncle y is red p[p[z]] C new z C D de B p[z] A y DA azde a B z is a right child here. Similar steps if z is a b g leftchild. b g • p[p[z]] (z’s grandparent) must be black, since z and p[z] are both red and there are no other violations of property 4. • Make p[z] and y black Þ now z and p[z] are not both red. But property 5 might now be violated. • Make p[p[z]] red Þ restores property 5. • The next iteration has p[p[z]] as the new z (i.e., z moves up 2 levels). Case 2 – y is black, z is a right child p[z] A C D z y (new) p[z] C BD y δ λ (new)z A g δ λ Left rotate around p[z], p[z] and z switch roles Þ now z is a left child, and both z and p[z] are red. Takes us immediately to case 3. a b B g ab • • Case 3 – y is black, z is a left child p[p[z]] p[z] B z abg Then right rotate right on p[p[z]] (in order to maintain property 4). No longer have 2 reds in a row. p[z] is now black Þ no more iterations. C BD y z p[z] Ag AC δλ D δλ • • • • Make p[z] black and p[p[z]] red. a b Algorithm Analysis • O(lg n) time to get through RB-Insert up to the call of RB-Insert-Fixup. • Within RB-Insert-Fixup: – Each iteration takes O(1) time. – Each iteration but the last moves z up 2 levels. – O(lg n) levels Þ O(lg n) time. – Thus, insertion in a red-black tree takes O(lg n) time. – Note: there are at most 2 rotations overall. Correctness Loop invariant: • At the start of each iteration of the while loop, – z is red. – There is at most one red-black violation: • Property 2: z is a red root, or • Property 4: z and p[z] are both red. Correctness – Contd. • Initialization:✓ • Termination:Theloopterminatesonlyifp[z]isblack. Hence, property 4 is OK. The last line ensures property 2 always holds. • Maintenance:Wedropoutwhenzistheroot(since then p[z] is sentinel nil[T ], which is black). When we start the loop body, the only violation is of property 4. – There are 6 cases, 3 of which are symmetric to the other 3. We consider cases in which p[z] is a left child. – See cases 1, 2, and 3 described above. AVL vs. Red-Black Trees • AVL trees are more strictly balanced ⇒ faster search • Red Black Trees have less constraints and insert/remove operations require less rotations ⇒ faster insertion and removal • AVL trees store balance factors or heights with each node • Red Black Tree requires only 1 bit of information per node Further Readings [CLRS2009] Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms. (available as E-book) See Chapter 13 for the complete proofs & deletion