title: Red-black tree join algorithm implementation
body: <p>I've been trying to implement join operation on RB trees recently according to the pseudocode provided on the <a href="https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Set_operations_and_bulk_operations" rel="nofollow noreferrer">Wikipedia page</a>. I recreated the pseudocode so that my code is almost identical, even with the same variable names but it still doesn't work. The join operation places the nodes in correct places but the recoloring and rotations just either don't work at all or break the tree. Here's an example starting tree:</p>
  <p><a href="https://i.stack.imgur.com/cFtKk.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cFtKk.png" alt="enter image description here" /></a></p>
  <p>Then after joining it on key 1000 with single node with key 1001 the result is this:</p>
  <p><a href="https://i.stack.imgur.com/fgIYf.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/fgIYf.png" alt="enter image description here" /></a></p>
  <p>Both nodes have been inserted correctly but double red node appeared in tree and wasn't fixed.
  In this scenario the function joinRightRB is called, which according to Wikipedia should rotate the tree when right child is red and right child of the right child is red, which is something that doesn't happen here. However changing it to left child of right child fixes only some scenarios and breaks others so I can't tell what's wrong here and I'm sure it's more likely that I'm wrong, not Wikipedia. As I said previously my code is almost an identical representation of the pseudocode:</p>
  <pre><code>struct RBTree* join(struct RBTree *left, struct RBTree *right, void *key, int (*compare)(void *, void *), size_t key_size, size_t value_size)
  {
      if(black_height(left-&gt;root) &gt; black_height(right-&gt;root)){
          struct Node* t_prim = __joinRight(left-&gt;root, key, right-&gt;root);
  
          if(t_prim-&gt;color == RED &amp;&amp; t_prim-&gt;right-&gt;color == RED) {
              t_prim-&gt;color = BLACK;
          }
  
          return create_tree(t_prim, compare, key_size, value_size);
      } else if(black_height(right-&gt;root) &gt; black_height(left-&gt;root)) {
          struct Node* t_prim = __joinLeft(left-&gt;root, key, right-&gt;root);
  
          if(t_prim-&gt;color == RED &amp;&amp; t_prim-&gt;left-&gt;color == RED) {
              t_prim-&gt;color = BLACK;
          }
  
          return create_tree(t_prim, compare, key_size, value_size);
      } else if(left-&gt;root-&gt;color == BLACK &amp;&amp; right-&gt;root-&gt;color == BLACK) {
          return create_tree(__create_node(left, key, RED, right), compare, key_size, value_size);
      } else {
          return create_tree(__create_node(left, key,  BLACK, right), compare, key_size, value_size);
      }
  }
  
  struct Node *__joinRight(struct Node *t_l, void *k, struct Node *t_r)
  {
      if(black_height(t_l) == black_height(t_r)) {
          return __create_node(t_l, k, RED, t_r);
      } else {
          struct Node* l_prim = t_l-&gt;left;
          struct Node* r_prim = t_l-&gt;right;
          void* k_prim = t_l-&gt;key;
          enum color_t c_prim = t_l-&gt;color;
  
          struct Node* t_prim = __create_node(l_prim, k_prim, c_prim, __joinRight(r_prim, k, t_r));
  
          if (c_prim == BLACK &amp;&amp; t_prim-&gt;right-&gt;color == RED &amp;&amp; t_prim-&gt;right-&gt;right-&gt;color == RED) {
              t_prim-&gt;right-&gt;right-&gt;color = BLACK;
              rotateTree(NULL, t_prim, LEFT);
          }
  
          return t_prim;
      }
  }
  
  struct Node *__joinLeft(struct Node *t_l, void *k, struct Node *t_r)
  {
      if(black_height(t_l) == black_height(t_r)) {
          return __create_node(t_l, k, RED, t_r);
      } else {
          struct Node *l_prim = t_r-&gt;left;
          struct Node *r_prim = t_r-&gt;right;
          void *k_prim = t_r-&gt;key;
          enum color_t c_prim = t_r-&gt;color;
  
          struct Node* t_prim = __create_node(__joinLeft(t_l, k, l_prim), k_prim, c_prim, r_prim);
  
          if (c_prim == BLACK &amp;&amp; t_prim-&gt;left-&gt;color == RED &amp;&amp; t_prim-&gt;left-&gt;left-&gt;color == RED) {
              t_prim-&gt;left-&gt;left-&gt;color = BLACK;
              rotateTree(NULL, t_prim, RIGHT);
          }
  
          return t_prim;
      }
  }
  
  struct Node* rotateTree(struct RBTree* t, struct Node* p, enum direction_t direction)
  {
      struct Node* g = p-&gt;parent;
      struct Node* s = direction == RIGHT ? p-&gt;left : p-&gt;right;
      struct Node* c = &amp;nil;
  
      assert(p != &amp;nil);
  
      c = direction == RIGHT ? p-&gt;right : p-&gt;left;
  
      if(direction == RIGHT) {
          p-&gt;left = c;
      } else {
          p-&gt;right = c;
      }
  
      if(c != &amp;nil) {
          c-&gt;parent = p;
      }
  
      if(direction == RIGHT) {
          s-&gt;right = p;
      } else {
          s-&gt;left = p;
      }
  
      p-&gt;parent = s;
  
      s-&gt;parent = g;
  
      if(g != &amp;nil) {
          if(p == g-&gt;right) {
              g-&gt;right = s;
          } else {
              g-&gt;left = s;
          }
      }
  
      return s;
  }
  
  unsigned black_height(struct Node* node)
  {
      struct Node* current = node;
      unsigned b_height = 0;
  
      while(current != &amp;nil) {
          if(current-&gt;color == BLACK) {
              ++b_height;
          }
  
          if(current-&gt;left != &amp;nil) {
              current = current-&gt;left;
          } else {
              current = current-&gt;right;
          }
      }
  
      return b_height;
  }
  </code></pre>
  <p>Function __create_node only creates a node with right and left child, color and key provided as parameters (parent is null). The rotate function is a mess because I've tried to replicate the function from psuedocode as closely as possible. I've been trying to figure out what's wrong for few days now and I'm all out of ideas.</p>