  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Red Black Tree in Data Structure

Last Updated on May 5, 2023 by Prepbytes Red Black Tree is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times. Let us first define a Binary Search Tree before diving into the red black tree. A BST (Binary Search Tree) is a non-linear data structure in which the nodes in the left subtree have values less than the root node and the nodes in the right subtree have values greater than the root node. In this article, we will go through the Red Black Tree in depth.

## What is Red Black Tree in Data Structure

The red-black tree is a binary search tree in which each node is either red or black. It’s a self-balancing binary search tree. It has a low worst-case running time complexity.

### Properties of a Red Black Tree in Data Structure

The Red-Black tree satisfies all of the properties of a binary search tree, as well as the following extra properties –

1. The root is black in color.
2. External property: In the Red-Black tree, every leaf (Leaf is a NULL offspring of a node) is black.
3. Internal property: A red node’s children are black. As a result, the red node’s probable parent is a black node.
4. Depth property: The dark depth of all the leaves is the same.
5. Path property: There is the same number of black nodes on every simple path from the root to a descendant leaf node.

The red black tree must obey some rules in addition to the given set of characteristics. Let’s talk about these rule sets.

### Set of Rules for Red Black Tree in Data Structure

Every Red Black Tree must abide by the following rules:

• Every node has one of two colors: RED or BLACK.
• The tree’s root is always BLACK.
• There are no adjacent RED nodes, which means that a RED node cannot have a RED parent or a RED child.
• Every path that connects a node (including the root) to any of its descendants The number of NULL nodes is the same as the number of BLACK nodes.
• Every leaf, that is, every NULL node, must be coloured BLACK.

### Why do we need the Red Black Tree?

Most BST operations (for example, search, max, min, insert, delete, etc.) take O(h) time, where h is the height of the BST. For a skewed Binary tree, the cost of these operations may become O(n). We can guarantee an upper bound of O(log n) for all of these operations if we ensure that the height of the tree remains O(log n) after every insertion and deletion. We can guarantee that all operations require O(log n) operations since the height of a Red-Black tree is always O(log n), where n is the number of nodes in the tree.

The time complexity of each operation is shown below in tabular form:

S.No Operation Time Complexity
1 Search O(log n)
2 Insert O(log n)
3 Delete O(log n)

### AVL Tree vs Red Black Tree in Data Structure

Let’s discuss the difference between AVL tree and Red black tree in Data Structure:

What is AVL Tree in Data Structure?
The AVL Tree is a height-balanced binary search tree in which each node has a balancing factor that is derived by subtracting the height of its right subtree from the height of its left subtree.
If the balance factor of each node is between -1 and 1, the tree is said to be balanced; otherwise, the tree is imbalanced and must be balanced.

Now, let us discuss some differences between AVL Tree and Red Black Tree.

Parameter Red Black Tree AVL Tree
Searching Searching is not efficient as they are not perfectly balanced. Searching is efficient as they are perfectly balanced.
Insertion and deletion Insertion and deletion are easier in the Red Black tree as it requires fewer rotations to balance the tree. Insertion and deletion are complex in AVL tree as it requires multiple rotations to balance the tree.
Color of the Node Red or Black No color
Balance factor No balance factor Each node has a balance factor in the AVL tree whose value can be 1, 0, or -1.
Strictly balanced Not strictly balanced Strictly balanced

## Operations on a Red Black Tree in Data Structure

In a Red Black Tree, we can do certain operations, including :

1. Rotating a sub-tree
2. Insertion
3. Deletion

### Rotating a subtree in a Red Black Tree in Data Structure

The positions of a subtree’s nodes are swapped during the rotation operation. When other processes, such as insertion and deletion, violate the attributes of a red-black tree, the rotation operation is employed to restore them. Rotations are classified into two types:

• Left Rotation
In left-rotation, the arrangement of the nodes on the right is replaced by the arrangement of the nodes on the left.

• Let the first tree be: • If y has a left subtree, make x the parent of y’s left subtree. • If the parent of x is NULL, make y the tree’s root.

• Otherwise, if x is p’s left child, make y p’s left child.

