Skip to content

Instantly share code, notes, and snippets.

@declank

declank/red_black_tree_insertion.cpp

Created December 7, 2014 16:23
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save declank/6275656687eafe22a1e8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save declank/6275656687eafe22a1e8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. declank created this gist Dec 7, 2014.
    303 changes: 303 additions & 0 deletions red_black_tree_insertion.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,303 @@
    #include <iostream>
    #include <string>
    using namespace std;

    typedef bool NodeColor;
    const NodeColor RED = false;
    const NodeColor BLACK = true;

    inline void test(bool expression, string message) {
    cout << message << (expression ? "\tTRUE" : "\tFALSE") << '\n';
    }

    template<typename T>
    struct RedBlackTreeNode {
    RedBlackTreeNode() { left = NULL; right = NULL; parent = NULL; color = RED; }
    RedBlackTreeNode(NodeColor c, T i) : color(c), item(i) { left = NULL; right = NULL; parent = NULL; }
    RedBlackTreeNode(NodeColor c, T i, RedBlackTreeNode* p) : color(c), item(i), parent(p) { left = NULL; right = NULL; }
    NodeColor color;
    T item;
    RedBlackTreeNode *left, *right, *parent;
    inline RedBlackTreeNode* grandparent() {
    if(parent)
    return parent->parent;
    else
    return NULL;
    }
    inline RedBlackTreeNode* uncle() {
    RedBlackTreeNode* g = grandparent();
    if(g == NULL) {
    // If there is no grandparent, there is no uncle
    return NULL;
    } else if(this->parent == g->left) {
    return g->right;
    } else {
    return g->left;
    }
    }

    };

    template<typename T>
    struct RedBlackTreeNodes {
    RedBlackTreeNode<T> nodes[];
    size_t number_of_nodes;
    };

    template<typename T>
    struct RedBlackTree {
    RedBlackTree() : root(NULL) {}
    void Insert(T item);
    bool VerifyTree() const;
    bool VerifyColors(RedBlackTreeNode<T>* node) const;
    bool VerifyOrder(RedBlackTreeNode<T>* node) const;


    RedBlackTreeNode<T>* root;

    };

    template<typename T>
    void RedBlackTree<T>::Insert(T item) {
    if (root == NULL) {
    root = new RedBlackTreeNode<T>(BLACK, item);
    return;
    } else {
    RedBlackTreeNode<T>* current_node = root;
    while(true) {
    if(item < current_node->item && current_node->left != NULL)
    current_node = current_node->left;
    else if(item >= current_node->item && current_node->right != NULL)
    current_node = current_node->right;
    else
    break;
    }
    RedBlackTreeNode<T>* new_node = new RedBlackTreeNode<T>(RED, item, current_node);
    if(item < current_node->item)
    current_node->left = new_node;
    else
    current_node->right = new_node;
    // If the parent is black then the tree is valid
    // If it's red then we need to move up the tree restoring the red-black property
    // starting with the new node (i.e. remove red-red violations)
    if(current_node->color == BLACK) {
    return;
    } else {
    current_node = new_node;
    while(current_node->parent != NULL) { // Fix up the tree
    // If the parent is black we don't need to check for violations
    // Move up one
    if(current_node->parent->color == BLACK) {
    current_node = current_node->parent;
    continue;
    }
    RedBlackTreeNode<T>* uncle = current_node->uncle();
    if(uncle != NULL && uncle->color == RED) {
    uncle->color = BLACK;
    current_node->parent->color = BLACK;
    current_node->grandparent()->color = RED;
    current_node = current_node->grandparent();
    } else {
    // If there's a zigzag, a double rotation is necessary, otherwise, single
    /*
    G
    / \
    P U
    \
    C
    */
    RedBlackTreeNode<T>* p = current_node->parent;
    RedBlackTreeNode<T>* g = current_node->grandparent();

    if(p == g->left) {
    if(current_node == p->right)
    LeftRotate(p);
    current_node = RightRotate(g);
    SwapColors(current_node, current_node->right);
    }
    else {
    if(current_node == p->left)
    RightRotate(p);
    current_node = LeftRotate(g);
    SwapColors(current_node, current_node->left);
    }
    }
    }

    root = current_node;
    root->color = BLACK;
    }
    }
    }

    template<typename T>
    RedBlackTreeNode<T>* LeftRotate(RedBlackTreeNode<T>* top_node) {
    cout << "Left rotating...\n";
    // Using the following notation:
    // Root is the parent node of the rotation (e.g. this pointer)
    // Pivot is the node that will become the new parent
    // Based on https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Tree_rotation.html

    // Rotation side = left; opposite side = right

    RedBlackTreeNode<T> *pivot = top_node->right;
    top_node->right = pivot->left;
    pivot->left = top_node;

    // Fix parents (see red lines on right side of diagram)
    // New top_node/pivot
    if(top_node->parent != NULL && top_node->parent->left == top_node) {
    top_node->parent->left = pivot;
    }
    else if(top_node->parent != NULL && top_node->parent->right == top_node){
    top_node->parent->right = pivot;
    }
    pivot->parent = top_node->parent;

    // old top_node's parent is pivot
    top_node->parent = pivot;
    // opposite side of old top_node's parent is top_node
    if(top_node->right != NULL)
    top_node->right->parent = top_node;

    // return new top node
    return pivot;
    }

    template<typename T>
    RedBlackTreeNode<T>* RightRotate(RedBlackTreeNode<T>* top_node) {
    cout << "Right rotating...\n";
    // Same as above but with swapped sides

    RedBlackTreeNode<T> *pivot = top_node->left;
    top_node->left = pivot->right;
    pivot->right = top_node;


    if(top_node->parent != NULL && top_node->parent->left == top_node) {
    top_node->parent->left = pivot;
    }
    else if(top_node->parent != NULL && top_node->parent->right == top_node){
    top_node->parent->right = pivot;
    }
    pivot->parent = top_node->parent;
    top_node->parent = pivot;
    if(top_node->left != NULL)
    top_node->left->parent = top_node;

    // return new top node
    return pivot;

    }

    template<typename T>
    inline void SwapColors(RedBlackTreeNode<T>* a, RedBlackTreeNode<T>* b) {
    cout << "Swapping colours.\n";
    NodeColor temp = a->color;
    a->color = b->color;
    b->color = temp;
    }

    template<typename T>
    bool RedBlackTree<T>::VerifyTree() const {
    // If tree has no root, then return as valid
    if(!root)
    return true;

    // If root is red, it's invalid
    if(root->color == RED)
    return false;

    // Every red node has two black child nodes (or NULL)
    if(VerifyColors(root) == false)
    return false;

    // Verify that the nodes are in-order correctly by number
    if(VerifyOrder(root) == false)
    return false;

    return true;
    }

    template<typename T>
    bool RedBlackTree<T>::VerifyColors(RedBlackTreeNode<T>* node) const {
    // Base case
    if(!node)
    return true;

    // Make sure if the node is red, there are no red child nodes
    if(node->color == RED
    && (
    (node->left && node->left->color == RED) // If left is red
    || (node->right && node->right->color == RED) // Or if right is red
    )) {
    return false;

    }

    return VerifyColors(node->left) && VerifyColors(node->right);
    }

    template<typename T>
    bool RedBlackTree<T>::VerifyOrder(RedBlackTreeNode<T>* node) const {
    // Base case
    if(!node)
    return true;

    if(node->left && node->left->item >= node->item) {
    return false;
    }

    if(node->right && node->right->item < node->item) {
    return false;
    }

    return VerifyOrder(node->left) && VerifyOrder(node->right);
    }



    int main() {
    RedBlackTree<int> rbt;
    rbt.Insert(15);
    test(rbt.root->item == 15 && rbt.root->color == BLACK, "Root node is 15 and black in colour.");
    rbt.Insert(45);
    test(rbt.root->right->item == 45 && rbt.root->right->color == RED, "45 in correct position and colour.");
    rbt.Insert(29);
    test(rbt.root->left->item == 15 && rbt.root->left->color == RED, "15 in correct position and colour.");
    test(rbt.root->right->item == 45 && rbt.root->right->color == RED, "45 in correct position and colour.");
    test(rbt.root->item == 29 && rbt.root->color == BLACK, "29 in correct position and colour.");
    rbt.Insert(10);
    test(rbt.root->left->item == 15 && rbt.root->left->color == BLACK, "15 in correct position and colour.");
    test(rbt.root->right->item == 45 && rbt.root->right->color == BLACK, "45 in correct position and colour.");
    test(rbt.root->item == 29 && rbt.root->color == BLACK, "29 in correct position and colour.");
    test(rbt.root->left->left->item == 10 && rbt.root->left->left->color == RED, "10 in correct position and colour.");
    rbt.Insert(5);
    test(rbt.root->left->right->item == 15 && rbt.root->left->right->color == RED, "15 in correct position and colour.");
    test(rbt.root->right->item == 45 && rbt.root->right->color == BLACK, "45 in correct position and colour.");
    test(rbt.root->item == 29 && rbt.root->color == BLACK, "29 in correct position and colour.");
    test(rbt.root->left->item == 10 && rbt.root->left->color == BLACK, "10 in correct position and colour.");
    test(rbt.root->left->left->item == 5 && rbt.root->left->left->color == RED, "15 in correct position and colour.");

    if(rbt.VerifyTree()) {
    cout << "Red black tree satisifies properties.\n";
    } else {
    cout << "Red black tree is broken!!!\n";
    }

    rbt.Insert(3);
    rbt.Insert(81);
    rbt.Insert(61);
    rbt.Insert(41);

    if(rbt.VerifyTree()) {
    cout << "Red black tree satisifies properties.\n";
    } else {
    cout << "Red black tree is broken!!!\n";
    }

    return 0;
    }