Red-black Trees Advanced)

Red-Black Trees

Presentation by Aasim Ali (04-9174)

Red-Black Trees • Definition: A Red-Black Tree (shortened as RB Tree or RBT) is a Binary Search Tree (BST) where: 1. 2. 3. 4. 5.

Every node is either RED or BLACK. The root is BLACK Every leaf (sentinel node) is BLACK. If a node is RED, then both of its children are BLACK. For each node, all paths from the node to descendant leaves contain the same number of BLACK nodes.

• Definition: The BLACK-height of a node, x, in a Red-Black Tree is the number of BLACK nodes on any path from x to any leaf (sentinel node), not counting x. • Definition: The BLACK-height of a Red-Black Tree is the BLACK-height of Root node.

A few RBT visual examples r x y z A valid Red-Black Tree Black-Height of: r=2 x=2 y=1 z=1

Black-Height of tree = 2 (since r is the root)

A few RBT visual examples

x y z A valid Red-Black Tree of Black-Height 3 Black-Height of: x=2

y=1

z=1

Contd.

A few RBT visual examples

x y z A valid Red-Black Tree of Black-Height 3 Black-Height of: x=3

y=2

z=1

Contd.

A few RBT visual examples

Contd.

ot

re n a s ode e n f l lea at sam l a ce to be t n e H ired igh e u h q re ry) a n i (ord

It is also a valid Red-Black Tree, because:  No RED Child has RED parent 

Black-Height from any node to all its successor leaf nodes is same

Theorems Related to RB Trees

Theorem 1: Any Red-Black Tree with root x has at least n = 2bh(x) – 1 internal nodes where bh(x) is the black height of node x. Proof: By induction: when h(x) = 0: 2bh(x) – 1 = 20 – 1 = 1 – 1 = 0 when h(x) > 0: (2bh(x)-1 – 1) + (2bh(x)-1 – 1) + 1 = 2bh(x) – 1

Theorems Related to RB Trees

Contd.

Theorem 2: In a red-black tree, at least half the nodes on any path from the root to a leaf must be black. Proof: If there is a red node on the path then there must be a corresponding black node.

Theorems Related to RB Trees

Contd.

Theorem 3: In a red-black tree, no path from any node, x, to a leaf is more than twice as long as any other path from x to any other leaf. Proof: • Every path from a node to any leaf contains the same number of black nodes [definition] • At least ½ the nodes on any such path are black [Theorem 2] • Therefore, there can be no more than twice as many nodes on any path from x to a leaf as on any other path. • Hence, the length of every path is no more than twice in length of any other path from x to any other leaf

Theorems Related to RB Trees

Contd.

Theorem 4: A red-black tree with n internal nodes has height h <= 2 lg(n + 1). Proof: Let h be the height of the red-black tree with rooted at x. bh(x) >= h/2 n >= 2bh(x) – 1 Therefore n >= 2 h/2 – 1 n + 1 >= 2h/2 lg(n + 1) >= h/2 2 lg(n + 1) >= h

[Theorem 2] [Theorem 1]

Operations on Red-Black Tree Search Insertion Deletion

Search

•

Search works exactly as in ordinary Binary Search Tree (BST)

•

Since h <= 2 lg (n + 1) hence search takes O (lg n) even in worst case (where h is height of the tree, and n is total number of nodes)

Mechanism for Insertion and Deletion •

Basic mechanism for Insertion & Deletion: same as in BST

•

Ensuring the validity of Red Black (RB) Properties may require certain adjustments for fixing of any violations

•

Fixing adjustments include: – Change of colors – Rotations: Left rotation and Right rotation

•

Two approaches are used for fixing: – Top-Down: Adjustments during the pre-insert/pre-delete downward traversal (while moving from the root towards insertion/deletion point) – Bottom-Up: Post-insert/post-delete adjustments during the upward traversal (while moving from the point of insertion/deletion towards root)

Only Bottom-Up cases are discussed further in this presentation

Possible Rotations in Red Black Fixing Types of Rotations: (a) Left Rotation, (b) Right Rotation Rotation is O(1) operation: simply requires update of fixed number of pointers

Left Rotation: Rotate R around P G

Right Rotation: Rotate L around P

P

L

P

P

L L

G

G

RL

R L R

L

L

R

R

R

L

L

R

L

L

R

R

R

Original Structure

L

L

R R

L

L

R

R

R

Red-Black Trees Bottom-Up Insertion

Bottom–Up Insertion • • •

Insert node as in BST Color the Node RED Two Red-Black properties may be violated? 1. 2. 3. 4. 5.

Every node is Red or Black Root is Black Sentinel nodes are Black If node is Red, both children must be Black Every path from node to descendant leaf must contain the same number of Blacks

Cases of Bottom-Up Insertion • Insert node; Color it RED; X is pointer to it • Cases 0: X is the root (Possibility: inserting 1st node, propagated effect of fixing) 1: Both parent and uncle are RED (Only this case may need recursive fixing) Two further cases when Parent is RED, and uncle is BLACK: 2: (zig-zag) –X and its parent are opposite type (left/right) children 3: (zig-zig) –X and its parent are both left or both right children

Terminology for Insertion • The node causing violation is pointed to by X (being the new node in the start of Insertion Fixing) • The parent of X is P • The uncle of X is U • The grandparent of X is G • The Sibling of X is S

Red Node

Black Node

Sentinel Node

Bottom-Up Insertion Case 0

X

X

Case 0 – X is root (Trivial case)  Just change the color of X to Black (This is the only case that increases Black-Height of the tree)

Bottom-Up Insertion Case 1

X

Case 1 – Both P and U are RED Just Recolor and move up:

G

 Color parent and uncle BLACK  Color grandparent RED

P

U

 Point X to grandparent  Check for violation in new situation (it may invoke any of four cases)

X and P can be either child; it does not affect the strategy

X

Bottom-Up Insertion Case 2 Case 2 – Zig-Zag: P is RED; U is BLACK; P & X are opposite children Double Rotate & Recolor:  Left rotate X around P  Right rotate X around G  Swap colors of G and X

X

G P is left

S

U X isright

This simulation shows Case 2 when X is right child and P is left child Symmetric handling is needed when X is left child and P is right child

Bottom-Up Insertion Case 3 Case 3 – Zig-Zig : P is RED; U is BLACK; P & X are same direction children

G

Single Rotate and Recolor:  Right rotate P around G  Swap colors of P and G

X

U

P S

This simulation shows Case 3 when X and P both are left children Symmetric handling is needed when X and P both are right children

Asymptotic Cost of Insertion • O(lg n) to descend to insertion point • O(1) to do insertion • O(lg n) to ascend and readjust == worst case only for insert-fix case 1 • Total: O(log n)

Examples of Insertion Let’s Insert:

80

96, 97, 99

60

88 75

45 18 10 25 50

55

5

70

84 77

82

95 86

92

65 72

97 98 96 98 96 97

15 20 30 Insert 96 as No Needs fixing fixing needed Insert 97 RED: as RED: case 2 (zig-zag)

Contd.

Examples of Insertion Let’s Insert:

80

96, 97, 99

60

88 75

45 18 10 25 50

55

5

15 20 30

70 65 72

84 77

82

95 86

97

92 96

Case 1

98 Case 1

Insert 99 as RED: Needs fixing

99

Contd.

Examples of Insertion Let’s Insert: 3, 56, 57

80 60

18

75

45 45 55

18 Case 3 (zig-zig)

88

10 25 50

65 77

84 82

95 86

92

97 96

99

5 15 20 30 3

Case 1

98

Insert 3 as RED: Needs fixing

Contd.

Examples of Insertion Let’s Insert: 3, 56, 57

80

Case 0

60 18 10 5

88 75

Case 1

45

65 77 55

15 25 50

3 20 30

84

Case 1

82

95 86

92

97 96

56 57

98 99

Case 1

Insert 5657 as as RED: NoNeeds fixingfixing needed Insert RED:

Red-Black Trees Bottom-Up Deletion (starting with BST delete)

Ordinary BST Delete 1.

Leaf: just delete it.

3.

Has just one child: replace it with that child

5.

Has two children then Delete-by-Copy: copy the value of in-order predecessor in the node (selected for deletion) then delete the in-order predecessor (bringing it to case 1 or 2 above)

Terminology for Deletion • • • • •

U was physically deleted Black node V takes U’s place, thus has an extra unit of blackness P is the parent of V S is the sibling of V + indicates extra blackness: P+ means P with extra blackness • Sentinel nodes are not shown Black Node

Red or Black, and don’t care

Red Node

Sentinel Node

RB Properties Verification Let’s analyze the effect of simple BST Delete on RBT Properties 3.

If U is RED? Not a problem – no RB properties violated

5.

If U is BLACK? (a) U is not root: black-height of some paths needs fixing (b) U is root: even then some verification is needed Sibling of a non-root BLACK node is guaranteed to exist

Cases of Bottom-Up Deletion • Cases (caused by deletion of a BLACK node) 1: Sibling of deleted node is RED (which implies: the Sibling has at least one BLACK child, and the parent of deleted node is BLACK) Three more cases when Sibling is BLACK 2: Both children (internal or external) of Sibling are BLACK 3: Deleted node is Left child and only the left child of Sibling is RED 4: Deleted node is Left child and at least right child of Sibling is RED If Deleted node is Right child then symmetric strategy for 3 and 4 is used.

Fixing the problem • Think of V as having an “extra” unit of BLACKNESS: – It may be absorbed into the tree (by a RED node), or – It may propagated up to the root and out of the tree

• There are four cases if V is a left child; and four symmetric cases if V is a right child • V as left child is illustrated in the following slides

Bottom-Up Deletion Case 1 • V’s sibling, S, is Red – Rotate S around P and recolor S & P

• NOT a terminal case – One of the other cases will now apply • All other cases apply when S is Black

P U V

S

Case 1 Diagram P V+

P

Rotate

V+

S

S P V+

Recolor

S

Bottom-Up Deletion Case 2 • V’s sibling, S, is black and has two black children – Recolor S to be Red – P absorbs V’s extra blackness • If P is Red, we’re done • If P is Black, it now has extra blackness and problem has been propagated up the tree

P U V

S

Case 2 diagram

P V+

Recolor and absorb

S

V

Either extra black absorbed by P or P now has extra blackness

P+ S

Bottom-Up Deletion Case 3

}