• Otherwise, make y the right child of p. • Make y the parent of x. • Right Rotation
The arrangement of the nodes on the left is changed into the arrangement of the nodes on the right in right-rotation.

• Let the initial tree be: • If x has a right subtree, assign y as the parent of the right subtree of x. • If the parent of y is NULL, make x as the root of the tree.

• Else if y is the right child of its parent p, make x as the right child of p.

• Else assign x as the left child of p. • Make x as the parent of y. ### Insertion in a Red Black Tree in Data Structure

When a new node is inserted, it is always inserted as a RED node. If the tree violates the properties of the red-black tree after insertion of a new node, we do the following activities.

1. Recolor
2. Rotation

Algorithm to Insert a Node in a Red Black Tree

• Navigate the tree to determine the best location for the new node.
• Once you’ve found the right spot, insert the new node as a red node.
• If the new node’s parent is black, no additional action is required, and the tree remains a valid red-black tree.
• If the new node’s parent is red, there are three possibilities:
• Case 1: The sibling of the parent is also red. In this scenario, color the parent and its sibling black, and the parent’s parent (grandparent) red in this scenario. Then, repeat the algorithm from the grandparent to ensure that the red-black tree properties are preserved.
• Case 2: The parent’s sibling is black, the new node is its parent’s right child, and the parent is its grandparent’s left child. Perform a left rotation on the parent in this case, so that the new node becomes the parent and the parent becomes the new node’s left child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.
• Case 3: The parent’s sibling is black, the new node is the parent’s left kid, and the parent is the grandparent’s left child. In this scenario, recolor the parent black and the grandparent red, and then right rotate the grandparent such that the parent becomes the grandparent’s right child and the grandparent becomes the parent’s right child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.
• Case 4: The parent’s sibling is black, the new node is its parent’s left child, and the parent is the right child of its grandparent. In this situation, right-rotate the parent such that the new node becomes the parent and the parent becomes the new node’s right child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.
• Case 5: The parent’s sibling is black, and the new node is the parent’s right kid, and the parent is the grandparent’s right child. In this scenario, recolor the parent black and the grandparent red, and then rotate the grandparent so that the parent becomes the grandparent’s left child and the grandparent becomes the parent’s left child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.
• Continue the procedure until you reach the tree’s root, and then recolor it black to ensure it is always black.

Code Implementation

