TutorialStudyMite
Red Black Tree Deletion
SSonal Moga10 min read
Beginner friendly
Track completion, mastery, and revision.
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:
- 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.
- 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.
- 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 TNULL;
void initializeNULLNode(NodePtr node, NodePtr parent)
{
}
void preOrderTraversal(NodePtr node)
{
}
void inOrderTraversal(NodePtr node)
{
}
void postOrderTraversal(NodePtr node)
{
}
NodePtr searchTreeTraversal(NodePtr node, int key)
{
}
void deleteFix(NodePtr x)
{
}
void rbTransplant(NodePtr u, NodePtr v)
{
}
void deleteNodeHelper(NodePtr node, int key)
{
}
void insertFix(NodePtr k)
{
}
void printHelper(NodePtr root, string indent, bool last)
{
}
public:
{
}
void preorder()
{
}
void inorder()
{
}
void postorder()
{
}
NodePtr searchTree(int k)
{
}
NodePtr minimum(NodePtr node)
{
}
NodePtr maximum(NodePtr node)
{
}
NodePtr successor(NodePtr x)
{
}
NodePtr predecessor(NodePtr x)
{
}
void leftRotate(NodePtr x)
{
}
void rightRotate(NodePtr x)
{
}
void insert(int key)
{
}
NodePtr getRoot()
{
}
void deleteNode(int data)
{
}
void printTree()
{
}
};
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
bst.deleteNode(40);
bst.printTree();
}Finished reading?