红黑树

作者: ticks | 来源:发表于2019-09-29 16:23 被阅读0次

红黑树

红黑树的介绍

红黑树是一种特殊的二叉搜索树, 每个节点多出了一个颜色属性,并满足一下 5 条性质

每个节点或者是黑色，或者是红色
根节点是黑色的
空的叶子节点是黑色的
红色节点的孩子是黑色的
每个节点到叶子的路径包含相同的黑色节点

红黑树的性质

引理

n 个内部节点的红黑树最大高度为 $2log_2(n+1)$

证明

先证以 x 为根的子树最少有 $2^{bh(x)}-1$ 个内部节点.

当 x 为空的叶子节点时, 以 x 为根的子树有 $2^0-1=0$ 个内部节点, 满足.

当 x 有两个内部孩子节点时, 孩子节点的黑色高度(black-height)为 bh(x) (/* 当 x 为红色节点/) 或者为 bh(x) -1 (/ 当 x 为黑色节点 */)

所以 x 的节点数目 $n\geqslant 2^{bh(x)-1}-1+2^{bh(x)-1}-1+1=2^{bh(x)}-1$

又 $bh(x)\geqslant h/2$ , 所以 $n\geqslant 2^{h/2}-1$

所以 $h\leqslant 2log_2(n+1)$

旋转

左旋

x 右孩子 y 的左孩子成为 x 的右孩子
x 成为 y 的左孩子
y 取代 x 的位置

右旋

x 左孩子 y 的右孩子成为 x 的左孩子
x 成为 y 的右孩子
y 取代 x 的位置

插入

根据 key 值的大小插入新的节点 z, 颜色为红色
若插入的是根节点, 只需要把根设为黑色
若插入节点 z 的 parent 是红色的
i. z 的 uncle 是红色的, 将 parent 和 uncle 设为黑色, grandparent 设为红色, 将 grandparent 当成插入节点, 重新判断
ii. z 的 uncle 是黑色的(tip. T.nil 也是黑色的), 将 z 到 uncle 的路径调为人形, parent 设为黑色 grandparent 设为红色, 将 grandparent 向 uncle 方向旋转

template <typename T>
void RBTree<T>::leftRoate(RBNode<T>* x)
{
    RBNode<T>* y = x->right;
    x->right     = y->left;
    if (x->right) x->right->parent = x;
    y->parent = x->parent;
    if (!y->parent)
        root = y;
    else if (y->parent->left == x)
        y->parent->left = y;
    else
        y->parent->right = y;
    y->left   = x;
    x->parent = y;
}

template <typename T>
void RBTree<T>::rightRoate(RBNode<T>* x)
{
    RBNode<T>* y = x->left;
    x->right     = y->left;
    if (y->left) y->left->parent = y;
    y->parent = x->parent;
    if (!y->parent)
        root = y;
    else if (y->parent->left == x)
        y->parent->left = y;
    else
        y->parent->right = y;
    y->right  = x;
    x->parent = y;
}

template <typename T>
void RBTree<T>::insert(T key)
{
    RBNode<T>* z  = new RBNode<T>(RED, key, nullptr, nullptr, nullptr);
    RBNode<T>* px = root;
    RBNode<T>* py = nullptr;
    while (root)
    {
        py = px;
        if (key < px->key)
            px = px->left;
        else
            px = px->right;
    }
    z->parent = py;
    if (!py)
        root = z;
    else if (z->key < py->key)
        py->left = z;
    else
        py->right = z;
    insertFix(z);
}