```/*package whatever //do not write package name here */

import java.io.*;

// considering that you know what are red-black trees here is the implementation in java for insertion and traversal.
// RedBlackTree class. This class contains subclass for node
// as well as all the functionalities of RedBlackTree such as - rotations, insertion and
// inoredr traversal
public class RedBlackTree
{
public Node root;//root node
public RedBlackTree()
{
super();
root = null;
}
// node creating subclass
class Node
{
int data;
Node left;
Node right;
char colour;
Node parent;

Node(int data)
{
super();
this.data = data; // only including data. not key
this.left = null; // left subtree
this.right = null; // right subtree
this.colour = 'R'; // colour . either 'R' or 'B'
this.parent = null; // required at time of rechecking.
}
}
// this function performs left rotation
Node rotateLeft(Node node)
{
Node x = node.right;
Node y = x.left;
x.left = node;
node.right = y;
node.parent = x; // parent resetting is also important.
if(y!=null)
y.parent = node;
return(x);
}
//this function performs right rotation
Node rotateRight(Node node)
{
Node x = node.left;
Node y = x.right;
x.right = node;
node.left = y;
node.parent = x;
if(y!=null)
y.parent = node;
return(x);
}

// these are some flags.
// Respective rotations are performed during traceback.
// rotations are done if flags are true.
boolean ll = false;
boolean rr = false;
boolean lr = false;
boolean rl = false;
// helper function for insertion. Actually this function performs all tasks in single pass only.
Node insertHelp(Node root, int data)
{
// f is true when RED RED conflict is there.
boolean f=false;

//recursive calls to insert at proper position according to BST properties.
if(root==null)
return(new Node(data));
else if(data<root.data)
{
root.left = insertHelp(root.left, data);
root.left.parent = root;
if(root!=this.root)
{
if(root.colour=='R' && root.left.colour=='R')
f = true;
}
}
else
{
root.right = insertHelp(root.right,data);
root.right.parent = root;
if(root!=this.root)
{
if(root.colour=='R' && root.right.colour=='R')
f = true;
}
// at the same time of insertion, we are also assigning parent nodes
// also we are checking for RED RED conflicts
}

// now lets rotate.
if(this.ll) // for left rotate.
{
root = rotateLeft(root);
root.colour = 'B';
root.left.colour = 'R';
this.ll = false;
}
else if(this.rr) // for right rotate
{
root = rotateRight(root);
root.colour = 'B';
root.right.colour = 'R';
this.rr = false;
}
else if(this.rl) // for right and then left
{
root.right = rotateRight(root.right);
root.right.parent = root;
root = rotateLeft(root);
root.colour = 'B';
root.left.colour = 'R';

this.rl = false;
}
else if(this.lr) // for left and then right.
{
root.left = rotateLeft(root.left);
root.left.parent = root;
root = rotateRight(root);
root.colour = 'B';
root.right.colour = 'R';
this.lr = false;
}
// when rotation and recolouring is done flags are reset.
// Now lets take care of RED RED conflict
if(f)
{
if(root.parent.right == root) // to check which child is the current node of its parent
{
if(root.parent.left==null || root.parent.left.colour=='B') // case when parent's sibling is black
{// perform certaing rotation and recolouring. This will be done while backtracking. Hence setting up respective flags.
if(root.left!=null && root.left.colour=='R')
this.rl = true;
else if(root.right!=null && root.right.colour=='R')
this.ll = true;
}
else // case when parent's sibling is red
{
root.parent.left.colour = 'B';
root.colour = 'B';
if(root.parent!=this.root)
root.parent.colour = 'R';
}
}
else
{
if(root.parent.right==null || root.parent.right.colour=='B')
{
if(root.left!=null && root.left.colour=='R')
this.rr = true;
else if(root.right!=null && root.right.colour=='R')
this.lr = true;
}
else
{
root.parent.right.colour = 'B';
root.colour = 'B';
if(root.parent!=this.root)
root.parent.colour = 'R';
}
}
f = false;
}
return(root);
}

// function to insert data into tree.
public void insert(int data)
{
if(this.root==null)
{
this.root = new Node(data);
this.root.colour = 'B';
}
else
this.root = insertHelp(this.root,data);
}
// helper function to print inorder traversal
void inorderTraversalHelper(Node node)
{
if(node!=null)
{
inorderTraversalHelper(node.left);
System.out.printf("%d ", node.data);
inorderTraversalHelper(node.right);
}
}
//function to print inorder traversal
public void inorderTraversal()
{
inorderTraversalHelper(this.root);
}
// helper function to print the tree.
void printTreeHelper(Node root, int space)
{
int i;
if(root != null)
{
space = space + 10;
printTreeHelper(root.right, space);
System.out.printf("\n");
for ( i = 10; i < space; i++)
{
System.out.printf(" ");
}
System.out.printf("%d", root.data);
System.out.printf("\n");
printTreeHelper(root.left, space);
}
}
// function to print the tree.
public void printTree()
{
printTreeHelper(this.root, 0);
}
public static void main(String[] args)
{
RedBlackTree t = new RedBlackTree();
int[] arr = {1,4,6,3,5,7,8,2,9};
for(int i=0;i<9;i++)
{
t.insert(arr[i]);
System.out.println();
t.inorderTraversal();
}
t.printTree();
}
}```

Output

``````1
1 4
1 4 6
1 3 4 6
1 3 4 5 6
1 3 4 5 6 7
1 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9 ``````

### Deletion in a Red Black Tree in Data Structure

