{"id":2128,"date":"2024-07-20T20:43:31","date_gmt":"2024-07-20T20:43:31","guid":{"rendered":"https:\/\/www.w3computing.com\/articles\/?p=2128"},"modified":"2024-07-20T20:43:36","modified_gmt":"2024-07-20T20:43:36","slug":"how-to-implement-a-red-black-tree-in-cpp","status":"publish","type":"post","link":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/","title":{"rendered":"How to Implement a Red-Black Tree in C++"},"content":{"rendered":"\n

Implementing a Red-Black Tree in C++ requires a good understanding of data structures, algorithms, and the specific properties that make Red-Black Trees efficient for various operations. In this tutorial, we will cover everything from the fundamental concepts to the complete implementation of a Red-Black Tree in C++.<\/p>\n\n\n\n

Introduction to Red-Black Trees<\/h2>\n\n\n\n

A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node, which can be either red or black. This color bit is used to ensure the tree remains approximately balanced during insertions and deletions. The balancing of the tree ensures that the operations such as insert, delete, and find can be performed in O(log n) time.<\/p>\n\n\n\n

Properties of Red-Black Trees<\/h3>\n\n\n\n

A Red-Black Tree must satisfy the following properties:<\/p>\n\n\n\n

    \n
  1. Root Property<\/strong>: The root is black.<\/li>\n\n\n\n
  2. Red Property<\/strong>: Red nodes cannot have red children (no two consecutive red nodes on any path).<\/li>\n\n\n\n
  3. Black Property<\/strong>: Every path from a node to its descendant null nodes has the same number of black nodes.<\/li>\n\n\n\n
  4. Depth Property<\/strong>: The depth of any path from the root to a leaf is no more than twice the depth of any other path.<\/li>\n<\/ol>\n\n\n\n

    These properties ensure that the tree remains balanced, and thus operations remain efficient.<\/p>\n\n\n\n

    Red-Black Tree Operations<\/h2>\n\n\n\n

    The primary operations we need to implement for a Red-Black Tree are:<\/p>\n\n\n\n

      \n
    1. Insertion<\/strong>: Adding a new node to the tree.<\/li>\n\n\n\n
    2. Deletion<\/strong>: Removing an existing node from the tree.<\/li>\n\n\n\n
    3. Search<\/strong>: Finding a node with a given value.<\/li>\n<\/ol>\n\n\n\n

      Before diving into the code, let’s discuss how these operations are handled in a Red-Black Tree.<\/p>\n\n\n\n

      Insertion<\/h3>\n\n\n\n

      Inserting a node in a Red-Black Tree involves the following steps:<\/p>\n\n\n\n

        \n
      1. Perform a standard BST insert.<\/li>\n\n\n\n
      2. Color the new node red.<\/li>\n\n\n\n
      3. Fix the tree to maintain the Red-Black properties by performing necessary rotations and recoloring.<\/li>\n<\/ol>\n\n\n\n

        Deletion<\/h3>\n\n\n\n

        Deleting a node from a Red-Black Tree involves:<\/p>\n\n\n\n

          \n
        1. Perform a standard BST delete.<\/li>\n\n\n\n
        2. Fix the tree to maintain the Red-Black properties by performing necessary rotations and recoloring.<\/li>\n<\/ol>\n\n\n\n

          Search<\/h3>\n\n\n\n

          Searching in a Red-Black Tree is similar to searching in a Binary Search Tree. It involves comparing the target value with the current node’s value and recursively searching in the left or right subtree.<\/p>\n\n\n\n

          Implementation in C++<\/h2>\n\n\n\n

          Let’s start with the implementation. We will define the structure for the nodes first, followed by the Red-Black Tree class that will include methods for insertion, deletion, and search.<\/p>\n\n\n\n

          Node Structure<\/h3>\n\n\n
          #include<\/span> <iostream><\/span><\/span>\n#include<\/span> <memory><\/span><\/span>\n\nenum<\/span> Color { RED, BLACK };\n\nstruct<\/span> Node<\/span> {<\/span>\n    int<\/span> data;\n    bool<\/span> color;\n    std<\/span>::shared_ptr<\/span><Node> left, right, parent;\n\n    Node(int<\/span> data) : data(data) {\n        parent = left = right = nullptr<\/span>;\n        color = RED;\n    }\n};<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Here, we use enum Color<\/code> to define the color of the nodes. Each node has a data value, color, and pointers to its left child, right child, and parent. The std::shared_ptr<\/code> is used for automatic memory management.<\/p>\n\n\n\n
          Red-Black Tree Class<\/h3>\n\n\n\n
          Now let’s define the Red-Black Tree class.<\/p>\n\n\n
          class<\/span> RedBlackTree<\/span> {<\/span>\nprivate<\/span>:\n    std<\/span>::shared_ptr<\/span><Node> root;\n    void<\/span> rotateLeft<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> rotateRight<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> fixInsert<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> fixDelete<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> transplant<\/span>(std<\/span>::shared_ptr<\/span><Node>&, std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    std<\/span>::shared_ptr<\/span><Node> minimum<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span><\/span>;\n    void<\/span> deleteNode<\/span>(std<\/span>::shared_ptr<\/span><Node>&, int<\/span>)<\/span><\/span>;\n    void<\/span> deleteFix<\/span>(std<\/span>::shared_ptr<\/span><Node>&, std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n\npublic<\/span>:\n    RedBlackTree() { root = nullptr<\/span>; }\n    void<\/span> insert<\/span>(const<\/span> int<\/span>& n)<\/span><\/span>;\n    void<\/span> deleteNode<\/span>(const<\/span> int<\/span>& data)<\/span><\/span>;\n    std<\/span>::shared_ptr<\/span><Node> search<\/span>(const<\/span> int<\/span>& n)<\/span><\/span>;\n    void<\/span> inorder<\/span>()<\/span><\/span>;\n    void<\/span> inorderHelper<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span><\/span>;\n};<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Rotations<\/h3>\n\n\n\n
          Rotations are a key part of maintaining the Red-Black Tree properties. Let’s implement the left and right rotations.<\/p>\n\n\n
          void<\/span> RedBlackTree::rotateLeft<\/span>(std<\/span>::shared_ptr<\/span><Node>& x)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> y = x->right;\n    x->right = y->left;\n\n    if<\/span> (y->left != nullptr<\/span>) {\n        y->left->parent = x;\n    }\n    y->parent = x->parent;\n\n    if<\/span> (x->parent == nullptr<\/span>) {\n        root = y;\n    } else<\/span> if<\/span> (x == x->parent->left) {\n        x->parent->left = y;\n    } else<\/span> {\n        x->parent->right = y;\n    }\n\n    y->left = x;\n    x->parent = y;\n}\n\nvoid<\/span> RedBlackTree::rotateRight<\/span>(std<\/span>::shared_ptr<\/span><Node>& x)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> y = x->left;\n    x->left = y->right;\n\n    if<\/span> (y->right != nullptr<\/span>) {\n        y->right->parent = x;\n    }\n    y->parent = x->parent;\n\n    if<\/span> (x->parent == nullptr<\/span>) {\n        root = y;\n    } else<\/span> if<\/span> (x == x->parent->right) {\n        x->parent->right = y;\n    } else<\/span> {\n        x->parent->left = y;\n    }\n\n    y->right = x;\n    x->parent = y;\n}<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Insertion<\/h3>\n\n\n\n
          The insert method involves inserting a new node like a standard BST and then fixing the tree to maintain the Red-Black properties.<\/p>\n\n\n
          void<\/span> RedBlackTree::insert<\/span>(const<\/span> int<\/span>& data)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> node = std<\/span>::make_shared<Node>(data);\n    std<\/span>::shared_ptr<\/span><Node> y = nullptr<\/span>;\n    std<\/span>::shared_ptr<\/span><Node> x = root;\n\n    while<\/span> (x != nullptr<\/span>) {\n        y = x;\n        if<\/span> (node->data < x->data) {\n            x = x->left;\n        } else<\/span> {\n            x = x->right;\n        }\n    }\n\n    node->parent = y;\n    if<\/span> (y == nullptr<\/span>) {\n        root = node;\n    } else<\/span> if<\/span> (node->data < y->data) {\n        y->left = node;\n    } else<\/span> {\n        y->right = node;\n    }\n\n    node->color = RED;\n    fixInsert(node);\n}\n\nvoid<\/span> RedBlackTree::fixInsert<\/span>(std<\/span>::shared_ptr<\/span><Node>& k)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> u;\n    while<\/span> (k->parent && k->parent->color == RED) {\n        if<\/span> (k->parent == k->parent->parent->right) {\n            u = k->parent->parent->left;\n            if<\/span> (u && u->color == RED) {\n                u->color = BLACK;\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                k = k->parent->parent;\n            } else<\/span> {\n                if<\/span> (k == k->parent->left) {\n                    k = k->parent;\n                    rotateRight(k);\n                }\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                rotateLeft(k->parent->parent);\n            }\n        } else<\/span> {\n            u = k->parent->parent->right;\n\n            if<\/span> (u && u->color == RED) {\n                u->color = BLACK;\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                k = k->parent->parent;\n            } else<\/span> {\n                if<\/span> (k == k->parent->right) {\n                    k = k->parent;\n                    rotateLeft(k);\n                }\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                rotateRight(k->parent->parent);\n            }\n        }\n        if<\/span> (k == root) {\n            break<\/span>;\n        }\n    }\n    root->color = BLACK;\n}<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Deletion<\/h3>\n\n\n\n
          Deletion involves removing the node like a standard BST and then fixing the tree to maintain the Red-Black properties.<\/p>\n\n\n
          void<\/span> RedBlackTree::transplant<\/span>(std<\/span>::shared_ptr<\/span><Node>& u, std<\/span>::shared_ptr<\/span><Node>& v)<\/span> <\/span>{\n    if<\/span> (u->parent == nullptr<\/span>) {\n        root = v;\n    } else<\/span> if<\/span> (u == u->parent->left) {\n        u->parent->left = v;\n    } else<\/span> {\n        u->parent->right = v;\n    }\n    if<\/span> (v != nullptr<\/span>) {\n        v->parent = u->parent;\n    }\n}\n\nstd<\/span>::shared_ptr<\/span><Node> RedBlackTree::minimum<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span> <\/span>{\n    while<\/span> (node->left != nullptr<\/span>) {\n        node = node->left;\n    }\n    return<\/span> node;\n}\n\nvoid<\/span> RedBlackTree::deleteNode<\/span>(const<\/span> int<\/span>& data)<\/span> <\/span>{\n    deleteNode(root, data);\n}\n\nvoid<\/span> RedBlackTree::deleteNode<\/span>(std<\/span>::shared_ptr<\/span><Node>& node, int<\/span> key)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> z = nullptr<\/span>;\n    std<\/span>::shared_ptr<\/span><Node> x, y;\n    while<\/span> (node != nullptr<\/span>) {\n        if<\/span> (node->data == key) {\n            z = node;\n        }\n\n        if<\/span> (node->data <= key) {\n            node = node->right;\n        } else<\/span> {\n            node = node->left;\n        }\n    }\n\n    if<\/span> (z == nullptr<\/span>) {\n        std<\/span>::cout<\/span> << \"Key not found in the tree\"<\/span> << std<\/span>::endl<\/span>;\n        return<\/span>;\n    }\n\n    y = z;\n    bool<\/span> yOriginalColor = y->color;\n    if<\/span> (z\n\n->left == nullptr<\/span>) {\n        x = z->right;\n        transplant(z, z->right);\n    } else<\/span> if<\/span> (z->right == nullptr<\/span>) {\n        x = z->left;\n        transplant(z, z->left);\n    } else<\/span> {\n        y = minimum(z->right);\n        yOriginalColor = y->color;\n        x = y->right;\n        if<\/span> (y->parent == z) {\n            if<\/span> (x != nullptr<\/span>) {\n                x->parent = y;\n            }\n        } else<\/span> {\n            transplant(y, y->right);\n            y->right = z->right;\n            if<\/span> (y->right != nullptr<\/span>) {\n                y->right->parent = y;\n            }\n        }\n        transplant(z, y);\n        y->left = z->left;\n        if<\/span> (y->left != nullptr<\/span>) {\n            y->left->parent = y;\n        }\n        y->color = z->color;\n    }\n    if<\/span> (yOriginalColor == BLACK) {\n        deleteFix(x);\n    }\n}\n\nvoid<\/span> RedBlackTree::deleteFix<\/span>(std<\/span>::shared_ptr<\/span><Node>& x)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> s;\n    while<\/span> (x != root && x->color == BLACK) {\n        if<\/span> (x == x->parent->left) {\n            s = x->parent->right;\n            if<\/span> (s->color == RED) {\n                s->color = BLACK;\n                x->parent->color = RED;\n                rotateLeft(x->parent);\n                s = x->parent->right;\n            }\n\n            if<\/span> ((s->left == nullptr<\/span> || s->left->color == BLACK) && (s->right == nullptr<\/span> || s->right->color == BLACK)) {\n                s->color = RED;\n                x = x->parent;\n            } else<\/span> {\n                if<\/span> (s->right == nullptr<\/span> || s->right->color == BLACK) {\n                    if<\/span> (s->left != nullptr<\/span>) {\n                        s->left->color = BLACK;\n                    }\n                    s->color = RED;\n                    rotateRight(s);\n                    s = x->parent->right;\n                }\n\n                s->color = x->parent->color;\n                x->parent->color = BLACK;\n                if<\/span> (s->right != nullptr<\/span>) {\n                    s->right->color = BLACK;\n                }\n                rotateLeft(x->parent);\n                x = root;\n            }\n        } else<\/span> {\n            s = x->parent->left;\n            if<\/span> (s->color == RED) {\n                s->color = BLACK;\n                x->parent->color = RED;\n                rotateRight(x->parent);\n                s = x->parent->left;\n            }\n\n            if<\/span> ((s->left == nullptr<\/span> || s->left->color == BLACK) && (s->right == nullptr<\/span> || s->right->color == BLACK)) {\n                s->color = RED;\n                x = x->parent;\n            } else<\/span> {\n                if<\/span> (s->left == nullptr<\/span> || s->left->color == BLACK) {\n                    if<\/span> (s->right != nullptr<\/span>) {\n                        s->right->color = BLACK;\n                    }\n                    s->color = RED;\n                    rotateLeft(s);\n                    s = x->parent->left;\n                }\n\n                s->color = x->parent->color;\n                x->parent->color = BLACK;\n                if<\/span> (s->left != nullptr<\/span>) {\n                    s->left->color = BLACK;\n                }\n                rotateRight(x->parent);\n                x = root;\n            }\n        }\n    }\n    x->color = BLACK;\n}<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Search<\/h3>\n\n\n\n
          The search operation is straightforward in a Red-Black Tree.<\/p>\n\n\n
          std<\/span>::shared_ptr<\/span><Node> RedBlackTree::search<\/span>(const<\/span> int<\/span>& n)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> temp = root;\n    while<\/span> (temp != nullptr<\/span>) {\n        if<\/span> (n < temp->data) {\n            temp = temp->left;\n        } else<\/span> if<\/span> (n > temp->data) {\n            temp = temp->right;\n        } else<\/span> {\n            return<\/span> temp;\n        }\n    }\n    return<\/span> nullptr<\/span>;\n}<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Inorder Traversal<\/h3>\n\n\n\n
          Inorder traversal is useful for verifying the structure of the tree.<\/p>\n\n\n
          void<\/span> RedBlackTree::inorder<\/span>()<\/span> <\/span>{\n    inorderHelper(root);\n}\n\nvoid<\/span> RedBlackTree::inorderHelper<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span> <\/span>{\n    if<\/span> (node == nullptr<\/span>) {\n        return<\/span>;\n    }\n    inorderHelper(node->left);\n    std<\/span>::cout<\/span> << node->data << \" \"<\/span>;\n    inorderHelper(node->right);\n}<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Complete Example<\/h2>\n\n\n\n
          Here is a complete example of a Red-Black Tree in C++ that includes insertion, deletion, and search operations.<\/p>\n\n\n
          #include<\/span> <iostream><\/span><\/span>\n#include<\/span> <memory><\/span><\/span>\n\nenum<\/span> Color { RED, BLACK };\n\nstruct<\/span> Node<\/span> {<\/span>\n    int<\/span> data;\n    bool<\/span> color;\n    std<\/span>::shared_ptr<\/span><Node> left, right, parent;\n\n    Node(int<\/span> data) : data(data) {\n        parent = left = right = nullptr<\/span>;\n        color = RED;\n    }\n};\n\nclass<\/span> RedBlackTree<\/span> {<\/span>\nprivate<\/span>:\n    std<\/span>::shared_ptr<\/span><Node> root;\n    void<\/span> rotateLeft<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> rotateRight<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> fixInsert<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> fixDelete<\/span>(std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    void<\/span> transplant<\/span>(std<\/span>::shared_ptr<\/span><Node>&, std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n    std<\/span>::shared_ptr<\/span><Node> minimum<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span><\/span>;\n    void<\/span> deleteNode<\/span>(std<\/span>::shared_ptr<\/span><Node>&, int<\/span>)<\/span><\/span>;\n    void<\/span> deleteFix<\/span>(std<\/span>::shared_ptr<\/span><Node>&, std<\/span>::shared_ptr<\/span><Node>&)<\/span><\/span>;\n\npublic<\/span>:\n    RedBlackTree() { root = nullptr<\/span>; }\n    void<\/span> insert<\/span>(const<\/span> int<\/span>& n)<\/span><\/span>;\n    void<\/span> deleteNode<\/span>(const<\/span> int<\/span>& data)<\/span><\/span>;\n    std<\/span>::shared_ptr<\/span><Node> search<\/span>(const<\/span> int<\/span>& n)<\/span><\/span>;\n    void<\/span> inorder<\/span>()<\/span><\/span>;\n    void<\/span> inorderHelper<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span><\/span>;\n};\n\nvoid<\/span> RedBlackTree::rotateLeft<\/span>(std<\/span>::shared_ptr<\/span><Node>& x)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> y = x->right;\n    x->right = y->left;\n\n    if<\/span> (y->left != nullptr<\/span>) {\n        y->left->parent = x;\n    }\n    y->parent = x->parent;\n\n    if<\/span> (x->parent == nullptr<\/span>) {\n        root = y;\n    } else<\/span> if<\/span> (x == x->parent->left) {\n        x->parent->left = y;\n    } else<\/span> {\n        x->parent->right = y;\n    }\n\n    y->left = x;\n    x->parent = y;\n}\n\nvoid<\/span> RedBlackTree::rotateRight<\/span>(std<\/span>::shared_ptr<\/span><Node>& x)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> y = x->left;\n    x->left = y->right;\n\n    if<\/span> (y->right != nullptr<\/span>) {\n        y->right->parent = x;\n    }\n    y->parent = x->parent;\n\n    if<\/span> (x->parent == nullptr<\/span>) {\n        root = y;\n    } else<\/span> if<\/span> (x == x->parent->right) {\n        x->parent->right = y;\n    } else<\/span> {\n        x->parent->left = y;\n    }\n\n    y->right = x;\n    x->parent = y;\n}\n\nvoid<\/span> RedBlackTree::insert<\/span>(const<\/span> int<\/span>& data)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> node = std<\/span>::make_shared<Node>(data);\n    std<\/span>::shared_ptr<\/span><Node> y = nullptr<\/span>;\n    std<\/span>::shared_ptr<\/span><Node> x = root;\n\n    while<\/span> (x != nullptr<\/span>) {\n        y = x;\n        if<\/span> (node->data < x->data) {\n            x = x->left;\n        } else<\/span> {\n            x = x->right;\n        }\n    }\n\n    node->parent = y;\n    if<\/span> (y == nullptr<\/span>) {\n        root = node;\n    } else<\/span> if<\/span> (node->data < y->data) {\n        y->left = node;\n    } else<\/span> {\n        y->right = node;\n    }\n\n    node->color = RED;\n    fixInsert(node);\n}\n\nvoid<\/span> RedBlackTree::fixInsert<\/span>(std<\/span>::shared_ptr<\/span><Node>& k)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> u;\n    while<\/span> (k->parent && k->parent->color == RED) {\n        if<\/span> (k->parent == k->parent->parent->right) {\n            u = k->parent->parent->left;\n            if<\/span> (u && u->color == RED) {\n                u->color = BLACK;\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                k = k->parent->parent;\n            } else<\/span> {\n                if<\/span> (k == k->parent->left) {\n                    k = k->parent;\n                    rotateRight(k);\n                }\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                rotateLeft(k->parent->parent);\n            }\n        } else<\/span> {\n            u = k->parent->parent->right;\n\n            if<\/span> (u && u->color == RED) {\n                u->color = BLACK;\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                k = k->parent->parent;\n            } else<\/span> {\n                if<\/span> (k == k->parent->right) {\n                    k = k->parent;\n                    rotateLeft(k);\n                }\n                k->parent->color = BLACK;\n                k->parent->parent->color = RED;\n                rotateRight(k->parent->parent);\n            }\n        }\n        if<\/span> (k == root) {\n            break<\/span>;\n        }\n    }\n    root->color = BLACK;\n}\n\nvoid<\/span> RedBlackTree::transplant<\/span>(std<\/span>::shared_ptr<\/span><Node>& u, std<\/span>::shared_ptr<\/span><Node>& v)<\/span> <\/span>{\n    if<\/span> (u->parent == nullptr<\/span>) {\n        root = v;\n    } else<\/span> if<\/span> (u == u->parent->left) {\n        u->parent->left = v;\n    } else<\/span> {\n        u->parent->right = v\n\n;\n    }\n    if<\/span> (v != nullptr<\/span>) {\n        v->parent = u->parent;\n    }\n}\n\nstd<\/span>::shared_ptr<\/span><Node> RedBlackTree::minimum<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span> <\/span>{\n    while<\/span> (node->left != nullptr<\/span>) {\n        node = node->left;\n    }\n    return<\/span> node;\n}\n\nvoid<\/span> RedBlackTree::deleteNode<\/span>(const<\/span> int<\/span>& data)<\/span> <\/span>{\n    deleteNode(root, data);\n}\n\nvoid<\/span> RedBlackTree::deleteNode<\/span>(std<\/span>::shared_ptr<\/span><Node>& node, int<\/span> key)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> z = nullptr<\/span>;\n    std<\/span>::shared_ptr<\/span><Node> x, y;\n    while<\/span> (node != nullptr<\/span>) {\n        if<\/span> (node->data == key) {\n            z = node;\n        }\n\n        if<\/span> (node->data <= key) {\n            node = node->right;\n        } else<\/span> {\n            node = node->left;\n        }\n    }\n\n    if<\/span> (z == nullptr<\/span>) {\n        std<\/span>::cout<\/span> << \"Key not found in the tree\"<\/span> << std<\/span>::endl<\/span>;\n        return<\/span>;\n    }\n\n    y = z;\n    bool<\/span> yOriginalColor = y->color;\n    if<\/span> (z->left == nullptr<\/span>) {\n        x = z->right;\n        transplant(z, z->right);\n    } else<\/span> if<\/span> (z->right == nullptr<\/span>) {\n        x = z->left;\n        transplant(z, z->left);\n    } else<\/span> {\n        y = minimum(z->right);\n        yOriginalColor = y->color;\n        x = y->right;\n        if<\/span> (y->parent == z) {\n            if<\/span> (x != nullptr<\/span>) {\n                x->parent = y;\n            }\n        } else<\/span> {\n            transplant(y, y->right);\n            y->right = z->right;\n            if<\/span> (y->right != nullptr<\/span>) {\n                y->right->parent = y;\n            }\n        }\n        transplant(z, y);\n        y->left = z->left;\n        if<\/span> (y->left != nullptr<\/span>) {\n            y->left->parent = y;\n        }\n        y->color = z->color;\n    }\n    if<\/span> (yOriginalColor == BLACK) {\n        deleteFix(x);\n    }\n}\n\nvoid<\/span> RedBlackTree::deleteFix<\/span>(std<\/span>::shared_ptr<\/span><Node>& x)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> s;\n    while<\/span> (x != root && x->color == BLACK) {\n        if<\/span> (x == x->parent->left) {\n            s = x->parent->right;\n            if<\/span> (s->color == RED) {\n                s->color = BLACK;\n                x->parent->color = RED;\n                rotateLeft(x->parent);\n                s = x->parent->right;\n            }\n\n            if<\/span> ((s->left == nullptr<\/span> || s->left->color == BLACK) && (s->right == nullptr<\/span> || s->right->color == BLACK)) {\n                s->color = RED;\n                x = x->parent;\n            } else<\/span> {\n                if<\/span> (s->right == nullptr<\/span> || s->right->color == BLACK) {\n                    if<\/span> (s->left != nullptr<\/span>) {\n                        s->left->color = BLACK;\n                    }\n                    s->color = RED;\n                    rotateRight(s);\n                    s = x->parent->right;\n                }\n\n                s->color = x->parent->color;\n                x->parent->color = BLACK;\n                if<\/span> (s->right != nullptr<\/span>) {\n                    s->right->color = BLACK;\n                }\n                rotateLeft(x->parent);\n                x = root;\n            }\n        } else<\/span> {\n            s = x->parent->left;\n            if<\/span> (s->color == RED) {\n                s->color = BLACK;\n                x->parent->color = RED;\n                rotateRight(x->parent);\n                s = x->parent->left;\n            }\n\n            if<\/span> ((s->left == nullptr<\/span> || s->left->color == BLACK) && (s->right == nullptr<\/span> || s->right->color == BLACK)) {\n                s->color = RED;\n                x = x->parent;\n            } else<\/span> {\n                if<\/span> (s->left == nullptr<\/span> || s->left->color == BLACK) {\n                    if<\/span> (s->right != nullptr<\/span>) {\n                        s->right->color = BLACK;\n                    }\n                    s->color = RED;\n                    rotateLeft(s);\n                    s = x->parent->left;\n                }\n\n                s->color = x->parent->color;\n                x->parent->color = BLACK;\n                if<\/span> (s->left != nullptr<\/span>) {\n                    s->left->color = BLACK;\n                }\n                rotateRight(x->parent);\n                x = root;\n            }\n        }\n    }\n    x->color = BLACK;\n}\n\nstd<\/span>::shared_ptr<\/span><Node> RedBlackTree::search<\/span>(const<\/span> int<\/span>& n)<\/span> <\/span>{\n    std<\/span>::shared_ptr<\/span><Node> temp = root;\n    while<\/span> (temp != nullptr<\/span>) {\n        if<\/span> (n < temp->data) {\n            temp = temp->left;\n        } else<\/span> if<\/span> (n > temp->data) {\n            temp = temp->right;\n        } else<\/span> {\n            return<\/span> temp;\n        }\n    }\n    return<\/span> nullptr<\/span>;\n}\n\nvoid<\/span> RedBlackTree::inorder<\/span>()<\/span> <\/span>{\n    inorderHelper(root);\n}\n\nvoid<\/span> RedBlackTree::inorderHelper<\/span>(std<\/span>::shared_ptr<\/span><Node> node)<\/span> <\/span>{\n    if<\/span> (node == nullptr<\/span>) {\n        return<\/span>;\n    }\n    inorderHelper(node->left);\n    std<\/span>::cout<\/span> << node->data << \" \"<\/span>;\n    inorderHelper(node->right);\n}\n\nint<\/span> main<\/span>()<\/span> <\/span>{\n    RedBlackTree tree;\n    tree.insert(10<\/span>);\n    tree.insert(20<\/span>);\n    tree.insert(30<\/span>);\n    tree.insert(15<\/span>);\n    tree.insert(25<\/span>);\n\n    std<\/span>::cout<\/span> << \"Inorder Traversal of Created Tree\\n\"<\/span>;\n    tree.inorder();\n    std<\/span>::cout<\/span> << std<\/span>::endl<\/span>;\n\n    tree.deleteNode(20<\/span>);\n    std<\/span>::cout<\/span> << \"Inorder Traversal after Deletion of 20\\n\"<\/span>;\n    tree.inorder();\n    std<\/span>::cout<\/span> << std<\/span>::endl<\/span>;\n\n    return<\/span> 0<\/span>;\n}<\/code><\/span>Code language:<\/span> C++<\/span> (<\/span>cpp<\/span>)<\/span><\/small><\/pre>\n\n\n
          Conclusion<\/h2>\n\n\n\n
          In this tutorial, we have covered the fundamental concepts of Red-Black Trees and provided a comprehensive implementation in C++. By understanding the properties and operations of Red-Black Trees, you can effectively utilize this data structure to ensure efficient data management and retrieval in your applications.<\/p>\n","protected":false},"excerpt":{"rendered":"
          Implementing a Red-Black Tree in C++ requires a good understanding of data structures, algorithms, and the specific properties that make Red-Black Trees efficient for various operations. In this tutorial, we will cover everything from the fundamental concepts to the complete implementation of a Red-Black Tree in C++. Introduction to Red-Black Trees A Red-Black Tree is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_genesis_hide_title":false,"_genesis_hide_breadcrumbs":false,"_genesis_hide_singular_image":false,"_genesis_hide_footer_widgets":false,"_genesis_custom_body_class":"","_genesis_custom_post_class":"","_genesis_layout":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[9,4],"tags":[],"class_list":["post-2128","post","type-post","status-publish","format-standard","category-cplusplus","category-programming-languages","entry"],"yoast_head":"\nHow to Implement a Red-Black Tree in C++<\/title>\n<meta name=\"description\" content=\"A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"How to Implement a Red-Black Tree in C++\" \/>\n<meta property=\"og:description\" content=\"A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/\" \/>\n<meta property=\"article:published_time\" content=\"2024-07-20T20:43:31+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-07-20T20:43:36+00:00\" \/>\n<meta name=\"author\" content=\"w3compadmin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"w3compadmin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"TechArticle\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/\"},\"author\":{\"name\":\"w3compadmin\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\"},\"headline\":\"How to Implement a Red-Black Tree in C++\",\"datePublished\":\"2024-07-20T20:43:31+00:00\",\"dateModified\":\"2024-07-20T20:43:36+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/\"},\"wordCount\":610,\"articleSection\":[\"C++\",\"Programming Languages\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/\",\"name\":\"How to Implement a Red-Black Tree in C++\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#website\"},\"datePublished\":\"2024-07-20T20:43:31+00:00\",\"dateModified\":\"2024-07-20T20:43:36+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\"},\"description\":\"A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-a-red-black-tree-in-cpp\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Articles Home\",\"item\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Programming Languages\",\"item\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/programming-languages\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"C++\",\"item\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/programming-languages\\\/cplusplus\\\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"How to Implement a Red-Black Tree in C++\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#website\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/\",\"name\":\"Developer Articles Hub\",\"description\":\"\",\"alternateName\":\"Developer Articles\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\",\"name\":\"w3compadmin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1780141266\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1780141266\",\"contentUrl\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1780141266\",\"caption\":\"w3compadmin\"},\"sameAs\":[\"http:\\\/\\\/w3computing.com\\\/articles\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"How to Implement a Red-Black Tree in C++","description":"A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/","og_locale":"en_US","og_type":"article","og_title":"How to Implement a Red-Black Tree in C++","og_description":"A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node","og_url":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/","article_published_time":"2024-07-20T20:43:31+00:00","article_modified_time":"2024-07-20T20:43:36+00:00","author":"w3compadmin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"w3compadmin","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"TechArticle","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/#article","isPartOf":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/"},"author":{"name":"w3compadmin","@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561"},"headline":"How to Implement a Red-Black Tree in C++","datePublished":"2024-07-20T20:43:31+00:00","dateModified":"2024-07-20T20:43:36+00:00","mainEntityOfPage":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/"},"wordCount":610,"articleSection":["C++","Programming Languages"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/","url":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/","name":"How to Implement a Red-Black Tree in C++","isPartOf":{"@id":"https:\/\/www.w3computing.com\/articles\/#website"},"datePublished":"2024-07-20T20:43:31+00:00","dateModified":"2024-07-20T20:43:36+00:00","author":{"@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561"},"description":"A Red-Black Tree is a type of self-balancing binary search tree. Each node in the tree contains an extra bit for storing the color of the node","breadcrumb":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-a-red-black-tree-in-cpp\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Articles Home","item":"https:\/\/www.w3computing.com\/articles\/"},{"@type":"ListItem","position":2,"name":"Programming Languages","item":"https:\/\/www.w3computing.com\/articles\/programming-languages\/"},{"@type":"ListItem","position":3,"name":"C++","item":"https:\/\/www.w3computing.com\/articles\/programming-languages\/cplusplus\/"},{"@type":"ListItem","position":4,"name":"How to Implement a Red-Black Tree in C++"}]},{"@type":"WebSite","@id":"https:\/\/www.w3computing.com\/articles\/#website","url":"https:\/\/www.w3computing.com\/articles\/","name":"Developer Articles Hub","description":"","alternateName":"Developer Articles","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.w3computing.com\/articles\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561","name":"w3compadmin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1780141266","url":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1780141266","contentUrl":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1780141266","caption":"w3compadmin"},"sameAs":["http:\/\/w3computing.com\/articles"]}]}},"featured_image_src":null,"featured_image_src_square":null,"author_info":{"display_name":"w3compadmin","author_link":"https:\/\/www.w3computing.com\/articles\/author\/w3compadmin\/"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2128","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/comments?post=2128"}],"version-history":[{"count":2,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2128\/revisions"}],"predecessor-version":[{"id":2130,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2128\/revisions\/2130"}],"wp:attachment":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/media?parent=2128"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/categories?post=2128"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/tags?post=2128"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}