Topic 5-2 Balanced BST
Data Structures
Copyright By PowCoder代写 加微信 powcoder
Today’s Goal
Definition
Properties
Implementation
How to maintain balance after insertion/deletion
What is a Red-Black tree
A red-black tree is a binary search tree in which each node is colored either red or black.
It satisfies the following 5 properties:
Every node is either red or black.
The root is black.
Every leaf(NIL) is black.
If a node is red, then both its children are black. -> No two consecutive nodes are red.
For each node x, all simple paths from the node to descendant leaves contain the same number of black nodes. -> black-height(x).
5)-> Height Invariant The number of black nodes on every path from the root to each leaf is the same. We call this the black height of the tree
Valid vs. Invalid R-B Tree
Every node is either red or black.
The root is black.
Every leaf is black.
—————————
If a node is red, then both its children are black.
For each node, all paths from the node to descendant leaves contain the same number of black nodes.
Black-Height of the tree (the root) = 2
Black-Height of node “X” = 1
(not including the node itself)
Valid vs. Invalid R-B Tree
If a node is red, then both its children are black.
For each node, all paths from the node to descendant leaves contain the same number of black nodes.
Violate rule 4
Violate rule 5
Violate rule 5
Violate rule 5
1->2->NULL
1->3->..NULL
1->2->NULL
Every node is either red or black.
The root is black.
Every leaf is black.
Red- : Property 1
The path from any node to the farthest leaf is no more than twice as long as the path from the node to the nearest leaf.
-> The result is that the tree is roughly height-balanced.
This allows for significant differences in height between the left subtree and the right subtree
at any given vertex. For example, the left subtree might consist entirely of Black vertices and
have height x, while the right subtree might consist of alternating levels of Red and Black
vertices and have height 2*x.
The path from any node to the farthest leaf is no more than twice as long as the path from the node to the nearest leaf
Let v be any internal node,
let the longest path from v down to a leaf have length k,
let be b the number of Black nodes in this path.
In this path, every Red node must have a Black child (rule 4), so the number of Red vertices must be <= , thus b >=
Now consider the shortest path from v down to a leaf.
Let the length of this path be k’.
Since all paths from v down to a leaf must contain the same number of Black vertices (Rule 5), we know k’>=b
Putting these together gives:
Height of a red-black tree
A red-black tree with n nodes has height:
h <= 2 log2(n + 1)
How can we proof it?
N = 10 (values)
H = 4 (including NIL)
Property 2
Height of a red-black tree: Proof
Idea: Merge red nodes into their black parents.
This process produces a tree in which each node has 2, 3, or 4 children.
The 2-3-4 tree has uniform depth h of leaves
We have h’ h/2, since at most half the leaves on any path are red.
The number of leaves in each tree is n + 1
n + 1 2h’
log2(n + 1) h’ h/2
h 2 log(n + 1)
A red-black tree with n nodes has height:
h 2 log2(n + 1)
A tree in which each node has 2, 3, or 4 children. The 2-3-4 tree has uniform depth h of leaves
All leaves are at the same depth
Insert/Delete in Red-
The operations INSERT and DELETE cause modifications to the red-black tree.
color changes,
restructuring the links of the tree via “rotations”.
Right and Left Rotations
Rotations maintain the ordering of keys:
• a ∈ α, b ∈ β, c ∈ γ ⇒ a ≤ A ≤ b ≤ B ≤ c.
A rotation can be performed in O(1) time.
Insertion a new item into a red-black tree
1) Insert x in tree. Color x red.
2) Only red-black property 4 might be violated.
3) Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring.
Why only property 4 might be violated?
Insert x =15
Every node is either red or black.
The root is black.
Every leaf(NIL) is black.
No two consecutive nodes are red.
For each node x, all simple paths from the node to descendant leaves contain the same number of black nodes.
Step 2: Recolor, moving the violation up the tree
Idea: Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring.
Step 1: Insert x =15
Insertion Sample (cont.)
Step 1: Insert x =15
Right rotate(10)
Step 2: Recolor, moving the violation up the tree
Insertion Sample (cont.)
Right rotate(10)
Left-rotate(7) and recolor.
Insertion Sample (cont.)
Left-rotate(7) and recolor.
Idea of insertion:
1) Insert x in tree. Color it as red.
2) Only red-black property 4 might be violated.
3) Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring.
1.How to find the right node to perform rotations and recoloring?
2. Should I do rotation?/recolor?/both?
The Aunt/Uncle Node is RED
x(i.e., B):
current node you are targeting.
y(i.e., D):
the Aunt/Uncle node of x
Grandparent
A subtree with a black root.
All have the same black-height.
C-> leaf nodes should have same number of black nodes
The Aunt/Uncle Node is RED
x(i.e., B): the node you have inserted.
Y(i.e., D): the Aunt/Uncle node of x
Grandparent
Action: Recolor
Deal with Case 1:
Don’t change the structure.
Simply recolour the grandparent, the parent and the aunt/uncle
Case 2: The Aunt/Uncle Node is Black
Action: Right-rotate c,
Done! No more violations of RB property 4 are possible.
Deal with Case 2:
Right/left rotate the grandparent node
Recolor parent(B), grandparent node(C).
x and x’s parent: same side
Case 3: The Aunt/Uncle Node is Black
x(i.e., B): the node you have inserted.
Y(i.e., D): the Aunt/Uncle node of x
Action: Left-rotate A
Deal with Case 3:
Left rotate the parent node if current node is the right child.
-> Transfer to Case 2.
This is Case 2
X and parent on different side
X and parent on same side
R-B tree: Insertion Time Complexity
Case 1, only recolors nodes.
If Case 2 or Case 3 occurs, perform 1 or 2 rotations, and terminate.
Running time: O(log n) insert with O(1) (rotations + recolors).
Revisit the given sample
Action: Recolor
Focus: 10-18-7-3(uncle/aunt)
Right rotate the parent node if current node is the left child.
-> Transfer to Case 2.
Revisit the given sample
Action: Recolor
Action: Right rotate (parent node) 18
Revisit the given sample
Action: Recolor
Action: Right rotate 18
Action: Left rotate (grandparent node) 7
General Insertion Algorithm
If current and parent are both red:
if Grandparent’s other child (aunt/uncle node) is red:
Color Grandparent Red
else if the Current and the Parent are both on the same side:
Do a single rotation and recolor
Do a double rotation (rotate 2 times) and recolor
Same side: current is the right/left child of the parent node
->the parent node is the right/left child of the grandparent node
def RB_insert(T, x):
T.root = rec_RB_insert(T.root,x)
T.root.color = Black
def rec_RB_insert(v,x):
if (v.is_a_leaf):
return new RB_Node(x)
else if (v.value > x):
v.left_child = rec_RB_insert(v.left_child,value)
if (v.left_child.colour == Black):
if (v.left_child.left_child.colour == Red) ||(v.left_child.right_child.colour == Red):
//now we have a problem and need to identify the cause
if (v.left_child.left_child.colour == Red):
return Left_Left_fix(v)
return Left_Right_fix(v)
Code: view from Grandparent node
# always have black root
Insert node recursively
If the root of subtree is black, no problem, otherwise, further check potential problems, why?
Fix v: Case 1,2,3
handling v.value < x,
Do the mirror image of the operations above, replacing v.left_child with v.right_child
We only need to look at the left child, as we insert at left.
Left_Left_fix(v): Practice
def Left_Left_fix(GP):
P = GP.left_child
S = GP.right_child (S is the aunt/uncle node)
GP's left child is Red, and that child's left child is also Red
Left_Left_fix(v): view from Grandparent node
def Left_Left_fix(GP):
P = GP.left_child
S = GP.right_child (S is the aunt/uncle node)
if S.colour == Red:
P.colour = .colour = P.colour = Red
GP.left_child = P.right_child
P.right_child = GP
// fix the colours
P.colour = P.colour = Red
GP's left child is Red, and that child's left child is also Red
Case 1: only recolor
Left_Left_fix(v): view from Grandparent node
def Left_Left_fix(GP):
P = GP.left_child
S = GP.right_child
if S.colour == Red:
P.colour = .colour = P.colour = Red
GP.left_child = P.right_child
P.right_child = GP
// fix the colours
P.colour = P.colour = Red
GP's left child is Red, and that child's left child is also Red
Case 2: Single rotate and recolor
new root of this subtree
GP.left_child = P.right_child
Left_Right_fix(v): view from Grandparent node
def Left_Right_fix(GP):
P = GP.left_child
S = GP.right_child
if S.colour == Red:
P.colour = .colour = P.colour = Red
C = P.right_child
P.right_child = C.left_child
GP.left_child = C.right_child
C.left_child = P
C.right_child = GP
// fix the colours
C.colour = P.colour = Red
// return the new root of this subtree
GP's left child is Red, and that child's right child is Red
Case 1: only recolor
Left_Right_fix(v): view from Grandparent node
def Left_Right_fix(GP):
P = GP.left_child
S = GP.right_child
if S.colour == Red:
P.colour = .colour = P.colour = Red
C = P.right_child
P.right_child = C.left_child
C.left_child = P
GP.left_child = C.right_child
C.right_child = GP
// fix the colours
C.colour = P.colour = Red
// return the new root of this subtree
GP's left child is Red, and that child's right child is Red
Case 3: Double rotate and recolor
Case 1: only recolor
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com