2019-07-24 18:04 已编辑同济大学算法工程师

关注

[数据结构与算法]二叉排序树之红黑树

文章目录

红黑树

整理时长两天半的红黑树，虐死我了，昨晚还失眠了！

红黑树

红黑树是二叉查找树的一种,每个节点上多了一个表示颜色的存储位.

1. 红黑树的特性

每个结点是黑色或者红色
根结点为黑色
空结点为黑色(这里把空结点称为叶节点)
红色结点的子节点都为黑色
从一个结点到其子孙叶子结点所有路径具有相同数目的黑结点

特性5和特性4保证了没有一条路径会比其他路径长出两倍.所以说红黑树是接***衡的二叉树

2. 红黑树时间复杂度证明

定理

一棵含有n个结点的红黑树的高度至多为 $2 l o g (n + 1)$

证明

(1) 转换为逆否命题

其逆否命题为:

一棵高度为h的红黑树结点数至少为 $2^{h / 2} - 1$

$h \leq 2 l o g (n + 1)$

$l o g (n + 1) \geq h / 2$

$n \geq 2^{h / 2} - 1$

(2)结合红黑树特性,进一步转换命题

假设红黑树的结点 $x$ (不计本身)到其叶子节点(空结点)经历的黑结点个数为 $b h (x)$ ,可以称为黑高度.根据特性5知道左右两条路径的黑高度都为 $b h (x)$ .根据特性4知道,经历的黑色结点大于等于红色结点的个数.因此从结点 $x$ 到叶子节点经历的结点个数不大于 $2 * b h (x)$

经历一个结点则高度加1,现在令 $x$ 结点为根节点, 到叶节点经历的节点数为 $n$ , 因此树的高度为 $1 + n - 1$ ,第一个1是根节点,最后一个-1是空结点,空结点不计高度.

$h = 1 + n - 1 = n$

由于 $n \leq 2 * b h (x)$ ,所以

$2 * b h (x) \geq h$

$b h (x) \geq h / 2$

因此命题变成:

一棵高度为h的红黑树,它包含的内节点数至少为 $2^{b h (x)} - 1$ 个

(3) 数学归纳法证明命题成立

i) $h = 0$ 时

$b h (x) = 0$ , $2^{b h (x)} - 1 = 0$ ,原命题成立

ii) $h > 0$ 时

假设高度为 $h - 1$ ,此时定理成立,结点至少为 $2^{b h (x) - 1} - 1$ .

iii) 考虑一棵高度为 $h$ 的红黑树.

当子节点为黑色时,该子树仍为红黑树,其高度为 $h - 1$ ,因此其节点数至少为 $2^{b h (x) - 1} - 1$
当子节点为红色时,子节点的左右子树都为红黑树(红色结点子结点为黑结点),高度为 $h - 2$ ,因此该子树节点数至少为红色结点加上红色结点左右子树至少节点数: $1 + 2 * (2^{b h (x) - 2} - 1) = 2^{b h (x) - 1} - 1$

因此高度为 $h$ 的红黑树结点数至少为
$1 + 2^{b h (x) - 1} - 1 + 2^{b h (x) - 1} - 1 = 2^{b h (x)} - 1$

证毕!

3. 红黑树的基本操作

两个旋转操作,左旋和右旋.是在红黑树发生删除或者插入时，维护树仍为红黑树的操作．

左旋

旋转的基本原则是维持二叉排序树的性质.

旋转前的中序遍历结果: $α, X, β, Y, γ$
旋转后的中序遍历结果: $α, X, β, Y, γ$

旋转操作要指定结点,对 $X$ 结点左旋就是将 $X$ 结点变成左子节点

#　先定义红黑树类和红黑树节点类
class RBTree(object):
    def __init__(self):
        # 定义一个叶节点，尽管值为空，但还是有各种属性
        self.nil = RBTreeNode(None)
        self.root = self.nil

class RBTreeNode(object):
    def __init__(self, x):
        self.key = x
        self.left = None
        self.right = None
        self.parent = None
        self.color = 'black'

