LLRBTree's code

RBTree.cpp

#include <iostream>

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

template <typename Key,typename Value> class RBTree
{
private:
  /* data */
  struct Node
  {
    Key key;
    Value value;
    bool color;
    Node *left = nullptr;
    Node *right = nullptr;
    Node();
    Node(Key k, Value val, bool col):key(k),value(val),color(col){}
  };
  Node *root = nullptr;
  const Value UNDEF_VAL = (Value) 0;

  Node *min(Node *h)
  {
    if (!h->left)
    {
      return h;
    }
    return min(h->left);
  }
  Node *max(Node *h)
  {
    if (!h->right)
    {
      return h;
    }
    return max(h->right);
  }
  Node *rotate_left(Node *h)
  {
    Node *x = h->right;
    h->right = x->left;
    x->left = h;
    x->color = h->color;
    h->color = RED;
    return x;
  }
  Node *rotate_right(Node *h)
  {
    Node *x = h->left;
    h->left = x->right;
    x->right = h;
    x->color = h->color;
    h->color = RED;
    return x;
  }
  void flip_colors_black(Node *h)
  {
    h->left->color = BLACK;
    h->right->color = BLACK;
    h->color = RED;
  }
  void flip_colors_red(Node *h)
  {
    h->left->color = RED;
    h->right->color = RED;
    h->color = BLACK;
  }
  bool is_red(Node *x)
  {
    if (x == nullptr)
    {
      return false;
    }
    return x->color;
  }
  Value find(Node *h, Key k)
  {
    if (!h)
    {
      return UNDEF_VAL;
    }
    if (h->key == k)
    {
      return h->value;
    }
    if (h->key > k)
    {
      return find(h->left, k);
    }
    return find(h->right, k);
  }
  Node *balance(Node *h)
  {
    if (is_red(h->right) && !is_red(h->left))
    {
      h = rotate_left(h);
    }
    if (is_red(h->left) && is_red(h->left->left))
    {
      h = rotate_right(h);
    }
    if (is_red(h->left) && is_red(h->right))
    {
      flip_colors_black(h);
    }
    return h;
  }
  Node * put(Node *h, Key k, Value val)
  {
    if (!h)
    {
      return new Node(k, val, RED);
    }
    if (k < h->key)
    {
      h->left = put(h->left, k, val);
    }
    else if (k > h->key)
    {
      h->right = put(h->right, k, val);
    }
    else
    {
      h->value = val;
    }
    return balance(h);
  }
  Node* move_red_left(Node *h)
  {
    flip_colors_red(h);
    if (is_red(h->right->left) )
    {
      h->right = rotate_right(h->right);
      h = rotate_left(h);
    }
    return h;
  }
  Node* delete_min(Node *h)
  {
    if (!h->left)
    {
      delete h;
      return nullptr;
    }
    if (!is_red(h->left) && !is_red(h->left->left))
    {
      move_red_left(h);
    }
    h->left = delete_min(h->left);
    return balance(h);
  }
  void move_red_right(Node *h)
  {
    flip_colors_red(h);
    if (is_red(h->left->left))
    {
      h = rotate_right(h);
    }
    return h;
  }
  Node* delete_max(Node * h)
  {
    if (!h->right)
    {
      Node* temp = h->left;
      delete h;
      return temp;
    }
    if (!is_red(h->right) && !is_red(h->right->right))
    {
      move_red_right(h);
    }
    h->right = delete_max(h->right);
    return balance(h);
  }
  Node *erase(Node *h, Key k)
  {
    if (h->key == k)
    {
      if (!h->left)
      {
        if (!h->right)
        {
          delete h;
          return nullptr;
        }
        else
        {
          Node *temp = h->right;
          delete h;
          return temp;
        }
      }
      else
      {
        if (!h->right)
        {
          Node *temp = h->left;
          delete h;
          return temp;
        }
        else
        {
          Node *min_node = min(h->right);
          std::swap(min_node->key, h->key);
          std::swap(min_node->value, h->value);
          std::swap(min_node->color, h->color);
          delete_min(h->right);
          return h;
        }
      }
    }
    else if (k > h->key)
    {
      if (!h->right)
      {
        return h;
      }
      if (!is_red(h->right) && !is_red(h->right->right))
      {
        h = move_red_right(h);
      }
      h = erase(h->right, k);
    }
    else
    {
      if (!h->left)
      {
        return h;
      }
      if (!is_red(h->left) && !is_red(h->left))
      {
        h = move_red_left(h);
      }
      h = erease(h->left, k);
    }
    return balance(h);
  }
  void destory(Node *h)
  {
    if (h->left)
    {
      destory(h->left);
    }
    if (h->right)
    {
      destory(h->right);
    }
    delete h;
  }
  size_t depth(Node *h,size_t dep)
  {
    if (!h)
    {
      return dep;
    }
    return std::max(depth(h->left,dep+1), depth(h->right,dep+1));
  }

public:
  RBTree () = default;
  RBTree (const RBTree &) = default;
  RBTree (Value undef_val):UNDEF_VAL(undef_val){}
  virtual ~RBTree ()
  {
    if (!empty())
    {
      destory(root);
    }
  };
  bool empty()
  {
    return !root;
  }
  Value get(Key k)
  {
    return find(root, k);
  }
  void put(Key k,Value val)
  {
    root = put(root, k, val);
  }
  void delete_min()
  {
    if (empty())
    {
      return;
    }
    if (!is_red(root->left) && !is_red(root->right))
    {
      root->color = RED;
    }
    root = delete_min(root);
  }
  void delete_max()
  {
    if (empty())
    {
      return;
    }
    if (!is_red(root->left) && !is_red(root->right))
    {
      root->color = RED;
    }
    root = delete_max(root);
  }
  void erease(Key k)
  {
    if (empty())
    {
      return;
    }
    if (!is_red(root->left) && !is_red(root->right))
    {
      root->color = RED;
    }
    root = erease(root, k);
    if (!empty())
    {
      root->color = BLACK;
    }
  }
  size_t depth()
  {
    return depth(root,0);
  }
};