• Locate the node that needs to be deleted.
• Remove the node from the tree if it has no children.
• Replace the node with that child and recolor the replacement node black if the original node was black. Remove the initial node from the tree if it is red.
• If the node has two children, replace it with its inorder successor (the node with the smallest key in the right subtree of the node), then delete the inorder successor from its original location. Because the inorder successor can only have one child, we can handle this deletion case using case 2 or 3 from the insertion algorithm.
• Find the inorder successor of the node to be deleted.
• Replace the node to be deleted with its inorder successor.
• Delete the inorder successor from its original location using cases 1, 2, or 3 from the insertion algorithm.
• Check whether any of the red-black tree attributes have been violated after deleting the node, and repair any violations using the following cases:
• If the node replaced during deletion is red, recolor it black.
• If the node replaced during deletion is black and its replacement is red, recolor the replacement black.
• If the node replaced during deletion is black and its replacement is black, then adjust the tree to restore the red-black tree properties by following one of the cases below:
• If the deleted node’s sibling is red, recolor the sibling and its parent black and red, respectively, and then rotate the parent left or right (depending on whether the sibling is a left or right child).
• If the deleted node’s sibling is black and both of its children are black, recolor the sibling red and proceed with the algorithm from the sibling’s parent.
• If the deleted node’s sibling is black, its inner child is red, and its outer child is black, rotate the sibling and its inner child, and then continue the algorithm from the original sibling.
• If the deleted node’s sibling is black and its outer child is red, recolor the sibling to match its parent, recolor the parent black, recolor the outer child black, and rotate the parent.
• Finally, recolor the root black to maintain the red-black tree properties.

Code Implementation