def left_rotate(T, x):
    """ T是一个红黑树类 ｘ是要进行旋转的结点 """
    y = x.right

    # 总共有三处连接发生改变，分别是Ｙ和整棵树的父节点，Ｙ和Ｘ，Ｘ和beta
    # 每处连接都是双向的，要处理两个指向

    # 1. 先处理ｘ和beta
    x.right = y.left
    if y.left != T.nil:  # y的左结点非空时，将其父节点设置成Ｘ
        y.left.parent = x

    # 2. 再处理Ｙ和父节点
    y.parent = x.parent # y向上连接的线
    # y 向下连接的线分三种情况，父节点为空ｙ当根节点，ｙ当左结点，ｙ当右结点
    if x.parent == T.nil:
        T.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y

    # 3. 最后处理Ｘ和Ｙ
    y.left = x
    x.parent = y

右旋

def right_rotate(T, x):
    y = x.left

    x.left = y.right
    if y.right != T.nil:
        y.right.parent = x

    y.parent = x.parent
    if x.parent == T.nil:
        T.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y

    y.right = x
    x.parent = y

4. 红黑树插入

插入步骤三步走:

按二叉排序树的方法，将结点插入到正确的位置
将结点标记为红色
通过旋转和着色操作，将树调整回红黑树

def insert(T, x):
    # step 1
    f = T.nil   # 父指针
    s = T.root  # 子指针
    # 找到插入位置
    while s != T.nil:
        if x.key < s.key:
            f = s
            s = s.left
        elif x.key > s.key:
            f = s
            s = s.right
        else:
            s.key = x.key
            return

    # 插入结点
    x.parent = f
    if f == T.nil:
        T.root = x
    elif x.key < f.key:
        f.left = x
    else:
        f.right = x
    x.left = T.nil
    x.right = T.nil

    # step 2
    # 着色
    x.color = 'red'

    # step 3
    # 插入后维护红黑树
    insert_fixup(T, x)

插入后的红黑树维护

插入结点之后，有三种情况：

插入节点为根节点
- i.直接把结点涂成黑色
插入的结点不是根节点
- ii.被插入结点的父节点是黑色，什么都不用做
- iii.被插入节点的父节点是红色，分三种情况进行调整进行调整 $↓$
  - 被插入节点的父节点是祖父结点的左结点
    - 叔叔结点为红色（祖父节点的另一个子节点）
      - 将父节点设置为黑色
      - 将叔叔结点设置为黑色
      - 将祖父节点设置为红色
      - 将祖父结点设置为当前结点，继续处理
    - 叔叔结点为黑色
      - 当前结点是父节点的右结点
        
        将父节点作为新的当前节点
        以当前结点进行左旋
      - 当前结点是父节点的左结点
        
        将父节点设置为黑色
        将祖父节点设置为红色
        以祖父节点进行右旋
  - 被插入节点的父节点是祖父结点的右结点
    - 叔叔结点为红色（祖父节点的另一个子节点）
      - 将父节点设置为黑色
      - 将叔叔结点设置为黑色
      - 将祖父节点设置为红色
      - 将祖父结点设置为当前结点，继续处理
    - 叔叔结点为黑色
      - 当前结点是父节点的左结点
        
        将父节点作为新的当前节点
        以当前结点进行右旋
      - 当前结点是父节点的右结点
        
        将父节点设置为黑色
        将祖父节点设置为红色
        以祖父节点进行左旋

总结一下，需要进行操作的主要有三种情况:

当前结点父节点为红色，叔叔结点为红色
当前结点父节点为红色，叔叔结点为黑色，当前结点是父节点左结点
当前结点父节点为红色，叔叔结点为黑色，当前结点是父节点右结点

以下仔细看下每种情况下的操作：

当前结点父节点为红色，叔叔结点为红色

当前结点是４

根据特性４，红色结点不能有红色子节点，因此将当前结点的父节点改为黑色
根据特性５，路径上黑色结点数相同，现在路径上多了一个黑色结点，因此将祖父结点改成红色结点，实现相等；
祖父结点变成红色结点导致叔叔路径黑色结点少一个，因此将叔叔结点变成黑色
现在整棵树满足特性５，问题可能出在祖父节点变成红色结点之后，破坏原来的特性４，因此将祖父结点变成当前结点

当前结点父节点为红色，叔叔结点为黑色，当前是父节点的内侧结点

当前结点为７

此时将父节点直接设置成黑色，或旋转都会造成更大的红黑树特性破坏．正确的做法是将当前结点移动到＂外侧＂，父节点是左孩子就左旋，父节点是右孩子就右旋．旋转结点为父节点．旋转完父节点变成了子节点，原来的子节点变成了父节点．解决红黑树特性问题从子结点开始，因此将原来的父节点，如今的子节点设置成当前节点．

当前结点父节点为红色，叔叔结点为黑色，当前结点是父节点的外侧结点

