红黑树与2-3树详解

一、红黑树与2-3树

1. 红黑树

R-B Tree，全称是Red-Black Tree，又称为"红黑树"，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性(算法导论):

• （1）每个节点或者是黑色，或者是红色。
• （2）根节点是黑色。
• （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
• （4）如果一个节点是红色的，则它的子节点必须是黑色的。
• （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

上边的红黑树定义的特别形式化，初次接触可能不太习惯，那么我们接下来先来介绍和红黑树等价的另外一种树2-3树；如果能把2-3树搞明白对于学习红黑树以及B类树都是有很大的好处的；

2. 2-3树

满足二分搜索树的基本性质，一个节点可以放置一个元素或者两个元素，每个子节点可以有两个元素或者三个元素，就叫做2-3树；

综上所属，2-3树也有可能会在一棵树中有这样的两种节点组成

在2-3树中有一个很重要的性质：2-3树是一个绝对平衡的树，这个特性是和2-3树的插入操作息息相关的；绝对平衡的意思就是说从根节点到任意一个叶子节点，所经过的节点数量一定是相同的。

二、2-3树的绝对平衡性

1. 2-3树是如何维护绝对的平衡的？

首先，我们往2-3树中添加第一个节点

由于此时2-3树是空的，所以42这个节点就理所当然的成为了根节点；

此时我们在添加一个新的节点37，由于2-3树一个节点可以存放两个元素且不能往空的节点添加新的元素，所以我们可以把新的元素与原来的元素进行融合形成一个三节点；

如果此时在添加一个新的元素12，由于不能往空节点存放数据，所以我们将这个新的元素也放在根节点，从而形成了一个四节点；

这个时候我们可以将这个四节点拆分成一个二分搜索树，当然这个二分搜索树也是绝对平衡的；

如果此时我们在添加一个新元素18，那么这个元素可以直接放在子节点中，与12这个元素形成一个三节点；

此时在新加入一个元素6，我们将重复以上的动作，将这个元素放在子节点中形成四元素；

对于四元素的节点我们依然选择对它进行拆分，但是此时拆分后它就没有绝对平衡性了

然后我们将新拆分的二分搜索树的根节点12与这颗树的根节点进行融合形成一个新的具有绝对平衡性的2-3树；

继续添加新的元素，我们仍然采用融合的方式进行数据的存储；

继续采用融合的存储方式添加元素；

拆分四节点；

继续融合根节点，让根节点成为四节点；

最后我们对根节点的元素进行拆分从而形成绝对平衡的2-3树；

注意： 这里所说的三节点，四节点是指子节点的数量，假设一个存储两个元素的根节点，那么它们的子节点一共有三个分别是左中右；

分析到这里我们可以得出，2-3树维护绝对平衡性的操作其实就是融合与拆分

三、红黑树与2-3树的等价性

在某种程度上，红黑树与2-3树是具有等价性的，这种等价性在2-3树每个节点为2节点时尤为明显

对于2-3树中的三节点在红黑树中的对应表示可能没有那么明显

我们将b与c连接的那个边表示为红色，意思就是b与c如果转化为2-3树的话将会是一个三节点，但是这个并不是红黑树最终的表示形式，如果使用红黑树表述的话将会是这样的

如果理解了上边的推导过程，那么下边的实例应该是非常简单的

像这样的一个2-3树如果转换成红黑树将会是这样的

为什么在这个红黑树中只有三个红色的节点呢，因为在转换前的2-3树中只有三个三节点，三节点转换后将会变成三个红色的节点，从这里我们也可以自己定义一个结论红色的节点一直在左侧；如果看起来抽象的话，我们可以对这个红黑树进行一次变形

代码实现

class RBTree:

    RED = True
    BLACK = False

    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
            self.color = RBTree.RED

    def __init__(self):
        self.root = None
        self.size = 0

    def get_size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def is_red(self, node):
        """
        判断节点node的颜色
        """
        if node is None:
            return self.BLACK
        return node.color

    def add(self, key, value):
        """向二分搜索树中添加新的元素(key, value)"""
        self.root = self._add(self.root, key, value)

    def _add(self, node, key, value):
        """向以node为根的二分搜索树中插入元素(key, value)，递归算法
        返回插入新节点后二分搜索树的根"""

        if node is None:
            self.size += 1
            return self.Node(key, value)

        if key < node.key:
            node.left = self._add(node.left, key, value)
        elif key > node.key:
            node.right = self._add(node.right, key, value)
        else:  # key == node.key
            node.value = value

        return node

    def get_node(self, node, key):
        """返回以node为根节点的二分搜索树中，key所在的节点"""

        if node is None:
            return None

        if key == node.key:
            return node
        elif key < node.key:
            return self.get_node(node.left, key)
        else:  # key > node.key
            return self.get_node(node.right, key)

    def contains(self, key):
        return self.get_node(self.root, key) is not None

    def get(self, key):
        node = self.get_node(self.root, key)
        return node.value if node is not None else None

    def set(self, key, new_value):
        node = self.get_node(self.root, key)
        if node is None:
            raise ValueError(f"{key} doesn't exist!")

        node.value = new_value

    def minimum(self, node):
        """返回以node为根的二分搜索树的最小值所在的节点"""
        if node.left is None:
            return node
        return self.minimum(node.left)

    def remove_min(self, node):
        """删除掉以node为根的二分搜索树中的最小节点
        返回删除节点后新的二分搜索树的根"""

        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            return right_node

        node.left = self.remove_min(node.left)
        return node

    def remove(self, key):
        """从二分搜索树中删除键为key的节点"""
        node = self.get_node(self.root, key)
        if node is not None:
            self.root = self._remove(self.root, key)
            return node.value
        return None

    def _remove(self, node, key):

        if node is None:
            return None

        if key < node.key:
            node.left = self._remove(node.left, key)
            return node
        elif key > node.key:
            node.right = self._remove(node.right, key)
            return node
        else:  # key == node.key

            # 待删除节点左子树为空的情况
            if node.left is None:
                right_node = node.right
                node.right = None
                self.size -= 1
                return right_node

            # 待删除节点右子树为空的情况
            if node.right is None:
                left_node = node.left
                node.left = None
                self.size -= 1
                return left_node

            # 待删除节点左右子树均不为空的情况

            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self.minimum(node.right)
            successor.right = self.remove_min(node.right)
            successor.left = node.left

            node.left = node.right = None

            return successor