```#include <iostream>
#include <queue>
using namespace std;

enum COLOR { RED, BLACK };

class Node {
public:
int val;
COLOR color;
Node *left, *right, *parent;

Node(int val) : val(val) {
parent = left = right = NULL;

// Node is created during insertion
// Node is red at insertion
color = RED;
}

// returns pointer to uncle
Node *uncle() {
// If no parent or grandparent, then no uncle
if (parent == NULL or parent->parent == NULL)
return NULL;

if (parent->isOnLeft())
// uncle on right
return parent->parent->right;
else
// uncle on left
return parent->parent->left;
}

// check if node is left child of parent
bool isOnLeft() { return this == parent->left; }

// returns pointer to sibling
Node *sibling() {
// sibling null if no parent
if (parent == NULL)
return NULL;

if (isOnLeft())
return parent->right;

return parent->left;
}

// moves node down and moves given node in its place
void moveDown(Node *nParent) {
if (parent != NULL) {
if (isOnLeft()) {
parent->left = nParent;
} else {
parent->right = nParent;
}
}
nParent->parent = parent;
parent = nParent;
}

bool hasRedChild() {
return (left != NULL and left->color == RED) or
(right != NULL and right->color == RED);
}
};

class RBTree {
Node *root;

// left rotates the given node
void leftRotate(Node *x) {
// new parent will be node's right child
Node *nParent = x->right;

// update root if current node is root
if (x == root)
root = nParent;

x->moveDown(nParent);

// connect x with new parent's left element
x->right = nParent->left;
// connect new parent's left element with node
// if it is not null
if (nParent->left != NULL)
nParent->left->parent = x;

// connect new parent with x
nParent->left = x;
}

void rightRotate(Node *x) {
// new parent will be node's left child
Node *nParent = x->left;

// update root if current node is root
if (x == root)
root = nParent;

x->moveDown(nParent);

// connect x with new parent's right element
x->left = nParent->right;
// connect new parent's right element with node
// if it is not null
if (nParent->right != NULL)
nParent->right->parent = x;

// connect new parent with x
nParent->right = x;
}

void swapColors(Node *x1, Node *x2) {
COLOR temp;
temp = x1->color;
x1->color = x2->color;
x2->color = temp;
}

void swapValues(Node *u, Node *v) {
int temp;
temp = u->val;
u->val = v->val;
v->val = temp;
}

// fix red red at given node
void fixRedRed(Node *x) {
// if x is root color it black and return
if (x == root) {
x->color = BLACK;
return;
}

// initialize parent, grandparent, uncle
Node *parent = x->parent, *grandparent = parent->parent,
*uncle = x->uncle();

if (parent->color != BLACK) {
if (uncle != NULL && uncle->color == RED) {
// uncle red, perform recoloring and recurse
parent->color = BLACK;
uncle->color = BLACK;
grandparent->color = RED;
fixRedRed(grandparent);
} else {
// Else perform LR, LL, RL, RR
if (parent->isOnLeft()) {
if (x->isOnLeft()) {
// for left right
swapColors(parent, grandparent);
} else {
leftRotate(parent);
swapColors(x, grandparent);
}
// for left left and left right
rightRotate(grandparent);
} else {
if (x->isOnLeft()) {
// for right left
rightRotate(parent);
swapColors(x, grandparent);
} else {
swapColors(parent, grandparent);
}

// for right right and right left
leftRotate(grandparent);
}
}
}
}

// find node that do not have a left child
// in the subtree of the given node
Node *successor(Node *x) {
Node *temp = x;

while (temp->left != NULL)
temp = temp->left;

return temp;
}

// find node that replaces a deleted node in BST
Node *BSTreplace(Node *x) {
// when node have 2 children
if (x->left != NULL and x->right != NULL)
return successor(x->right);

// when leaf
if (x->left == NULL and x->right == NULL)
return NULL;

// when single child
if (x->left != NULL)
return x->left;
else
return x->right;
}

// deletes the given node
void deleteNode(Node *v) {
Node *u = BSTreplace(v);

// True when u and v are both black
bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK));
Node *parent = v->parent;

if (u == NULL) {
// u is NULL therefore v is leaf
if (v == root) {
// v is root, making root null
root = NULL;
} else {
if (uvBlack) {
// u and v both black
// v is leaf, fix double black at v
fixDoubleBlack(v);
} else {
// u or v is red
if (v->sibling() != NULL)
// sibling is not null, make it red"
v->sibling()->color = RED;
}

// delete v from the tree
if (v->isOnLeft()) {
parent->left = NULL;
} else {
parent->right = NULL;
}
}
delete v;
return;
}

if (v->left == NULL or v->right == NULL) {
// v has 1 child
if (v == root) {
// v is root, assign the value of u to v, and delete u
v->val = u->val;
v->left = v->right = NULL;
delete u;
} else {
// Detach v from tree and move u up
if (v->isOnLeft()) {
parent->left = u;
} else {
parent->right = u;
}
delete v;
u->parent = parent;
if (uvBlack) {
// u and v both black, fix double black at u
fixDoubleBlack(u);
} else {
// u or v red, color u black
u->color = BLACK;
}
}
return;
}

// v has 2 children, swap values with successor and recurse
swapValues(u, v);
deleteNode(u);
}

void fixDoubleBlack(Node *x) {
if (x == root)
// Reached root
return;

Node *sibling = x->sibling(), *parent = x->parent;
if (sibling == NULL) {
// No sibling, double black pushed up
fixDoubleBlack(parent);
} else {
if (sibling->color == RED) {
// Sibling red
parent->color = RED;
sibling->color = BLACK;
if (sibling->isOnLeft()) {
// left case
rightRotate(parent);
} else {
// right case
leftRotate(parent);
}
fixDoubleBlack(x);
} else {
// Sibling black
if (sibling->hasRedChild()) {
// at least 1 red children
if (sibling->left != NULL and sibling->left->color == RED) {
if (sibling->isOnLeft()) {
// left left
sibling->left->color = sibling->color;
sibling->color = parent->color;
rightRotate(parent);
} else {
// right left
sibling->left->color = parent->color;
rightRotate(sibling);
leftRotate(parent);
}
} else {
if (sibling->isOnLeft()) {
// left right
sibling->right->color = parent->color;
leftRotate(sibling);
rightRotate(parent);
} else {
// right right
sibling->right->color = sibling->color;
sibling->color = parent->color;
leftRotate(parent);
}
}
parent->color = BLACK;
} else {
// 2 black children
sibling->color = RED;
if (parent->color == BLACK)
fixDoubleBlack(parent);
else
parent->color = BLACK;
}
}
}
}

// prints level order for given node
void levelOrder(Node *x) {
if (x == NULL)
// return if node is null
return;

// queue for level order
queue<Node *> q;
Node *curr;

// push x
q.push(x);

while (!q.empty()) {
// while q is not empty
// dequeue
curr = q.front();
q.pop();

// print node value
cout << curr->val << " ";

// push children to queue
if (curr->left != NULL)
q.push(curr->left);
if (curr->right != NULL)
q.push(curr->right);
}
}

// prints inorder recursively
void inorder(Node *x) {
if (x == NULL)
return;
inorder(x->left);
cout << x->val << " ";
inorder(x->right);
}

public:
// constructor
// initialize root
RBTree() { root = NULL; }

Node *getRoot() { return root; }

// searches for given value
// if found returns the node (used for delete)
// else returns the last node while traversing (used in insert)
Node *search(int n) {
Node *temp = root;
while (temp != NULL) {
if (n < temp->val) {
if (temp->left == NULL)
break;
else
temp = temp->left;
} else if (n == temp->val) {
break;
} else {
if (temp->right == NULL)
break;
else
temp = temp->right;
}
}

return temp;
}

// inserts the given value to tree
void insert(int n) {
Node *newNode = new Node(n);
if (root == NULL) {
// when root is null
// simply insert value at root
newNode->color = BLACK;
root = newNode;
} else {
Node *temp = search(n);

if (temp->val == n) {
// return if value already exists
return;
}

// where the value is to be inserted

// connect new node to correct node
newNode->parent = temp;

if (n < temp->val)
temp->left = newNode;
else
temp->right = newNode;

// fix red red violation if exists
fixRedRed(newNode);
}
}

// utility function that deletes the node with given value
void deleteByVal(int n) {
if (root == NULL)
// Tree is empty
return;

Node *v = search(n), *u;

if (v->val != n) {
cout << "No node found to delete with value:" << n << endl;
return;
}

deleteNode(v);
}

// prints inorder of the tree
void printInOrder() {
cout << "Inorder: " << endl;
if (root == NULL)
cout << "Tree is empty" << endl;
else
inorder(root);
cout << endl;
}

// prints level order of the tree
void printLevelOrder() {
cout << "Level order: " << endl;
if (root == NULL)
cout << "Tree is empty" << endl;
else
levelOrder(root);
cout << endl;
}
};

int main() {
RBTree tree;

tree.insert(7);
tree.insert(3);
tree.insert(18);
tree.insert(10);
tree.insert(22);
tree.insert(8);
tree.insert(11);
tree.insert(26);
tree.insert(2);
tree.insert(6);
tree.insert(13);

tree.printInOrder();
tree.printLevelOrder();

cout<<endl<<"Deleting 18, 11, 3, 10, 22"<<endl;

tree.deleteByVal(18);
tree.deleteByVal(11);
tree.deleteByVal(3);
tree.deleteByVal(10);
tree.deleteByVal(22);

tree.printInOrder();
tree.printLevelOrder();
return 0;
}
```

