RUN


What is Red Black Tree ?

Insertion in Red Black Tree

Deletion in Red Black Tree

Red Black Tree Deletion

The deletion of an element from a tree means the removal of a node from a tree. The process of deleting a node from a Red-black tree is complex than insertion. In the removal of a node, the notion of double black is followed.

 Following steps are followed for deleting a node from Red-Black Tree:

  1. Standard BST removal: in this case, we delete a node that is either a leaf or has only one child. We will consider node to be deleted as L and node that replaces it as C.
  2. Simple case: Either L or C is red, we color the replaced child as black. Both the L and C nodes cannot be red as two consecutive red nodes are not allowed in a Red-Black Tree.
  3. If both L & C are black, the child node becomes double black after the removal of a black node.

 

// Program to show Deletion in red-black tree

#include <iostream>

using namespace std;

struct Node

{

  int data;

  Node * parent;

  Node * left;

  Node * right;

  int color;

};

typedef Node * NodePtr;

class RedBlackTree

{

  private:

    NodePtr root;

  NodePtr TNULL;

  void initializeNULLNode(NodePtr node, NodePtr parent)

  {

    node - > data = 0;

    node - > parent = parent;

    node - > left = nullptr;

    node - > right = nullptr;

    node - > color = 0;

  }

  void preOrderTraversal(NodePtr node)

  {

    if (node != TNULL)

    {

      cout << node - > data << " ";

      preOrderTraversal(node - > left);

      preOrderTraversal(node - > right);

    }

  }

  void inOrderTraversal(NodePtr node)

  {

    if (node != TNULL)

    {

      inOrderTraversal(node - > left);

      cout << node - > data << " ";

      inOrderTraversal(node - > right);

    }

  }

  void postOrderTraversal(NodePtr node)

  {

    if (node != TNULL)

    {

      postOrderTraversal(node - > left);

      postOrderTraversal(node - > right);

      cout << node - > data << " ";

    }

  }

  NodePtr searchTreeTraversal(NodePtr node, int key)

  {

    if (node == TNULL || key == node - > data)

    {

      return node;

    }

    if (key < node - > data)

    {

      return searchTreeTraversal(node - > left, key);

    }

    return searchTreeTraversal(node - > right, key);

  }

  void deleteFix(NodePtr x)

  {

    NodePtr s;

    while (x != root && x - > color == 0)

    {

      if (x == x - > parent - > left)

      {

        s = x - > parent - > right;

        if (s - > color == 1)

        {

          s - > color = 0;

          x - > parent - > color = 1;

          leftRotate(x - > parent);

          s = x - > parent - > right;

        }

        if (s - > left - > color == 0 && s - > right - > color == 0)

        {

          s - > color = 1;

          x = x - > parent;

        } else

        {

          if (s - > right - > color == 0)

          {

            s - > left - > color = 0;

            s - > color = 1;

            rightRotate(s);

            s = x - > parent - > right;

          }

          s - > color = x - > parent - > color;

          x - > parent - > color = 0;

          s - > right - > color = 0;

          leftRotate(x - > parent);

          x = root;

        }

      } else

      {

        s = x - > parent - > left;

        if (s - > color == 1)

        {

          s - > color = 0;

          x - > parent - > color = 1;

          rightRotate(x - > parent);

          s = x - > parent - > left;

        }

        if (s - > right - > color == 0 && s - > right - > color == 0)

        {

          s - > color = 1;

          x = x - > parent;

        } else

        {

          if (s - > left - > color == 0)

          {

            s - > right - > color = 0;

            s - > color = 1;

            leftRotate(s);

            s = x - > parent - > left;

          }

          s - > color = x - > parent - > color;

          x - > parent - > color = 0;

          s - > left - > color = 0;

          rightRotate(x - > parent);

          x = root;

        }

      }

    }

    x - > color = 0;

  }

  void rbTransplant(NodePtr u, NodePtr v)

  {

    if (u - > parent == nullptr)

    {

      root = v;

    } else if (u == u - > parent - > left)

    {

      u - > parent - > left = v;

    } else

    {

      u - > parent - > right = v;

    }

    v - > parent = u - > parent;

  }

  void deleteNodeHelper(NodePtr node, int key)

  {

    NodePtr z = TNULL;

    NodePtr x, y;

    while (node != TNULL)

    {

      if (node - > data == key)

      {

        z = node;

      }

      if (node - > data <= key)

      {

        node = node - > right;

      } else

      {

        node = node - > left;

      }

    }

    if (z == TNULL)

    {

      cout << "Key not found in the tree" << endl;

      return;

    }

    y = z;

    int y_original_color = y - > color;

    if (z - > left == TNULL)

    {

      x = z - > right;

      rbTransplant(z, z - > right);

    } else if (z - > right == TNULL)

    {

      x = z - > left;

      rbTransplant(z, z - > left);

    } else

    {

      y = minimum(z - > right);

      y_original_color = y - > color;

      x = y - > right;

      if (y - > parent == z)

      {

        x - > parent = y;

      } else

      {

        rbTransplant(y, y - > right);

        y - > right = z - > right;

        y - > right - > parent = y;

      }

      rbTransplant(z, y);

      y - > left = z - > left;

      y - > left - > parent = y;

      y - > color = z - > color;

    }

    delete z;

    if (y_original_color == 0)

    {

      deleteFix(x);

    }

  }

  void insertFix(NodePtr k)

