TutorialStudyMite
Red Black Tree Insertion
SSonal Moga7 min read
Beginner friendly
Track completion, mastery, and revision.
What is Red Black Tree ?
Insertion in Red Black Tree
Deletion in Red Black Tree
Red Black Tree Insertion
Insertion operation in a Red-black tree is quite similar to a standard binary tree insertion, it begins by adding a node at a time and by coloring it red.
The main difference that we can point out is that in a binary search tree, a new node is added as a leaf but in red-black tree leaf nodes don’t contain any info, so a new node replaces the existing leaf and then has two black leaves of its own added.
# Program to implement 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 searchTree(NodePtr node, int key)
{
}
void rbTransplant(NodePtr u, NodePtr v)
{
}
void insertFix(NodePtr k)
{
}
void printTree(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 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();
}Finished reading?