template <typename T>
void RBTree<T>::insertFix(RBNode<T>* z)
{
    while (z->parent && z->parent->color == RED)
    {
        if (z->parent == z->parent->parent->left)
        {
            RBNode<T>* uncle = z->parent->parent->right;
            if (uncle && uncle->color == RED)
            {
                uncle->color             = BLACK;
                z->parent->color         = BLACK;
                z->parent->parent->color = RED;
                z                        = z->parent->parent;
            }
            else if (z == z->parent->right)
            {
                z = z->parent;
                leftRoate(z);
            }
            z->parent->color         = BLACK;
            z->parent->parent->color = RED;
            rightRoate(z->parent->parent);
        }
        else
        {
            RBNode<T>* uncle = z->parent->parent->left;
            if (uncle && uncle->color == RED)
            {
                uncle->color             = BLACK;
                z->parent->color         = BLACK;
                z->parent->parent->color = RED;
                z                        = z->parent->parent;
            }
            else if (z == z->parent->left)
            {
                z = z->parent;
                rightRoate(z);
            }
            z->parent->color         = BLACK;
            z->parent->parent->color = RED;
            leftRoate(z->parent->parent);
        }
    }
    root->color = BLACK;
}

没有父指针的红黑树插入

插入时需要回返节点来进行修正, 若不提供父指针就需要栈来保存插入时的路径

RB-INSERT(T, z)
    y = T.nil
    x = T.root
    stack St
    while x ≠ T.nil
        y = x
        if z.key < x.key
            x = x.left
        else
            x = x.right
        St.push(y)
    if y == T.nil
        T.root = z
    elseif z.key < y.key
        y.left = z
    else 
        y.right = z
    z.left = T.nil
    z.right = T.nil
    z.color = RED
    RB-INSERT-FIXUP(T, z, St)

RB-INSERT-FIXUP(T, z, St)
    while z ≠ T.root and (p = St.pop()).color == RED // pop 是 top, pop 2合1
        gp = St.pop()
        if p == gp.left
            uncle = gp.right
            if uncle.color == RED
                uncle.color = BLACK
                p.color = BLACK
                gp.color = RED
                z = gp
            else
                if z = p.right
                    leftRoate(T, p)
                    swap(z, p)
                p.color = BLACK
                gp.color = RED
                rightRoate(gp)
                break
        else (same as before clause with "left" and "right" exchanged)
    T.root.color = BLACK

删除

子树替换的辅助程序

  template <typename T>
  void RBTree<T>::transSubtree(RBNode<T>* src, RBNode<T>* dic)
  {
    if (!src->parent)
      root = dic;
    else if (src == src->parent->left)
      src->parent->left = dic;
    else
      src->parent->right = dic;
    if (dic) dic->parent = src->parent;
  }

删除节点 z

z 的孩子小于 2 个. y = z, x = z->child
z 有 2 个孩子. 两个指针 x, y; y 指向 z 的后继. x 总是指向 y 的替代者 x = y->right. 保存 y 的原始颜色
y = successor(z), x = y->right

  template <typename T>
  void RBTree<T>::remove(RBNode<T>* z)
  {
    if (!z->left)
    {
      transSubtree(z, z->right);
    }
    else if (!z->right)
    {
      transSubtree(z, z->left);
    }
    else
    {
      RBNode<T>* y = successor(z);
      RBNode<T>* x = y->right;

      RBColor yOriginalCol = y->color;
      if (y->parent == z)
        x->parent = y;
      else
      {
        transSubtree(y, x);
        y->right         = z->right;
        y->right->parent = y;
      }
      transSubtree(z, y);
      y->left         = z->left;
      y->left->parent = y;
      delete z;
      if (yOriginalCol == BLACK) removeFix(x);
    }
  }

修复红黑树, 使其满足 5 条性质

y 的原始颜色是红色的, 则红黑树的性质仍然保持

树中黑高不变, 保持性质 5
y 在新位置的颜色是 z 的颜色所以新位置, y 不会破坏性置 4. 若 y 是红色的, 则 x 是黑色的, x 替代 y 也不会破坏性置 4
明显根结点的颜色不会变, 所有结点没有多出或少颜色, 空叶子节点的颜色也不会变化. 所以性质 1,2,3 保持

y 是黑色的, 给 x 添加一个黑色

有可能产生的问题

编号	问题	解决办法
1	若 x 是根,违返了性质 1, 2	只保留 x 的一个黑色 `x.color = BLACK`
2	若 x 是红黑色的违返性质 1	去除 x 的红色 `x.color = BLACK`
3	若 x 不是根且是双黑色的, 违返了性质 1	下面

