【C++高阶(四)】红黑树深度剖析--手撕红黑树!

为啥满足了以上性质的红黑树就一定
能做到最长路径最多是最短路径的二倍?
下面我画一个极限情况来分析一下!

综上所述,红黑树的效率虽然比
AVL树差一点,但是总体来说红黑树胜!

enum Colour
{
  RED,
    BLACK
};
template<class K,class V>
struct RBTreeNode
{
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    ,_col(RED)
  {}
  RBTreeNode<K, V>* _left;
  RBTreeNode<K, V>* _right;
  RBTreeNode<K, V>* _parent;
  pair<K, V> _kv; 
  Colour _col;
};
template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
private:
  Node* _root = nullptr;
};

bool insert(const pair<K, V>& kv)//第一步:按照二叉搜索树的方式插入值
{
  if (_root == nullptr)
  {
    _root = new Node(kv);
    _root->_col = BLACK;
    return true;
  }
  Node* cur = _root;
  Node* parent = nullptr;
  while (cur)
  {
    if (cur->_kv.first < kv.first)
    {
      parent = cur;
      cur = cur->_right;
    }
    else if (cur->_kv.first > kv.first)
    {
      parent = cur;
      cur = cur->_left;
    }
    else return false;
  }
  cur = new Node(kv);
  if (parent->_kv.first < kv.first)
    parent->_right = cur;
  else
    parent->_left = cur;
  //此时new出来的节点的parent还指向空
  cur->_parent = parent;
  ///前面的过程和AVL树一致
}

综上所述,插入红色更优!
换句话说,你犯错肯定宁愿犯轻一点
的错误被妈妈打一顿,也不愿意犯很重
的错直接被家族除名了对吧[doge]

//走到这一步后,就已经找到cur和parent了!
while (parent && parent->_col == RED)//当parent为黑就不用往上更新了
{
  if (parent == _root)
  {
    _root->_col = BLACK;
    break;
  }
  Node* grandf = parent->_parent;
  assert(grandf);
  assert(grandf->_col == BLACK);
  Node* uncle = nullptr;
  if (parent == grandf->_left)//判断叔叔在par的左还是右
    uncle = grandf->_right;
  else uncle = grandf->_left;
  if (uncle == nullptr || uncle->_col == BLACK)//uncle为空或为黑有四种情况来变色＋旋转
  {
    if (parent == grandf->_left && cur == parent->_left)//左左->右旋＋变色
    {
      RotateR(grandf);
      parent->_col = BLACK;
      grandf->_col = RED;
      break;
    }
    else if (parent == grandf->_right && cur == parent->_right)//右右->左旋+变色
    {
      RotateL(grandf);
      parent->_col = BLACK;
      grandf->_col = RED;
      break;
    }
    else if (parent == grandf->_left && cur == parent->_right)//左右->先左旋再右旋再变色
    {
      RotateL(parent);
      RotateR(grandf);
      cur->_col = BLACK;
      grandf->_col = RED;
      break;
    }
    else if (parent == grandf->_right && cur == parent->_left)//右左->先右旋再左旋再变色
    {
      RotateR(parent);
      RotateL(grandf);
      cur->_col = BLACK;
      grandf->_col = RED;
      break;
    }
  }
  else if (uncle && uncle->_col == RED)//叔叔为红,直接变色,不旋转
  {
    parent->_col = BLACK;
    uncle->_col = BLACK;
    grandf->_col = RED;
    cur = grandf;
    parent = cur->_parent;//将parent更新后往上传!
  }
  _root->_col = BLACK;
}