Red-Black Tree Insertion Code

Question

I'm attempting to write an implementation of a red-black tree for my own learning and I've been staring at this for a few days now.

Could anyone help me figure out how I can get the double rotation cases to work correctly? If you spot anything else that sucks while you're looking through the snippets, feel free to make me feel like an idiot.

Your help is appreciated.

Rebalancing Function

int impl_rbtree_rebalance (xs_rbtree_node *node)
{
    check_mem(node);

    xs_rbtree_node *p = node->parent;
    if (!p) return 0;

    if (p->color == BLACK) return 0;

    xs_rbtree_node *gp = p->parent;
    if (!gp) return 0;

    xs_rbtree_node *uncle;
    int is_parent_left_child;

    /* check if parent is left or right child */
    if (p == gp->left) {
        uncle = gp->right;
        is_parent_left_child = 1;
    } else {
        uncle = gp->left;
        is_parent_left_child = 0;
    }

    if (uncle && uncle->color == RED) {

        p->color = uncle->color = BLACK;
        gp->color = RED;

    } else { /* uncle is black */

        if (gp->parent == NULL) return 0;

        if (node == p->left) {

            if (is_parent_left_child == 0) {

                /* Double rotation logic */

            } else {/* parent is left child */

                gp->color = RED;
                gp->left->color = BLACK;

                impl_rbtree_rr(&gp);

            }

        } else { /* node is right child */

            if (is_parent_left_child == 1) {

                /* Double rotation logic */

            } else { /* parent is right child */

                gp->color = RED;
                gp->right->color = BLACK;

                impl_rbtree_rl(&gp);

            }

        }
    }

   return 0;
}

Relevant Functions

xs_rbtree_node *impl_rbtree_node_alloc (xs_rbtree_node *parent, void *val)
{
    xs_rbtree_node *n = malloc(sizeof(xs_rbtree_node));
    n->parent = parent;
    n->val = val;
    n->left = n->right = NULL;
    n->color = (parent == NULL) ? BLACK : RED;
    return n;
}

void rbtree_insert (xs_rbtree_ *tree, void *val)
{
    check_mem(tree);
    check_mem(val);
    tree->root = impl_rbtree_insert(tree->cmp, NULL, tree->root, val);
    tree->root->color = BLACK;
}

xs_rbtree_node *impl_rbtree_insert (xs_tree_cmp cmp, xs_rbtree_node *parent, xs_rbtree_node *node, void *val)
{
    check_mem(cmp);
    check_mem(val);

    if (!node) {

        node = impl_rbtree_node_alloc(parent, val);

    } else if (cmp(node->val, val) < 0) {

        /* node->val < val */
        check_mem(node);
        node->right = impl_rbtree_insert(cmp, node, node->right, val);
        impl_rbtree_rebalance(node->right);

    } else if (cmp(node->val, val) > 0)  {

        /* node->val > val */
        check_mem(node);
        node->left = impl_rbtree_insert(cmp, node, node->left, val);
        impl_rbtree_rebalance(node->left);

    }

    /* ignoring values that are equal */

    return node;
}

Rotation Functions

#include <xs/base/bstree.h>


void impl_tree_rr(xs_tree_node **node)
{
    check_mem(*node);
    check_mem((*node)->left);

    xs_tree_node *k1, *k2;
    k2 = *node;

    k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;

    k1->parent = k2->parent;
    k2->parent = k1;

    *node = k1;
}

void impl_tree_rl(xs_tree_node **node)
{
    check_mem(*node);
    check_mem((*node)->right);

    xs_tree_node *k1, *k2;
    k2 = *node;

    k1 = k2->right;

    k2->right = k1->left;

    k1->left = k2;

    k1->parent = k2->parent;
    k2->parent = k1;

    *node = k1;
}

void impl_tree_drr(xs_tree_node **node)
{
    check_mem(*node);
    impl_tree_rl(&((*node)->left));
    impl_tree_rr(node);
}

void impl_tree_drl(xs_tree_node **node)
{
    check_mem(*node);
    impl_tree_rr(&((*node)->right));
    impl_tree_rl(node);
}

RBT Definitions

typedef struct xs_rbtree_node xs_rbtree_node;
typedef struct xs_rbtree_ xs_rbtree_;

typedef enum { RED, BLACK  } impl_rbtree_color;

struct xs_rbtree_node {

    xs_rbtree_node      *left;
    xs_rbtree_node      *right;
    xs_rbtree_node      *parent;
    void                *val;
    impl_rbtree_color   color;

};

struct xs_rbtree_ {

    xs_rbtree_node   *root;
    xs_tree_cmp    cmp;

};

Answer 1

Double rotation is kind of tricky in Red Black trees when compared to AVL trees, the reason being the existence of parent pointers which exist in RB trees. While we rotate the trees we need to adjust the parent pointers too. I will to demonstrate it with an example. The tree below is the initial tree

                     20 
                  /      \ 
                10        30
              /   \          
            3      15      
                 /    \
                12    18

And here goes the right rotated one

                     10 
                  /      \ 
                3        20
                        /   \        
                      15    30    
                    /    \
                   12    18

We observe 2 things there. 1. The root got changed. 2. The parent pointers for 3 nodes got changed ( 10, 20, 15 ) ie. for new root, old root and right child of new root. This will be true for all right rotation cases. This is to make sure that that, the in order traversal remains intact after rotation happens.

Now see how we rotate step by step.

public Node rotateRight() {
        if(root.left == null) {
            System.out.println("Cannot be rotated Right");
        } else {
            Node newRoot = root.left; // Assign new root.
            Node orphaned = newRoot.right; // Store ref to the right child of new root.

            newRoot.parent = root.parent; // new root parent point to old root parent.
            root.parent = newRoot; // new root becomes parent of old root.

            newRoot.right = root;  // old root becomes right child of new root
            root.left = orphaned;
            if (orphaned != null) {
                orphaned.parent = root;
            }
            root = newRoot;
        }
        return root;
    }

Try doing this on paper couple of times, then it will look simpler. Hope this helps.

Coming back to RB Trees. The above implementation will be applied to both the rotations we do in the balancing process. ( Let us take right right case)

When we have 3 generations of nodes, a grandfather, a father and a child which got inserted. 1. When we have RR or LL config, do not swap colors 2. With RL and LR, we rotate the grandfather we swap the colour of grandpa and father, but when rotating the parent we do not try to swap colours. Intent is just to bring them to RR or LL configs.

   a. We need to see if the grandpa is right or left child of its 
      parent and assign the root accordingly.
   b. If the grandpa has no parent means we are doing rotation at the level of tree's root, then we reassign the root of the tree.

Snippet for my implementation of RB tree.

temp is the new node which is added.
    // if new node is the right child AND parent is right child
    else if(temp.parent.right == temp && grandPa!=null && grandPa.right == temp.parent) {
                                // If becomes a right-right case
                                Boolean isLeft = isLeftChild(grandPa);
                                if(isLeft == null) {
                                // Grandpa has no parent, reassign root.
                                    root = rotateLeft(grandPa,true);
                                }
                                else if(isLeft) {
                                    grandPa.parent.left = rotateLeft(grandPa,true);
                                } else {
                                    grandPa.parent.right = rotateLeft(grandPa,true);
                                }
                            }