解决办法
1. x 的兄弟节点 brother 是红色的.
  
  x.parent.colr = RED, brother.color = BLACK 向 x 方向旋转 x.parent
2. x 的兄弟节点 brother 是黑色的
  - brother 的孩子都是是黑色的
```
brother.color = RED;
x = x.parent;
```
  - brother.left.color = RED, brother.right.color = BLACK
  - brother.right.colr = RED

enum RBColor { RED, BLACK };
template <typename T>
class RBNode
{
public:
    RBColor color;
    T key;
    RBNode* left;
    RBNode* right;
    RBNode* parent;
    RBNode(RBColor _color = BLACK, T _key = 0, RBNode* _left = nullptr, RBNode* _right = nullptr, RBNode* _parent = nullptr) : color(_color), key(_key), left(_left), right(_right), parent(_parent) {}
};

/**
 *  @brief 红黑树
 */

template <typename T>
class RBTree
{
private:
    RBNode<T>* root;

public:
    RBTree() : root(nullptr) {}
    ~RBTree();
    RBTree(const RBTree<T>& rbt);
    RBTree<T>& operator=(const RBTree<T>& rbt);
    /**
     *  @brief 查找键值为 k 的节点, 递归
     *  @param key 关键字
     *  @return  RBNode*
     */
    RBNode<T>* search(T key);

    /**
     *  @brief 查找键值为 k 的节点, 非递归
     *  @param key 关键字
     *  @return  RBNode*
     */
    RBNode<T>* iterSearch(T key);

    /**
     * @brief 插入节点
     */
    void insert(T key);

    /**
     * @brief 删除节点
     */
    void remove(T key);

    /**
     * @brief 查找节点 x (有右孩子) 的后继节点
     */
    RBNode<T>* successor(RBNode<T>* x);

    /**
     * @brief 返回最小值, 空树返回 0
     */
    T minimum();

    /**
     * @brief 返回最大值, 空树返回 0
     */
    T maximum();

    /**
     * @brief 中序遍历
     */
    void inOrder() const;

    /**
     * @breif 前序遍历
     */
    void preOrder() const;

private:
    /**
     * @brief 递归的拷贝函数
     */
    RBNode<T>* copy(RBNode<T>* parent, RBNode<T>* _root);

    /**
     * 递归删除树
     */
    void destory(RBNode<T>* _root);

    /**
     * @brief 左旋
     */
    void leftRoate(RBNode<T>* x);

    /**
     *  @brief 右旋
     */
    void rightRoate(RBNode<T>* x);

    RBNode<T>* search(RBNode<T>* _root, T key) const;

    void insertFix(RBNode<T>* z);

    void transSubtree(RBNode<T>* src, RBNode<T>* dic);

    void removeFix(RBNode<T>* x);

    void remove(RBNode<T>* z);
};

template <typename T>
RBTree<T>::RBTree(const RBTree<T>& rbt)
{
    root = copy(nullptr, rbt.root);
}

template <typename T>
RBTree<T>::~RBTree()
{
    destory(root);
}

template <typename T>
RBNode<T>* RBTree<T>::copy(RBNode<T>* parent, RBNode<T>* _root)
{
    if (!_root) return nullptr;
    RBNode<T>* ret = new RBNode<T>(_root->color, _root->key, copy(ret, _root->left), copy(ret, _root->right), parent);
}

template <typename T>
RBTree<T>& RBTree<T>::operator=(const RBTree<T>& rbt)
{
    if (this == &rbt) return *this;
    destory(root);
    root = copy(nullptr, rbt.root);
}

template <typename T>
RBNode<T>* RBTree<T>::search(T key)
{
    return search(root, key);
}

template <typename T>
RBNode<T>* RBTree<T>::search(RBNode<T>* _root, T key) const
{
    if (!_root) return nullptr;
    if (key == _root->key) return _root;
    if (key < _root->key) return search(_root->left, key);
    if (key > _root->key) return search(_root->right, key);
}

