Scribd
Upload
39 views4 pages

11 Red Black Trees: 11.1 Preliminaries

This document summarizes key aspects of red-black trees, including: 1) Red-black trees are binary search trees that guarantee search, insertion, and deletion operations take O(log n) time. 2) They satisfy properties such as every node being red or black, leaves being black, and all paths to leaves containing the same number of black nodes. 3) Rotations are a fundamental operation used to maintain the red-black properties during insertions and deletions. 4) The RB_INSERT algorithm handles insertion by recoloring nodes and performing rotations to fix violations of red-black properties introduced by inserting a new node. It considers three cases to address different violation scenarios.

Uploaded by

anubhav41
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
39 views4 pages

11 Red Black Trees: 11.1 Preliminaries

This document summarizes key aspects of red-black trees, including: 1) Red-black trees are binary search trees that guarantee search, insertion, and deletion operations take O(log n) time. 2) They satisfy properties such as every node being red or black, leaves being black, and all paths to leaves containing the same number of black nodes. 3) Rotations are a fundamental operation used to maintain the red-black properties during insertions and deletions. 4) The RB_INSERT algorithm handles insertion by recoloring nodes and performing rotations to fix violations of red-black properties introduced by inserting a new node. It considers three cases to address different violation scenarios.

Uploaded by

anubhav41
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

11 Red black trees

11.1 Preliminaries

A BST that guarantees that


 

Definition: A BST is a red-black tree if it satisfies the following properties.

 Every node is either red or black.

 Every leaf (external node) is black.

 If a node is red, then both of its children are black.

 Every path from a node to a descendant external node contains the same number of black
nodes.

Notation:   is the black height of a node  = number of black nodes on any path from (but not

including) to an external node.
Example: Fig 13.1

Lemma 3 A red black tree with


internal nodes has height at most   
  .
Proof

1. ST subtree at node
 contains at least !#"%$&  internal nodes.

By induction on height of the subtree rooted at :



(')*,+.- leaf
-  /0+1- 2/& 30+ internal nodes.

39
Consider an internal node
 (with black height   ). Its children have height   &  or
  . Assume   &  to be conservative.

From the induction hypothesis, the number of nodes in the subtree rooted at is
    #"%$5476 &
89:;  !<"%$ &  .
2. let be the height of the tree.
 =>>'?A@CB 
D@  %EGF & 
- IH   
7 J

11.2 Rotations

This is a fundamental operation used to maintain the red black property during insertion/deletion.
Look at Figs 13.2 and 13.3 very carefully.

40
11.3 RB INSERT(KMLN )

TREE INSERT(T,x)
 O red
color( )

while ( is not the root and P
 is red) do
if (P
*.QR8ST') P  P ?U )
V W ’s uncle
if (color(V ) == red)
Case 1.
else
if (x == right(p(x))
Case 2
Case 3
else
three symmetric cases.
endwhile
color(root) O black
Note: the cases are not mutually exclusive. Look at Fig 13.4 very carefully to understand the three
cases.
Case 1: Preconditions

1. P  is red.
2. P P
 ? must be black (why?)
3. V  P  P U ’s other child is red.
Case 1: Steps

1. Make P  and V black.


2. Make P P
 ? red.
3. set
X P  P U

41
Case 2: Preconditions

1. P   is red.
2. V , P P
 ? are black.

3. is right child of P

4. P  is left child of P  P 
Case 2: Steps

1. Set
Y P   ..
2. Do a LEFT ROTATE( )

3. So what does this do? Ans:
 becomes left child of P  and P  becomes a left child of
P  P ? .
Case 3: Preconditions

1. V is black

2.
 is P  ’s left child.
3. P
 is P  P ? ’s left child.
Case 3: Steps

1. Make P  black.


2. Make P P
  red.
3. RIGHT ROTATE( P  P U )

11.4 RB DELETE
 skip

42

You might also like