• S is Black, S’s right child is Black and S’s left child is Red

– Rotate S’s left child around S – Swap color of S and S’s left child – Now in case 4

P U

V

S

Case 3 Diagrams P V+

P

S V+

P Rotate

V+

S S Recolor

Bottom-Up Deletion • S is black, S’s RIGHT child is RED (Left child either color)

Case 4

}

– Rotate S around P – Swap colors of S and P, and color S’s Right child Black

P

• This is the terminal case It does not cause recursive call

U V

S

Case 4 diagrams P

P

Rotate

V+

S

V+

S P V

Recolor

S

Asymptotic Cost of Deletion • O(lg n) to descend to deletion point • O(1) to do deletion • O(lg n) to ascend and readjust == worst case only for delete-fixing case 1 • Total: O(log n)

Examples of Deletion Let’s Delete:

80

20, 25, 30

60

88 75

45 18 30 50 10 25

55

5

70

84 77

82

95 86

92

97

65 72

15 20 30 20 (RED): No fixing needed Delete 25 30 (BLACK): Needs trivial Delete (BLACK): Fixing Casefixing 4 Extra blackness U=25 is be absorbed by by V=30 Extra blackness of of U=30 will absorbed P=18

References • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 2nd Ed. May 2001. May 2001.

• The following URL has a tutorial on Red-Black Trees [Julienne Walker and The EC Team]: Collection of Tutorials on Data Structures http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.a