template <typename T>
RBNode<T>* RBTree<T>::iterSearch(T key)
{
    RBNode<T>* pt = root;
    while (pt)
    {
        if (key == pt->key) return pt;
        if (key < pt->key)
            pt = pt->left;
        else if (key > pt->key)
            pt = pt->right;
    }
    return pt;
}

template <typename T>
void RBTree<T>::destory(RBNode<T>* _root)
{
    if (_root)
    {
        RBNode<T>* _left  = _root->left;
        RBNode<T>* _right = _root->right;
        delete _root;
        destory(_left);
        destory(_right);
    }
}

template <typename T>
RBNode<T>* RBTree<T>::successor(RBNode<T>* x)
{
    RBNode<T>* ret = x->right;
    while (ret->left)
    {
        ret = ret->left;
    }
    return ret;
}

template <typename T>
T RBTree<T>::minimum()
{
    if (!root) return 0;
    RBNode<T>* pt = root;
    while (pt->left) pt = pt->left;
    return pt->key;
}

template <typename T>
T RBTree<T>::maximum()
{
    if (!root) return 0;
    RBNode<T>* pt = root;
    while (pt->right) pt = pt->right;
    return pt->key;
}

template <typename T>
void RBTree<T>::leftRoate(RBNode<T>* x)
{
    RBNode<T>* y = x->right;
    x->right     = y->left;
    if (x->right) x->right->parent = x;
    y->parent = x->parent;
    if (!y->parent)
        root = y;
    else if (y->parent->left == x)
        y->parent->left = y;
    else
        y->parent->right = y;
    y->left   = x;
    x->parent = y;
}

template <typename T>
void RBTree<T>::rightRoate(RBNode<T>* x)
{
    RBNode<T>* y = x->left;
    x->left      = y->right;
    if (x->left) x->left->parent = x;
    y->parent = x->parent;
    if (!y->parent)
        root = y;
    else if (y->parent->left == x)
        y->parent->left = y;
    else
        y->parent->right = y;
    y->right  = x;
    x->parent = y;
}

template <typename T>
void RBTree<T>::insert(T key)
{
    RBNode<T>* z  = new RBNode<T>(RED, key, nullptr, nullptr, nullptr);
    RBNode<T>* px = root;
    RBNode<T>* py = nullptr;
    while (px)
    {
        py = px;
        if (key < px->key)
            px = px->left;
        else
            px = px->right;
    }
    z->parent = py;
    if (!py)
        root = z;
    else if (key < py->key)
        py->left = z;
    else
        py->right = z;
    insertFix(z);
}

template <typename T>
void RBTree<T>::insertFix(RBNode<T>* z)
{
    while (z->parent && z->parent->color == RED)
    {
        if (z->parent == z->parent->parent->left)
        {
            RBNode<T>* uncle = z->parent->parent->right;
            if (uncle && uncle->color == RED)
            {
                uncle->color             = BLACK;
                z->parent->color         = BLACK;
                z->parent->parent->color = RED;
                z                        = z->parent->parent;
                continue;
            }
            else if (z == z->parent->right)
            {
                z = z->parent;
                leftRoate(z);
            }
            z->parent->color         = BLACK;
            z->parent->parent->color = RED;
            rightRoate(z->parent->parent);
        }
        else
        {
            RBNode<T>* uncle = z->parent->parent->left;
            if (uncle && uncle->color == RED)
            {
                uncle->color             = BLACK;
                z->parent->color         = BLACK;
                z->parent->parent->color = RED;
                z                        = z->parent->parent;
                continue;
            }
            else if (z == z->parent->left)
            {
                z = z->parent;
                rightRoate(z);
            }
            z->parent->color         = BLACK;
            z->parent->parent->color = RED;
            leftRoate(z->parent->parent);
        }
    }
    root->color = BLACK;
}

template <typename T>
void RBTree<T>::transSubtree(RBNode<T>* src, RBNode<T>* dic)
{
    if (!src->parent)
        root = dic;
    else if (src == src->parent->left)
        src->parent->left = dic;
    else
        src->parent->right = dic;
    if (dic) dic->parent = src->parent;
}