当前结点是2

将父节点变红，将祖父结点变黑，此时当前结点所在半侧满足红黑树特性，但另外半侧不满足特性５，考虑到将当前结点向上移动的原则，以祖父节点为支点进行右旋操作，正好能使另外半侧满足特性５．

此时当前结点的父节点已变成黑色，搞定！

def insert_fixup(T, x):
    while x.parent.color == 'red':
        if x.parent == x.parent.parent.left:
            y = x.parent.parent.right
            if y.color == 'red':
                x.parent.color = 'black'
                y.color = 'black'
                x.parent.parent.color = 'red'
                x = x.parent.parent
            else:
                if x == x.parent.right:
                    x = x.parent
                    left_rotate(T, x)

                x.parent.color ='black'
                x.parent.parent.color='red'
                right_rotate(T, x.parent.parent)
        else:
            y = x.parent.parent.left
            if y.color == 'red':
                x.parent.color = 'black'
                y.color = 'black'
                x.parent.parent.color = 'red'
                x = x.parent.parent

            else:
                if x == x.parent.left:
                    x = x.parent
                    right_rotate(T, x)

                x.parent.color = 'black'
                x.parent.parent.color = 'red'
                left_rotate(T, x.parent.parent)

    T.root.color = 'black'

5. 红黑树结点删除

红黑树结点删除两大步走！

将红黑树当做一棵二叉树，将结点删除
如果删除的结点颜色为黑，通过旋转和着色，维护红黑树特性

删除结点

结点的删除分三种情况：

没有子结点．直接将结点删除
一个子节点．将子节点顶替它的位置
两个子节点．找到左子树的最大值结点或右子树的最小值结点，称为后继结点．交换两个结点内容，删除后继结点，若有子节点则将后继结点唯一子节点顶替位置．

def delete(T, z):
    if z.left == T.nil or z.right == T.nil:
        y = z
    else:
        q = z.left  # 寻找后继结点的指针,寻早左子树的最大值结点
        while q.right != T.nil:
            q = q.right
        y = q

    # 交换值：
    if y != z:
        y.key, z.key = z.key, y.key

    # 将y的子节点挂到y的父节点下
    if y.left != T.nil:
        child = y.left
    else:
        child = y.right

    # 向上连线
    child.parent = y.parent
    # 向下连线
    if y.parent == T.nil:
        T.root = child
    elif y == y.parent.left:
        y.parent.left = child
    else:
        y.parent.right = child

    if y.color == 'black':
        delete_fixup(T, child)

维护红黑树特性

结点删除之后，被删除结点的子节点顶替了它的位置．由于删除的结点ｙ是黑色结点，现在我们假设顶替的结点ｘ身上多了一层黑色．这样就能维持特性５不被破坏，但破坏了特性1．另外特性2,4会因为x是红色而可能被破坏．

依据x的状态，可分为三种情况：

i) x是红加黑结点
- 直接将ｘ设为黑色结点，直接能维护特性1,2,4,红黑树特性全部恢复．
ii) x是黑加黑结点，且x是根
- 此时，什么都不做即可
iii) x是黑加黑结点，且x不是根．有四种子情况
- x的父节点是左孩子
  - x的兄弟结点是红色
    - 父节点设置为红色
    - 兄弟节点设置为黑色
    - 以父节点为支点，左旋
    - 重新设置兄弟节点
  - x的兄弟结点是黑色
    - 兄弟结点两个孩子都是黑色
      - 兄弟节点设为红色
      - 父节点设置为当前结点
    - 兄弟结点的左孩子是红色，右孩子是黑色
    - 兄弟节点的右孩子是红色的
- x的父节点是右孩子
  - x的兄弟结点是红色
  - x的兄弟结点是黑色
    - 兄弟结点两个孩子都是黑色
    - 兄弟结点的右孩子是红色，左孩子是黑色
    - 兄弟节点的左孩子是红色的

以下仔细说明每种情况，即详细操作步骤和原因

case1: x是黑加黑，兄弟结点是红色

兄弟结点是红色的，要先将兄弟结点转换成黑色的，这是这一步的目的．由于兄弟结点的子节点都为黑色，所以通过旋转操作能将兄弟结点的子节点变成当前节点的兄弟节点．旋转结点为父节点，旋转方向为朝着当前结点的方向．旋转之后要保持另外一半子树满足特性5，要将原来的兄弟节点设置为黑，原来的父节点设置为红．（规律！旋转前，交换两个旋转元素的颜***r> 操作总结:

