Red-Black Trees in C++

Red-Black Trees are one of the most widely used data structures in computer science. These trees are a type of self-balancing binary search tree, which means the tree structure is able to maintain a balance between the left and right subtrees. This ensures that operations on the tree, such as insertion, search, and deletion, are performed quickly. Red-Black Trees are used in many applications, from databases to operating systems, and have become an essential tool for any programmer. In this article, we will discuss the fundamentals of Red-Black Trees in C++, including the tree structure, time complexity for operations, and space complexity.

Tree Structure of Red-Black Trees

A Red-Black Tree is a type of binary search tree that is self-balancing. This means that the tree is able to maintain a balance between the left and right subtrees, which ensures that operations on the tree are performed quickly. The tree structure of a Red-Black Tree is composed of nodes, which are connected by edges. Each node is labeled with either a red or black color, and the root node is always black.

Each node in a Red-Black Tree contains three pieces of information: a key, a color, and two pointers to left and right subtrees. The key is used to compare nodes and determine the order of the tree. The color of the node is either red or black, and is used to maintain a balance in the tree. The pointers are used to connect nodes to the left and right subtrees.

The following is a sample implementation of a Red-Black Tree in C++:

struct Node { 
  int data; 
  bool color; 
  Node *left, *right; 
}; 

// Root node is always black 
Node *root = new Node(data); 
root->color = BLACK; 

// Create new node 
Node *newNode(int data) { 
  Node *node = new Node(data); 
  node->left = node->right = NULL; 
  node->color = RED; 
  return node; 
}

Time Complexity of Red-Black Trees

The time complexity of Red-Black Trees is dependent on the type of operation being performed. Generally, the time complexity of operations on a Red-Black Tree is O(log n), where n is the number of nodes in the tree. This means that the time complexity of operations on a Red-Black Tree is much smaller than that of a regular binary search tree.

The average time complexity of operations on a Red-Black Tree is O(log n). This means that the time complexity of operations is small and consistent, regardless of the size of the tree.

The worst-case time complexity of operations on a Red-Black Tree is also O(log n). This means that the time complexity of an operation is not affected by the size of the tree, and will always be the same.

Space Complexity of Red-Black Trees

The space complexity of Red-Black Trees is O(n), where n is the number of nodes in the tree. This means that the space complexity is dependent on the size of the tree and increases as the tree grows.

Insertion and Deletion in Red-Black Trees

Insertion and deletion in Red-Black Trees is similar to that of a regular binary search tree, but with the added complexity of maintaining the balance of the tree.

When inserting a new node into the tree, the node must be inserted in the correct position and the color of the node must be set to red. If the node’s parent is red, then the tree must be rebalanced in order to maintain the balance of the tree. The process of rebalancing the tree is complex and beyond the scope of this article.

When deleting a node from the tree, the process is similar to that of insertion. The deleted node must be replaced with another node, and the color of the new node must be set to red. If the new node’s parent is red, then the tree must be rebalanced in order to maintain the balance of the tree.

Conclusion

Red-Black Trees are a type of self-balancing binary search tree, which means the tree structure is able to maintain a balance between the left and right subtrees. This ensures that operations on the tree, such as insertion, search, and deletion, are performed quickly. The time complexity of operations on a Red-Black Tree is O(log n), and the space complexity is O(n). Insertion and deletion in Red-Black Trees is similar to that of a regular binary search tree, but with the added complexity of maintaining the balance of the tree.

Exercises

void insertNode(Node *root, int data) { 
  Node *newNode = new Node(data); 
  if (root == NULL) { 
    root = newNode; 
    root->color = BLACK; 
  } 
  else { 
    Node *current = root; 
    while (current != NULL) { 
      if (data < current->data) { 
        if (current->left == NULL) { 
          current->left = newNode; 
          newNode->color = RED; 
          break; 
        } 
        else { 
          current = current->left; 
        } 
      } 
      else { 
        if (current->right == NULL) { 
          current->right = newNode; 
          newNode->color = RED; 
          break; 
        } 
        else { 
          current = current->right; 
        } 
      } 
    } 
  } 
} 

Node* searchNode(Node *root, int data) { 
  if (root == NULL) { 
    return NULL; 
  } 
  else { 
    Node *current = root; 
    while (current != NULL) { 
      if (data == current->data) { 
        return current; 
      } 
      else if (data < current->data) { 
        current = current->left; 
      } 
      else { 
        current = current->right; 
      } 
    } 
    return NULL; 
  } 
}

void deleteNode(Node* root, int data) { 
  if (root == NULL) { 
    return; 
  } 
  else { 
    Node *current = root; 
    Node *parent = NULL; 
    while (current != NULL) { 
      if (data == current->data) { 
        // Node to be deleted is a leaf node 
        if (current->left == NULL && current->right == NULL) { 
          // If node is a left child of its parent 
          if (parent->left == current) 
            parent->left = NULL; 
          // If node is a right child of its parent 
          else
            parent->right = NULL; 
          delete current; 
          return; 
        } 
        // Node to be deleted has one child 
        else if (current->left == NULL || current->right == NULL) { 
          if (current->left == NULL) { 
            // If node is a left child of its parent 
            if (parent->left == current) 
              parent->left = current->right; 
            // If node is a right child of its parent 
            else
              parent->right = current->right; 
          } 
          else { 
            // If node is a left child of its parent 
            if (parent->left == current) 
              parent->left = current->left; 
            // If node is a right child of its parent 
            else
              parent->right = current->left; 
          } 
          delete current; 
          return; 
        } 
        // Node to be deleted has two children 
        else { 
          Node *successor = findSuccessor(current); 
          int successorData = successor->data; 
          deleteNode(root, successorData); 
          current->data = successorData; 
          return; 
        } 
      } 
      else if (data < current->data) { 
        parent = current; 
        current = current->left; 
      } 
      else { 
        parent = current; 
        current = current->right; 
      } 
    } 
    cout << "Element not found." << endl; 
  } 
}

Node* findSuccessor(Node *node) { 
  if (node->right != NULL) { 
    Node *current = node->right; 
    while (current->left != NULL) { 
      current = current->left; 
    } 
    return current; 
  } 
  else { 
    Node *current = node->parent; 
    while (current != NULL && node == current->right) { 
      node = current; 
      current = current->parent; 
    } 
    return current; 
  } 
}

void rebalanceTree(Node* root) { 
  // Left-Left case 
  if (root->left->left != NULL && root->left->color == RED) { 
    root->color = RED; 
    root->left->color = BLACK; 
    rightRotate(root); 
  } 
  // Right-Right case 
  if (root->right->right != NULL && root->right->color == RED) { 
    root->color = RED; 
    root->right->color = BLACK; 
    leftRotate(root); 
  } 
  // Left-Right case 
  if (root->left->right != NULL && root->left->color == RED) { 
    root->left->right->color = BLACK; 
    leftRotate(root->left); 
    rightRotate(root); 
  } 
  // Right-Left case 
  if (root->right->left != NULL && root->right->color == RED) { 
    root->right->left->color = BLACK; 
    rightRotate(root->right); 
    leftRotate(root); 
  } 
}