template <typename T>
void RBTree<T>::remove(T key)
{
    RBNode<T>* pt = root;
    while (key != pt->key)
    {
        if (key < pt->key)
            pt = pt->left;
        else
            pt = pt->right;
    }
    remove(pt);
}

template <typename T>
void RBTree<T>::remove(RBNode<T>* z)
{
    RBNode<T>* y = z;
    RBNode<T>* x;
    RBColor yOriginalCol = y->color;
    if (!z->left)
    {
        x = z->right;
        transSubtree(z, x);
    }
    else if (!z->right)
    {
        x = z->left;
        transSubtree(z, x);
    }
    else
    {
        y            = successor(z);
        yOriginalCol = y->color;
        x            = y->right;
        if (y->parent == z)
            x->parent = y;
        else
        {
            transSubtree(y, x);
            y->right         = z->right;
            y->right->parent = y;
        }
        transSubtree(z, y);
        y->left         = z->left;
        y->left->parent = y;
    }
    delete z;
    if (yOriginalCol == BLACK) removeFix(x);
}

template <typename T>
void RBTree<T>::removeFix(RBNode<T>* x)
{
    if (x != root && x->color == BLACK)
    {
        if (x == x->parent->left)
        {
            RBNode<T>* brother = x->parent->right;
            if (brother->color == RED)
            {
                brother->color   = BLACK;
                x->parent->color = RED;
                leftRoate(x->parent);
                brother = x->parent->right;
            }
            if (brother->left->color == BLACK && brother->right->color == BLACK)
            {
                brother->color = RED;
                x              = x->parent;
            }
            else if (brother->right->color == BLACK)
            {
                brother->left->color = BLACK;
                brother->color       = RED;
                rightRoate(brother);
                brother = x->parent->right;
            }
            brother->color        = x->parent->color;
            x->parent->color      = BLACK;
            brother->right->color = BLACK;
            leftRoate(x->parent);
            x = root;
        }
        else
        {
            RBNode<T>* brother = x->parent->left;
            if (brother->color == RED)
            {
                brother->color   = BLACK;
                x->parent->color = RED;
                rightRoate(x->parent);
                brother = x->parent->left;
            }
            if (brother->left->color == BLACK && brother->right->color == BLACK)
            {
                brother->color = RED;
                x              = x->parent;
            }
            else if (brother->left->color == BLACK)
            {
                brother->right->color = BLACK;
                brother->color        = RED;
                leftRoate(brother);
                brother = x->parent->left;
            }
            brother->color       = x->parent->color;
            x->parent->color     = BLACK;
            brother->left->color = BLACK;
            rightRoate(x->parent);
            x = root;
        }
    }
    x->color = BLACK;
}
template <typename T>
void RBTree<T>::preOrder() const
{
    using std::cout;
    using std::endl;
    using std::stack;
    stack<RBNode<T>*> St;
    RBNode<T>* pt = root;
    while (pt || !St.empty())
    {
        while (pt)
        {
            cout << pt->key << ",";
            St.push(pt);
            pt = pt->left;
        }
        pt = St.top();
        St.pop();
        pt = pt->right;
    }
    cout << endl;
}

template <typename T>
void RBTree<T>::inOrder() const
{
    using std::cout;
    using std::endl;
    using std::stack;
    stack<RBNode<T>*> St;
    RBNode<T>* pt = root;
    while (pt || !St.empty())
    {
        while (pt)
        {
            St.push(pt);
            pt = pt->left;
        }
        pt = St.top();
        cout << pt->key << ",";
        St.pop();
        pt = pt->right;
    }
    cout << endl;
}

红黑树

红黑树

红黑树的介绍

红黑树的性质

旋转

左旋

右旋

插入

没有父指针的红黑树插入

删除

子树替换的辅助程序

删除节点 z

修复红黑树, 使其满足 5 条性质

y 的原始颜色是红色的, 则红黑树的性质仍然保持

y 是黑色的, 给 x 添加一个黑色

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读