父节点设置为红色
兄弟节点设置为黑色
以父节点为支点，左旋
重新设置兄弟节点

case2:x是黑加黑，兄弟结点及其子节点都为黑

首先记住处理问题的核心在于解决掉黑加黑的双重颜色，将这层黑色不断向上传递，如果传递到一个红色结点，将红色结点设置成黑色，问题解决！如果传递到黑色结点，且黑色结点是根的话，问题解决！如果不是根的话，继续传递！

这种情况的处理措施是将兄弟节点设置成红色结点，这样兄弟节点路径上黑色结点就会比当前节点少１；这时再将当前节点设置成父节点，换句话说，就是讲当前节点的另外一层黑传递到父节点，这样就能满足特性５了．

操作总结：

兄弟节点设为红色
父节点设为当前节点

case3:ｘ是黑加黑，兄弟节点为黑，兄弟结点靠近ｘ子节点为红，远离ｘ子节点为黑

这是一种过度状态，不好解决，要将远离ｘ的子节点变成红,同时兄弟节点保持不变

旋转操作＋旋转时的换色正好能实现！　　
旋转支点兄弟结点，旋转方向为远离ｘ的方向．

操作总结：

兄弟节点设为红色
兄弟节点的靠近ｘ的子结点设为黑色
以兄弟节点为支点向远离x的方向旋转
重新设置当前结点的兄弟节点

case 4: x 是黑加黑，兄弟节点是黑色，兄弟节点远离x的子结点是红色，另外一个结点颜色任意

这一步的核心同样在于消除x结点上的双重颜色，因此需要一个结点来分担一个黑色．由于旋转操作会附加一个换色操作，因此使用旋转操作！以父节点为中心，向靠近x方向旋转．旋转前交换颜色，父节点与兄弟结点颜色交换．旋转完检查每条路径的黑结点总和和旋转前情况比较．旋转后：根节点到当前节点1+1，旋转前：1*2;到原兄弟节点靠近x子节点保持不变，仍为１,到远离x子节点从1变为０,有问题！因此需要将原兄弟节点的远离x的子节点变成黑色．至此，成功消除x上的双层颜色．

操作总结:

兄弟节点设置为父节点颜色
父节点设置为黑色
以父节点为支点，向x旋转
设置原兄弟结点远离x的子结点为黑色

def delete_fixup(T, x):
    while x != T.root and x.color == 'black':
        if x == x.parent.left:
            brother = x.parent.right
            if brother.color == 'red':
                x.parent.color, brother.color = brother.color, x.parent.color
                left_rotate(T, x.parent)
                brother = x.parent.right

            if brother.left.color == 'black' and brother.right.color == 'black':
                brother.color = 'red'
                x = x.parent
            else:
                if brother.right.color == 'black':
                    brother.color, brother.left.color = brother.left.color, brother.color
                    right_rotate(T, brother)
                    brother = x.parent.right
                x.parent.color, brother.color = brother.color, x.parent.color
                brother.right.color = 'black'
                left_rotate(T, x.parent)

                x = T.root
        else:
            brother = x.parent.left
            if brother.color == 'red':
                x.parent.color, brother.color = brother.color, x.parent.color
                right_rotate(T, x.parent)
                brother = x.parent.left

            if brother.right.color == 'black' and brother.left.color == 'black':
                brother.color = 'red'
                x = x.parent
            else:
                if brother.right.color == 'red':
                    brother.right.color, brother.color = brother.color, brother.right.color
                    left_rotate(T, brother)
                brother = x.parent.left
                x.parent.color, brother.color = brother.color, x.parent.color
                brother.left.color = 'black'
                right_rotate(T, x.parent)

                x = T.root
    x.color = 'black'

6.完整代码

class RBTree(object):
    def __init__(self):
        # 定义一个叶节点，尽管值为空，但还是有各种属性
        self.nil = RBTreeNode(None)
        self.root = self.nil


class RBTreeNode(object):
    def __init__(self, x):
        self.key = x
        self.left = None
        self.right = None
        self.parent = None
        self.color = 'black'