Output

``````Inorder:
2 3 6 7 8 10 11 13 18 22 26

Level order:
10 7 18 3 8 11 22 2 6 13 26

Deleting 18, 11, 3, 10, 22

Inorder:
2 6 7 8 13 26

Level order:
13 7 26 6 8 2 ``````

Conclusion
In this article, we have discussed the Red black tree in data structure. Red Black Tree is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times. We have also discussed the use cases of Red Black Tree in data structure. How insertion and deletion work, along with how we can rotate a subtree in a Red black data structure.

Q1. What is the purpose of the red-black tree?
Ans. RB trees are used to construct associative arrays in functional programming. RB trees are used in conjunction with 2-4 trees, a self-balancing data structure in which each node has two, three, or four child nodes.

Q2. In terms of data structure complexity, what is a red-black tree?
Ans. Red-black trees give a logarithmic average and worst-case time complexity for insertion, search, and deletion. Rebalancing has an average time complexity of O(1), with a worst-case complexity of O(log n).

Q3. What exactly is a red-black tree?
Ans. A self-balancing binary search tree is a Red Black Tree. It was invented in 1972 by Rudolf Bayer and termed "symmetric binary B-trees."

Q4. What exactly is the red-black tree sorting algorithm?
Ans. The red-black tree algorithm is a method for balancing trees. The term is derived from the fact that each node is either red or black, and the color of the node is significant in defining the balance of the tree.

Q5. What is the highest point of the red-black tree algorithm?
Ans. Because red nodes cannot have red children, the path’s nodes must alternate between red and black. As a result, the path can only be twice as long as the black depth of the tree. As a result, the worst-case height of the tree is O(2 log nb). A red-black tree’s height is O(log n).