Algorithms & Data Structures (Winter 2021) Red-
Announcements
• A1 has been released.
Copyright By PowCoder代写 加微信 powcoder
• Please start early.
• Try by yourself + Use discussion board + OH.
Comp 251(c) 2021
• Introduction. • Operations.
Introduction – Red-Black trees
• Red-black trees are a variation of binary search trees to ensure that the tree is ‘approximately’ balanced.
• Height is O(lg n), where n is the number of nodes.
• BST + 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).
• no path (from the root to a leaf) is more than twice as long as any other path.
• Operations take O(lg n) time in the worst case.
• Invented by R. Bayer (1972).
• Modern definition by L.J. Guibas & R. Sedgewick (1978).
Comp 251(c) 2022
Red-Black trees – 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).
Comp 251(c) 2022
Red-Black trees – example
Note: every internal node has two children, even though nil leaves are not usually shown.
Comp 251(c) 2022
Red-Black trees – height
• 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. • By RB Property 5, black height is well defined.
Comp 251(c) 2022
Red-Black trees – height
• Height h(x):
#edges in a longest path to a leaf.
• Black-height bh(x):
# black nodes on path from x to leaf,
not counting x.
• Property: bh(x) ≤ h(x) ≤ 2 bh(x)
h=2 30 bh=1
h=1 50 bh=1
Comp 251(c) 2022
Red-Black trees – 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
Comp 251(c) 2022
Red-Black trees – 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(Nil)Þ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
Comp 251(c) 2022
Red-Black trees – 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).
•Bylemma2,n32bh –1, •Bylemma1,bh3h/2,thusn32h/2 –1. •Þ h£2lg(n+1).
Comp 251(c) 2022
• Introduction. • Operations.
RB trees – Insertion
• 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 rotations to
preserve RB tree property.
• Procedure RB-Insert-Fixup.
Comp 251(c) 2022
RB trees – Insertion
RB-Insert(T, z)
4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
y ¬ nil[T]
x ¬ root[T] while x 1 nil[T]
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
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)
Comp 251(c) 2022
RB trees – 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
thencolor[p[z]]¬BLACK //Case1
color[y] ¬ BLACK color[p[p[z]]] ¬ RED z ¬ p[p[z]]
// Case 1 // Case 1
// Case 1 15
Comp 251(c) 2022
RB trees – Insertion - Fixup
RB-Insert-Fixup(T, z) (Contd.)
// Case 2 // Case 2
else if z = right[p[z]] // color[y] 1 RED
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
Comp 251(c) 2022
RB trees – Insertion - Fixup
1. To determine what violations of the red-black properties are introduced in RB-Insert when node z is inserted and colored red.
2. To understand each of the three cases within the while loop’s body
3. To understand the overall goal of the while loop in lines 1-15.
RB trees – Insertion - Fixup
To determine what violations of the red-black properties are introduced in RB-Insert when node z is inserted and colored red.
Every node is either red or black.
The root is black.
• Violatedifzistheroot.
All leaves (nil) are black.
• Violatedifz’sparentisred
i.e. no 2 consecutive red
If a node is red, then its children are black (
For each node, all paths from the node to descendant leaves contain the
same number of black nodes (i.e. same black height).
• nodezreplacesthe(black)sentinel,andnodezisredwithsentinelchildren.
RB trees – Insertion - Fixup
2. To understand each of the three cases within the while loop’s body
3. To understand the overall goal of the while loop in lines 1-15.
To determine what violations of the red
introduced in RB
black properties are
Insert when node
is inserted and colored
RB trees – Insertion - Fixup
2. To understand each of the three cases within the while loop’s body.
• We actually need to consider six cases in the while loop, but three of them
are symmetric to the other three.
• Line2:Threecasesiftheparentofzisaleft(right)childofthegrandparentofz.
• The grand parent of z exists.
• If the parent of z is the root (i.e., the grand parent will not exist), then the parent of z is black, but notice that we enter a loop iteration only if the parent of z is red, then we know that the parent of z cannot be the root. Hence, the grand parent of z exists.
RB-Insert-Fixup (T, z)
while color[p[z]] = RED do if p[z] = left[p[p[z]]]
..................... 20
RB trees – Insertion - Fixup
2. To understand each of the three cases within the while loop’s body. • In all three cases, the grand-parent of z is black.
• Since the parent of z is red (line 1), and property 4 is violated only between z and its parent (p[z]).
• We distinguish case 1 from cases 2 and 3 by the color of z’s parent’s sibling, or “uncle”.
• Line3: Makes y point to z’s uncle.
• Line4:Testy’scolor.Ifyisred,thenweexecutecase1.Otherwise,control passes to cases 2 and 3.
RB-Insert-Fixup (T, z)
1. 2. 3. 4.
while color[p[z]] = RED do if p[z] = left[p[p[z]]]
then y ¬ right[p[p[z]]] if color[y] = RED
Insertion – Case1 – Uncle y is red
z is a right child here. Similar steps if z is a
b g leftchild.
• p[p[z]] (z’s grandparent) must be black, since z and p[z] are both red and
• 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. 22
• The next iteration has p[p[z]] as the new z (i.e., z moves up 2 levels).
there are no other violations of property 4.
Case2 – y is black, z is a right child
(new) p[z] y BD
δ λ (new)z A
left child, and both z and p[z] are red. • Takes us immediately to case 3.
g δ λ • Left rotate around p[z], p[z] and z switch roles Þ now z is a
Case3 – y is black, z is a left child
• Make p[z] black and p[p[z]] red.
• Then right rotate 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.
RB trees – Insertion - Fixup
3. To understand the overall goal of the while loop in lines 1-15.
To determine what violations of the red
black properties are
introduced in RB
Insert when node
is inserted and colored
To understand each of the three cases within the while
loop’s body
RB trees – Insertion - Fixup
3. To understand the overall goal of the while loop in lines 1-15. • The loop maintains the following invariant at the start of each iteration
If the tree violates any of the red-black properties, then: • Theviolationiseitherproperty2orproperty4.
• Itviolatesatmostoneofthem.
Recall that we need to show that a loop invariant is true prior to the first iteration of the loop, that each iteration maintains the loop invariant, and that the loop invariant gives us a useful property at loop termination.
RB trees – Insertion - Fixup
3. To understand the overall goal of the while loop in lines 1-15.
• Initialization: Prior to the first iteration of the loop, we started with a red-black tree with no violations, and we added a red node z.
If the tree violates any of the red-black properties, then the violation is at most one of property 2 or property 4:
Ifproperty2isviolated:zmustbetheredroot.Bothchildrenofzaresentinels,whichare black. Then, the tree does not also violate property 4.
Ifproperty4isviolated:zanditsparentmustbered.Giventhatbothchildrenofzare sentinels, which are black and that the tree had no other violations prior to z being added, the parent of z can not be the root. Then, the tree does not also violate property 2.
RB trees – Insertion - Fixup
3. To understand the overall goal of the while loop in lines 1-15. • Maintenance: Case 1: z’s uncle y is red.
If the tree violates any of the red-black properties, then the violation is at most one of property 2 or property 4:
Case1maintainsproperty5,anditdoesnotintroduceaviolationofproperties1or3.
Ifthenewnodez(i.e.,thegrandparentofthecurrentz)istherootatthestartofthe next iteration, then case 1 corrected the lone violation of property 4. since the new node z is red and it is the root, property 2 becomes the only one that is violated.
Ifthenewnodez(i.e.,thegrandparentofthecurrentz)isnottherootatthestartofthe next iteration, then case 1 has not created a violation of property 2. The only possible violation in the next iteration will be to property 4.
RB trees – Insertion - Fixup
3. To understand the overall goal of the while loop in lines 1-15. • Maintenance: Case 2 and 3: z’s uncle y is black.
If the tree violates any of the red-black properties, then the violation is at
most one of property 2 or property 4:
• Case2and3maintainproperties1,3and5.
• zisnottherootincases2and3,thenthereisnoviolationofproperty2.
• Cases2and3correcttheloneviolationofproperty4,andtheydonotintroduce another violation.
RB trees – Insertion - Fixup
3. To understand the overall goal of the while loop in lines 1-15.
• Termination: When the loop terminates, it does so because p[z] is black. Thus, the tree does not violate property 4 at loop termination. By the loop invariant, the only property that might fail to hold is property 2. Line 17 restores this property.
RB-Insert-Fixup(T, z) (Contd.) 1. while color[p[z]] = RED 2. do if p[z] = left[p[p[z]]] 3. .....................
15. else (if p[z] = right[p[p[z]]])(same as 10-14 16. with “right” and “left” exchanged) 17. color[root[T ]] ¬ BLACK
Insert RB tree - Example
Comp 251(c) 2022
Insert RB tree - Example
15 Nil Nil
Insert(T,15)
Comp 251(c) 2022
Insert RB tree - Example
Case 1 – uncle y is red
11 Nil 15 z
Comp 251(c) 2022
Insert RB tree - Example
15 Nil Nil
Recolor 10, 8 &11
Comp 251(c) 2022
Insert RB tree - Example
Case 2 – y is black,
z is a left child.
Notice that we are in
line 15 (if p[z] = right[p[p[z]]]).
15 Nil Nil
Comp 251(c) 2022
Insert RB tree - Example
15 Nil Nil
Right rotate at 18 p[z]
Comp 251(c) 2022
Insert RB tree - Example
Parent & child with conflict are now aligned with the root.
Comp 251(c) 2022
Insert RB tree - Example
Case 3 – y is black,
z is a right child.
Notice that we are in
line 15 (if p[z] = right[p[p[z]]]).
Parent & child with conflict are now aligned with the root.
Comp 251(c) 2022
Insert RB tree - Example
Left rotate at 7 p[p[z]]
Comp 251(c) 2022
Insert RB tree - Example
Nil Nil Nil
Comp 251(c) 2022
Insert RB tree - Example
8 11 Nil Nil
Recolor 10 p[z] & 7 p[p[z]] (root must be black!)
Comp 251(c) 2022
Insert RB tree - Complexity
• 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.
• The while loop repeats only if case 1 occurs.
• 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.
• Since the while loop terminates if case 2 or case 3 is executed.
Comp 251(c) 2022
AVL vs Red-
• AVL trees are more strictly balanced ⇒ faster search
• Red 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
Comp 251(c) 2022
Further readings
[CLRS2009] Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms. (available as E-book)
See Chapter 13 for the complete proofs & deletion
Comp 251(c) 2022
• Introduction. • Operations.
Outline – Course so far
First 7 lectures Next 8 lectures
Modified image initially taken from Programmer Humor
Algorithmic Paradigms
• General approaches to the construction of efficient solutions to problems.
• Such methods are of interest because:
• They provide templates suited to solving a broad range of diverse
• They can be translated into common control and data structures provided by most high-level languages.
• The temporal and spatial requirements of the algorithms which result can be precisely analyzed.
• Although more than one technique may be applicable to a specific problem, it is often the case that an algorithm constructed by one approach is clearly superior to equivalent solutions built using alternative techniques.
Algorithmic Paradigms
• Complete Search.
• Divide and Conquer.
• Dynamic Programming. • Greedy
• Conclusions
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com