def left_rotate(T, x):
    """ T是一个红黑树类 ｘ是要进行旋转的结点 """
    y = x.right

    # 总共有三处连接发生改变，分别是Ｙ和整棵树的父节点，Ｙ和Ｘ，Ｘ和beta
    # 每处连接都是双向的，要处理两个指向

    # 1. 先处理ｘ和beta
    x.right = y.left
    if y.left != T.nil:  # y的左结点非空时，将其父节点设置成Ｘ
        y.left.parent = x

    # 2. 再处理Ｙ和父节点
    y.parent = x.parent # y向上连接的线
    # y 向下连接的线分三种情况，父节点为空ｙ当根节点，ｙ当左结点，ｙ当右结点
    if x.parent == T.nil:
        T.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y

    # 3. 最后处理Ｘ和Ｙ
    y.left = x
    x.parent = y


def right_rotate(T, x):
    y = x.left

    x.left = y.right
    if y.right != T.nil:
        y.right.parent = x

    y.parent = x.parent
    if x.parent == T.nil:
        T.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y

    y.right = x
    x.parent = y


def insert(T, x):
    # step 1
    f = T.nil   # 父指针
    s = T.root  # 子指针
    # 找到插入位置
    while s != T.nil:
        if x.key < s.key:
            f = s
            s = s.left
        elif x.key > s.key:
            f = s
            s = s.right
        else:
            s.key = x.key
            return

    # 插入结点
    x.parent = f
    if f == T.nil:
        T.root = x
    elif x.key < f.key:
        f.left = x
    else:
        f.right = x
    x.left = T.nil
    x.right = T.nil

    # step 2
    # 着色
    x.color = 'red'

    # step 3
    # 插入后维护红黑树
    insert_fixup(T, x)


def insert_fixup(T, x):
    while x.parent.color == 'red':
        if x.parent == x.parent.parent.left:
            y = x.parent.parent.right
            if y.color == 'red':
                x.parent.color = 'black'
                y.color = 'black'
                x.parent.parent.color = 'red'
                x = x.parent.parent
            else:
                if x == x.parent.right:
                    x = x.parent
                    left_rotate(T, x)

                x.parent.color ='black'
                x.parent.parent.color='red'
                right_rotate(T, x.parent.parent)
        else:
            y = x.parent.parent.left
            if y.color == 'red':
                x.parent.color = 'black'
                y.color = 'black'
                x.parent.parent.color = 'red'
                x = x.parent.parent

            else:
                if x == x.parent.left:
                    x = x.parent
                    right_rotate(T, x)

                x.parent.color = 'black'
                x.parent.parent.color = 'red'
                left_rotate(T, x.parent.parent)

    T.root.color = 'black'


def delete(T, z):
    if z.left == T.nil or z.right == T.nil:
        y = z
    else:
        q = z.left  # 寻找后继结点的指针,寻早左子树的最大值结点
        while q.right != T.nil:
            q = q.right
        y = q

    # 交换值：
    if y != z:
        y.key, z.key = z.key, y.key

    # 将y的子节点挂到y的父节点下
    if y.left != T.nil:
        child = y.left
    else:
        child = y.right

    # 向上连线
    child.parent = y.parent
    # 向下连线
    if y.parent == T.nil:
        T.root = child
    elif y == y.parent.left:
        y.parent.left = child
    else:
        y.parent.right = child

    if y.color == 'black':
        delete_fixup(T, child)


def delete_fixup(T, x):
    while x != T.root and x.color == 'black':
        if x == x.parent.left:
            brother = x.parent.right
            if brother.color == 'red':
                x.parent.color, brother.color = brother.color, x.parent.color
                left_rotate(T, x.parent)
                brother = x.parent.right

            if brother.left.color == 'black' and brother.right.color == 'black':
                brother.color = 'red'
                x = x.parent
            else:
                if brother.right.color == 'black':
                    brother.color, brother.left.color = brother.left.color, brother.color
                    right_rotate(T, brother)
                    brother = x.parent.right
                x.parent.color, brother.color = brother.color, x.parent.color
                brother.right.color = 'black'
                left_rotate(T, x.parent)

                x = T.root
        else:
            brother = x.parent.left
            if brother.color == 'red':
                x.parent.color, brother.color = brother.color, x.parent.color
                right_rotate(T, x.parent)
                brother = x.parent.left

            if brother.right.color == 'black' and brother.left.color == 'black':
                brother.color = 'red'
                x = x.parent
            else:
                if brother.right.color == 'red':
                    brother.right.color, brother.color = brother.color, brother.right.color
                    left_rotate(T, brother)
                brother = x.parent.left
                x.parent.color, brother.color = brother.color, x.parent.color
                brother.left.color = 'black'
                right_rotate(T, x.parent)

                x = T.root
    x.color = 'black'