  {

    NodePtr u;

    while (k - > parent - > color == 1)

    {

      if (k - > parent == k - > parent - > parent - > right)

      {

        u = k - > parent - > parent - > left;

        if (u - > color == 1)

        {

          u - > color = 0;

          k - > parent - > color = 0;

          k - > parent - > parent - > color = 1;

          k = k - > parent - > parent;

        } else

        {

          if (k == k - > parent - > left)

          {

            k = k - > parent;

            rightRotate(k);

          }

          k - > parent - > color = 0;

          k - > parent - > parent - > color = 1;

          leftRotate(k - > parent - > parent);

        }

      } else

      {

        u = k - > parent - > parent - > right;

        if (u - > color == 1)

        {

          u - > color = 0;

          k - > parent - > color = 0;

          k - > parent - > parent - > color = 1;

          k = k - > parent - > parent;

        } else

        {

          if (k == k - > parent - > right)

          {

            k = k - > parent;

            leftRotate(k);

          }

          k - > parent - > color = 0;

          k - > parent - > parent - > color = 1;

          rightRotate(k - > parent - > parent);

        }

      }

      if (k == root)

      {

        break;

      }

    }

    root - > color = 0;

  }

  void printHelper(NodePtr root, string indent, bool last)

  {

    if (root != TNULL)

    {

      cout << indent;

      if (last)

      {

        cout << "R----";

        indent += "   ";

      } else

      {

        cout << "L----";

        indent += "|  ";

      }

      string sColor = root - > color ? "RED" : "BLACK";

      cout << root - > data << "(" << sColor << ")" << endl;

      printHelper(root - > left, indent, false);

      printHelper(root - > right, indent, true);

    }

  }

  public:

    RedBlackTree()

  {

    TNULL = new Node;

    TNULL - > color = 0;

    TNULL - > left = nullptr;

    TNULL - > right = nullptr;

    root = TNULL;

  }

  void preorder()

  {

    preOrderTraversal(this - > root);

  }

  void inorder()

  {

    inOrderTraversal(this - > root);

  }

  void postorder()

  {

    postOrderTraversal(this - > root);

  }

  NodePtr searchTree(int k)

  {

    return searchTreeTraversal(this - > root, k);

  }

  NodePtr minimum(NodePtr node)

  {

    while (node - > left != TNULL)

    {

      node = node - > left;

    }

    return node;

  }

  NodePtr maximum(NodePtr node)

  {

    while (node - > right != TNULL)

    {

      node = node - > right;

    }

    return node;

  }

  NodePtr successor(NodePtr x)

  {

    if (x - > right != TNULL)

    {

      return minimum(x - > right);

    }

    NodePtr y = x - > parent;

    while (y != TNULL && x == y - > right)

    {

      x = y;

      y = y - > parent;

    }

    return y;

  }

  NodePtr predecessor(NodePtr x)

  {

    if (x - > left != TNULL)

    {

      return maximum(x - > left);

    }

    NodePtr y = x - > parent;

    while (y != TNULL && x == y - > left)

    {

      x = y;

      y = y - > parent;

    }

    return y;

  }

  void leftRotate(NodePtr x)

  {

    NodePtr y = x - > right;

    x - > right = y - > left;

    if (y - > left != TNULL)

    {

      y - > left - > parent = x;

    }

    y - > parent = x - > parent;

    if (x - > parent == nullptr)

    {

      this - > root = y;

    } else if (x == x - > parent - > left)

    {

      x - > parent - > left = y;

    } else

    {

      x - > parent - > right = y;

    }

    y - > left = x;

    x - > parent = y;

  }

  void rightRotate(NodePtr x)

  {

    NodePtr y = x - > left;

    x - > left = y - > right;

    if (y - > right != TNULL)

    {

      y - > right - > parent = x;

    }

    y - > parent = x - > parent;

    if (x - > parent == nullptr)

    {

      this - > root = y;

    } else if (x == x - > parent - > right)

    {

      x - > parent - > right = y;

    } else

    {

      x - > parent - > left = y;

    }

    y - > right = x;

    x - > parent = y;

  }

  void insert(int key)

  {

    NodePtr node = new Node;

    node - > parent = nullptr;

    node - > data = key;

    node - > left = TNULL;

    node - > right = TNULL;

    node - > color = 1;

    NodePtr y = nullptr;

    NodePtr x = this - > root;

    while (x != TNULL)

    {

      y = x;

      if (node - > data < x - > data)

      {

        x = x - > left;

      } else

      {

        x = x - > right;

      }

    }

    node - > parent = y;

    if (y == nullptr)

    {

      root = node;

    } else if (node - > data < y - > data)

    {

      y - > left = node;

    } else

    {

      y - > right = node;

    }

    if (node - > parent == nullptr)

    {

      node - > color = 0;

      return;

    }

    if (node - > parent - > parent == nullptr)

    {

      return;

    }

    insertFix(node);

  }

  NodePtr getRoot()

  {

    return this - > root;

  }

  void deleteNode(int data)

  {

    deleteNodeHelper(this - > root, data);

  }

  void printTree()

  {

    if (root)

    {

      printHelper(this - > root, "", true);

    }

  }

};

int main()

{

  RedBlackTree bst;

  bst.insert(55);

  bst.insert(40);

  bst.insert(65);

  bst.insert(60);

  bst.insert(75);

  bst.insert(57);

  bst.printTree();

  cout << endl

    <<
    "After deleting" << endl;

  bst.deleteNode(40);

  bst.printTree();

}

Report Error/ Suggestion

Related Posts:

[yuzo_views]



Interview Questions



CopyRight © 2020

CopyRight © 2020