四、保持根节点为黑色和左旋转

1. 保持根节点为黑色

def add(self, key, value):
    """向二分搜索树中添加新的元素(key, value)"""
    self.root = self._add(self.root, key, value)
    # 保持根节点为黑色
    self.root.color = self.BLACK

2. 向红黑树中添加新的元素(二节点）

1. 如果新添加的元素比根元素要小的话也就是说是往根节点的左节点中插入元素的话，我们就不用考虑节点颜色的问题；

2. 但是如果要添加的元素是往根节点的右侧添加，我们就需要处理一下节点颜色的问题，因为根据我们的定义右侧不能有红色的节点；

为了不失一般性，我们给每个节点都加上子节点，这个时候这棵树是不满足红黑树的要求的

这个时候我们就需要对这个树进行一次左旋转，旋转完成以后我们还需要对这个树的旋转后的节点进行颜色的维护；

3. 代码实现红黑树左旋转

def left_rotate(self, node):
    """
    #   node                     x
    #  /   \     左旋转         /  \
    # T1   x   --------->   node   T3
    #     / \              /   \
    #    T2 T3            T1   T2
    """

    x = node.right

    # 左旋转
    node.right = x.left
    x.left = node

    x.color = node.color
    node.color = self.RED

    return x

五、颜色反转和右旋转

1. 颜色反转

首先我们添加一个元素的时候(三节点)

如果默认是往左侧添加，则直接添加即可；

如果继续添加，则就会变成这样因为我们默认添加的元素都是红色的

如果将这个红黑树转换为2-3树的话就是现在的样子；

我们在2-3树中对一个临时的四节点需要进行拆分，拆分成二分搜索树的形式；拆分后每一个子节点就相当于一个二节点存在，与之对应的就是红黑树表示方式就是一个单独的黑色的节点，所以我们要对红黑树的左右子节点进行颜色的维护就变成了现在这样；

我们在对2-3树拆分以后我们需要将拆分后的根节点于其祖先节点进行融合，所以对应的我们的黑红书的根节点颜色就需要维护成红色；这个过程就叫做颜色反转；

2. 代码实现颜色反转

def flip_colors(self, node):
    """颜色反转"""
    node.color = self.RED
    node.left.color = self.BLACK
    node.right.color = self.BLACK

3. 右旋转

如果我们向一个三节点中添加新的元素

紧接着我们在添加一个新元素

这个时候的红黑树就等同于2-3树的临时四节点

现在这样的红黑树形状我们怎么把它变成由三个二节点组成的子树呢？这个时候我们就需要使用右旋转来实现；

4. 右旋转代码实现

def right_rotate(self, node):
    """
    #     node                   x
    #    /   \     右旋转       /  \
    #   x    T2   ------->   y   node
    #  / \                       /  \
    # y  T1                     T1  T2
    """

    x = node.left

    # 右旋转
    node.left = x.right
    x.right = node

    x.color = node.color
    node.color = self.RED

    return x

六、红黑树中添加新元素

由于之前已经分析过添加新元素的原理，在这里就不再重复了，添加新元素的过程可以参考图示：

这个是最复杂的添加情况的实现过程，其他两种稍微简单的添加情况(当添加一个小于三节点的值，或者添加一个大于三节点的值)情况就是这样的

维护的时机和AVL树是一样的，采用的方式也是和AVL一样，添加成功后回溯向上维护；

代码实现

def add(self, key, value):
    """向红黑树中添加新的元素(key, value)"""
    self.root = self._add(self.root, key, value)
    # 保持根节点为黑色
    self.root.color = self.BLACK

def _add(self, node, key, value):
    """向以node为根的红黑树中插入元素(key, value)，递归算法
    返回插入新节点后红黑树的根"""

    if node is None:
        self.size += 1
        # 默认插入红色节点
        return self.Node(key, value)

    if key < node.key:
        node.left = self._add(node.left, key, value)
    elif key > node.key:
        node.right = self._add(node.right, key, value)
    else:  # key == node.key
        node.value = value

    if self.is_red(node.right) and not self.is_red(node.left):
        node = self.left_rotate(node)
    if self.is_red(node.left) and node.left is not None and self.is_red(node.left.left):
        node = self.right_rotate(node)
    if self.is_red(node.left) and self.is_red(node.right):
        self.flip_colors(node)

    return node

另外红黑树的其他操作： 由于红黑树底层结构使用的是二分搜索树，所以其他操作可以参考二分搜索树，还有就是红黑树的删除操作由于过于复杂这里就不再进行分析；