Red-Black Trees: Properties, Implications, and Methods
Red Black Tree Essentials
Notes from “Introduction to
Algorithms”, Cormen et al.
Definition
Red Black Trees
A red-black tree is a binary search tree with an extra bit of
storage per node.
The extra bit represents the color of the node. It's either red
or black.
Each node contains the fields: color, key, left, right, and p. Any
nil pointers are regarded as pointers to external nodes (leaves)
and key bearing
nodes are considered as internal nodes of the tree.
See the video at:
http://www.youtube.com/watch?v=vDHFF4wjWYU
Properties
Red-black tree properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (nil) is black.
4. If a node is red then both of its children are
black.
5. For each node, all paths from the node to
descendant leaves contain the
same number of black nodes.
Implications
•
From these properties, it can be shown
(with a proof by induction) that the tree has a
height no more than 2 * Lg(n + 1).
•
Thus, worst case lookUp, insert, delete are all
Θ(Log n).
Three essential methods
•
Rotation
•
Insertion
•
Insert-fixUp
LeftRotate(T,x)
pre: right[x] != nil[T]
pre: root's parent is nill[T]
Left-Rotate(T,x)
y = right[x]
right[x] = left[y]
p[left[y]] = x
p[y] = p[x]
if p[x] == nil[T] then root[T] = y
else
if x == left[p[x]] then left[p[x]] = y
else
right[p[x]] = y
left[y] = x
p[x] = y
Red Black Insert
RB-Insert(T,z)
y = nil[T]
x = root[T]
while x != nil[T]
y = x
if key[z] < key[x] then
x = left[x]
else
x = right[x]
p[z] = y
if y = nil[T]
root[T] = z
else
if key[z] < key[y] then
left[y] = z
else
right[y] = z
left[z] = nil[T]
right[z] = nil[T]
color[z] = RED
RB-Insert-fixup(T,z)
RB-Insert-fixup(T,z)
RB-Insert-fixup(T,z) { while(z's parent is Red) {set y to be z's uncle
if uncle y is Red {color parent and uncle black
color grandparent red
set z to grandparent
}
else { // the uncle is black if (zig zag) { // make it a zig zigset z to parent
rotate to zig zig
}
// rotate the zig zig and finish
color parent of z black
color grandparent of z red
rotate grand parent of z
}
} // end while
color root black
}
Problem
•
Insert the following numbers (one by one) into
a Red Black Tree. Draw the tree after each
insertion. Place an ‘R’ or circle red nodes.
•
1,2,3,4,10,14,7,6,12
Answer
•
Here is the final tree.
4
/ \
2R 10R
/ \ / \
1 3 7 14
/ /
6R 12R
Red-Black Trees are binary search trees with specific properties and color coding that facilitate efficient lookup, insert, and delete operations due to their balanced nature. The properties, implications, and essential methods like rotation and insertion-fixup make them a crucial data structure in computer science.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Red Black Tree Essentials Notes from Introduction to Algorithms , Cormen et al.
Definition Red Black Trees A red-black tree is a binary search tree with an extra bit of storage per node. The extra bit represents the color of the node. It's either red or black. Each node contains the fields: color, key, left, right, and p. Any nil pointers are regarded as pointers to external nodes (leaves) and key bearing nodes are considered as internal nodes of the tree. See the video at: http://www.youtube.com/watch?v=vDHFF4wjWYU
Properties Red-black tree properties: 1. Every node is either red or black. 2. The root is black. 3. Every leaf (nil) is black. 4. If a node is red then both of its children are black. 5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.
Implications From these properties, it can be shown (with a proof by induction) that the tree has a height no more than 2 * Lg(n + 1). Thus, worst case lookUp, insert, delete are all (Log n).
Three essential methods Rotation Insertion Insert-fixUp
LeftRotate(T,x) pre: right[x] != nil[T] pre: root's parent is nill[T] Left-Rotate(T,x) y = right[x] right[x] = left[y] p[left[y]] = x p[y] = p[x] if p[x] == nil[T] then root[T] = y else if x == left[p[x]] then left[p[x]] = y else right[p[x]] = y left[y] = x p[x] = y
Red Black Insert RB-Insert(T,z) y = nil[T] x = root[T] while x != nil[T] y = x if key[z] < key[x] then x = left[x] else x = right[x] p[z] = y if y = nil[T] root[T] = z else if key[z] < key[y] then left[y] = z else right[y] = z left[z] = nil[T] right[z] = nil[T] color[z] = RED RB-Insert-fixup(T,z)
RB-Insert-fixup(T,z) RB-Insert-fixup(T,z) { while(z's parent is Red) { set y to be z's uncle if uncle y is Red { color parent and uncle black color grandparent red set z to grandparent } else { // the uncle is black if (zig zag) { // make it a zig zig set z to parent rotate to zig zig } // rotate the zig zig and finish color parent of z black color grandparent of z red rotate grand parent of z } } // end while color root black }
Problem Insert the following numbers (one by one) into a Red Black Tree. Draw the tree after each insertion. Place an R or circle red nodes. 1,2,3,4,10,14,7,6,12
Answer Here is the final tree. 4 / \ 2R 10R / \ / \ 1 3 7 14 / / 6R 12R
