# 红黑树、2-3-4树 -- 潘登同学的图论笔记

@

2-3-4树

红黑树是2-3-4树的一种实现形式，只是2-3-4树的编程不太好写，但是2-3-4树的思想还是比较简洁明了滴...

2-3-4树是四阶的balance tree，他属于一种多叉查找树

有如下要求

• 1.所有叶子节点都拥有相同的深度
• 2.节点只能是2-节点，3-节点，4-节点之一
• 3.2-节点：包含一个元素的节点，有2个子节点
• 3-节点：包含两个元素的节点，有3个子节点
• 4-节点：包含三个元素的节点，有4个子节点
• 4.元素始終保持排序順序，整体上保持二叉查找树的性质，即父节点大于左子节点，小于右子节点
• 5.而节点有多个元素时，每个元素必须大于他左边的和他的左子树中元素

通过一个2-3-4树的生成过程来加深对他的认识

简单概况一下2-3-4树的生成过程： 在叶节点添加元素，如果叶节点超过了三个元素（如4个元素），那么第二个元素就会上升，其余分裂成一个二节点和一个三节点

总之，在叶节点上添加，然后多了就上升分裂，这样能保持树的高度是趋于一致的

红黑树

红黑树也是二叉树，与AVL树类似，但是平衡性比AVL树要好，要经过很多次插入和删除才会更新一次，有如下要求

• 1.根节点一定是黑色，叶节点是不存储数据的黑色空节点
• 2.红节点的子节点必须是黑色的
• 3.对任意节点，走到叶节点(空节点)路径上遇到的黑节点个数一样
• 4.由前三条推出 红黑树的高度最高是 2*log_2(n+1) n是节点个数

红黑树与2-3-4树的对应关系

• 2-节点： 黑色节点

• 3-节点: 左倾或者右倾

• 4-节点: 对应一个完整的叉

注意 上面的都是上黑下红

• 裂变状态

当在10-11-12中加入节点13，可以理解为 10-11-12节点集体上升然后变色，如果11是根节点，那么将会变回黑色

红黑树节点

红黑树节点有这样几个属性:

• 1.val: 节点储存的值
• 2.left: 左子节点
• 3.right: 右子节点
• 4.color: 节点颜色
• 5.parent: 父节点

伴随着的有如下节点方法:

• 1.hasleft: 判断是否有左子节点
• 2.hasright: 判断是否有右子节点
• 3.isleft: 判断节点是否为左子节点
• 4.isright: 判断节点是否为右子节点
• 5.isroot: 判断节点是否为根节点
• 6.getcolor: 获取节点颜色
• 7.setcolor: 设置节点颜色
• 8.getparent: 获取父节点
• 9.__str__ 显示设置
• 10.__iter__ 遍历设置
• 11.search: 查找操作

上代码

class RBTreeNode:
    def __init__(self,val=None,left=None,right=None,color='black',parent=None):
        self.left = left
        self.right = right
        # color = 'red' or 'black'
        self.color = color
        self.parent = parent
        self.val = val

    def hasleft(self):
        return self.left

    def hasright(self):
        return self.right

    def isleft(self):
        return self.parent and self.parent.left == self

    def isright(self):
        return self.parent and self.parent.right == self

    def isroot(self):
        return not self.parent

    def getcolor(self):
        return self.color

    def getparent(self):
        return self.parent

    def setcolor(self,color):
        self.color = color

    def __str__(self):
        return '数据是:{}'.format(self.val) 

    def __iter__(self):
        if self:
            if self.hasleft():
                # 递归调用
                for elem in self.left:
                    yield elem
            yield self.val  # 把根节点放在中间，最终的输出就是从小到大
            if self.hasright():
                # 递归调用
                for elem in self.right:
                    yield elem

    def search(self,val):
        '''
        :type val: number
        :rtype: RBTreeNode
        '''
        if self.val > val:
            return self.left.search(val) if self.left else None
        elif self.val == val:
            return self
        else:
            return self.right.search(val) if self.right else None

红黑树

红黑树基础的有两个属性

• 1.root: 存储根节点
• 2.size: 记录节点数

两个基本方法:

• 1.__len__ 查看树的节点数
• 2.__iter__ 树的遍历(前序遍历，从小到大)

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

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

红黑树的插入操作

红黑树的插入分为两步

• 1.普通二叉树的插入
• 2.红黑树的平衡(旋转 + 变色)

先写旋转（左旋、右旋）操作，这个在AVL中也有，基本上是一样的

    # 左旋操作
    def leftRotate(self,rotRoot):
        '''
        :type rotRoot: RBTreeNode
        '''
        newRoot = rotRoot.right
        rotRoot.right = newRoot.left
        if newRoot.left:
            newRoot.left.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isroot():
            self.root = newRoot
        else:
            if rotRoot.isleft():
                rotRoot.parent.left = newRoot
            else:
                rotRoot.parent.right = newRoot
        newRoot.left = rotRoot
        rotRoot.parent = newRoot

    # 右旋操作
    def rightRotate(self,rotRoot):
        '''
        :type rotRoot: RBTreeNode
        '''
        newRoot = rotRoot.left
        rotRoot.left = newRoot.right
        if newRoot.right:
            newRoot.right.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isroot():
            self.root = newRoot
        else:
            if rotRoot.isleft():
                rotRoot.parent.left = newRoot
            else:
                rotRoot.parent.right = newRoot
        newRoot.right = rotRoot
        rotRoot.parent = newRoot

再写插入put()

    def put(self,val):
        # 新增节点，分为两步
        #   1.普通二叉树的插入
        #   2.红黑树的平衡(旋转+变色)
        if self.root:
            self._put(val, self.root)
        else:
            self.root = RBTreeNode(val=val,color='black')
        self.size += 1

    def _put(self,val,currentNode):
        if val < currentNode.val:
            if currentNode.hasleft():
                # 如果有左节点就递归调用自身
                self._put(val, currentNode.left)
            else:
                currentNode.left = RBTreeNode(val=val, parent=currentNode)
                self.fixAfterput(currentNode.left)
        # 如果与某个节点相等那就不管他，直接return
        elif val == currentNode.val:
            return
        else:
            if currentNode.hasright():
                # 如果有右节点就递归调用自身
                self._put(val, currentNode.right)
            else:
                currentNode.right = RBTreeNode(val=val, parent=currentNode)
                self.fixAfterput(currentNode.right)

在插入put()操作中存在一个未定义的方法fixAfterput()，这个就是插入后调整的方法，需要分类讨论何时需要调整

对应回2-3-4树，有三类情况

• 情况一: 2-节点 新增一个元素 直接合并为3-节点 --> 红黑树直接添加一个红色节点无需调整
• 情况二: 3-节点 新增一个元素 合并为4-节点 --> 红黑树有6种情况，有两种不需要调整根左左、根右右 旋转一次 根左右 根右左 旋转两次

详细情况可以参考下图

• 根左左

• 根右右

• 根左右

• 根右左

• 正常情况

对于根左左、根右右只需对中间节点进行一次左旋或右旋即可，对于根左右、根右右，也是对中间节点进行左旋或者右旋就变成了根左左、根右右，然后再来一遍就可以了

• 情况三: 4节点 新增一个元素 4节点中间元素升级为父节点，新增元素和剩下元素合并 --> 红黑树:新增节点为红色, 爷爷节点是黑色.父节点和叔叔节点为红色 调整为 爷爷节点变为红色(如果是root则为黑色),父亲和叔叔节点变为黑色,

情况三会有这四种情况

因为红黑树的红色节点下面不能还是红色节点，所以需要做变色操作，具体来说是:插入节点变红，插入节点的父节点(包括叔叔节点)变黑，爷爷节点变红(如果爷爷节点是根节点，变回黑色)

红黑树情况三(4)修改过后应是这样

而值得注意的是，由于爷爷节点从黑色变为红色，对于爷爷节点的父节点来说，爷爷节点就相当于一个新插入的节点，这个新插入的红色节点又可能会影响爷爷节点的父节点进而产生情况一、二、三，所以需要对爷爷节点做递归处理

综合以上8种情况，以新增节点在爷爷节点的左子节点还是右子节点下，一分为二，在以情况二(旋转)、三(变色)的不同操作一分为二，最后给出调整代码

def fixAfterput(self,node):
        node.setcolor('red')
        while node and not node.isroot() and node.parent.getcolor() == 'red':
            # 如果插入的节点的父节点是爷爷节点的左侧
            if node.parent == node.parent.parent.left:
                # 对满足条件的4中情况 一分为二进行处理
                # 判断是否有叔叔节点，如果叔叔节点是红色就做变色操作
                if node.parent.parent.hasright() and node.parent.parent.right.getcolor() == 'red':
                    # 将父亲和叔叔节点变为黑色,将爷爷节点变为红色
                    node.parent.setcolor('black')
                    node.parent.parent.right.setcolor('black')
                    node.parent.parent.setcolor('red')
                    # 将修改了颜色的这一组子、父、爷节点视作一个整体，
                    # 看成一个红色节点插入到爷爷的父节点中递归处理
                    node = node.parent.parent
                else:
                    # 如果是根左右，先对‘左’进行一次左旋，就变成根左左
                    if node == node.parent.right:
                        self.leftRotate(node.parent)
                        node = node.left
                    # 如果是根左左
                    # 将父节点变为黑色
                    # 在对爷爷节点变色变为红色，最后对爷爷节点进行右旋
                    node.parent.setcolor('black')
                    node.parent.parent.setcolor('red')
                    self.rightRotate(node.parent.parent)
            else:
                # 与上面刚好相反的4中情况
                if node.parent.parent.hasleft() and node.parent.parent.left.getcolor() == 'red':
                    # 将父亲和叔叔节点变为黑色,将爷爷节点变为红色
                    node.parent.setcolor('black')
                    node.parent.parent.left.setcolor('black')
                    node.parent.parent.setcolor('red')
                    # 将修改了颜色的这一组子、父、爷节点视作一个整体，
                    # 看成一个红色节点插入到爷爷的父节点中递归处理
                    node = node.parent.parent
                else:
                    # 如果是根右左，先对‘右’进行一次右旋，就变成根右右
                    if node == node.parent.left:
                        self.rightRotate(node.parent)
                        node = node.right
                    # 如果是根右右
                    # 将父节点变为黑色
                    # 在对爷爷节点变色变为红色，最后对爷爷节点进行左旋
                    node.parent.setcolor('black')
                    node.parent.parent.setcolor('red')
                    self.leftRotate(node.parent.parent)
        # 最后处理爷爷节点为根节点的情况
        self.root.setcolor('black')

测试代码

进行完插入操作我们肯定要看自己写的对不对，我们新建一个画图函数，将红黑树绘制出来

import matplotlib.pyplot as plt
import numpy as np
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

class Draw_RBTree:
    def __init__(self, tree):
        self.tree = tree

    def show_node(self, node, ax, height, index, font_size):
        if not node:
            return
        x1, y1 = None, None
        if node.left:
            x1, y1, index = self.show_node(node.left, ax, height-1, index, font_size)
        x = 100 * index - 50
        y = 100 * height - 50
        if x1:
            plt.plot((x1, x), (y1, y), linewidth=2.0,color='b')
        circle_color = "black" if node.getcolor()=='black' else 'r'
        text_color = "beige" if node.getcolor()=='black' else 'black'
        ax.add_artist(plt.Circle((x, y), 50, color=circle_color))
        ax.add_artist(plt.Text(x, y, node.val, color= text_color, fontsize=font_size, horizontalalignment="center",verticalalignment="center"))
        # print(str(node.val), (height, index))

        index += 1
        if node.right:
            x1, y1, index = self.show_node(node.right, ax, height-1, index, font_size)
            plt.plot((x1, x), (y1, y), linewidth=2.0, color='b')

        return x, y, index

    def show_rb_tree(self, title):
        fig, ax = plt.subplots()
        left, right = self.get_left_length(), self.get_right_length(), 
        height = 2 * np.log2(self.tree.size + 1)
        # print(left, right, height)
        plt.ylim(0, height*100 + 50)
        plt.xlim(0, 100 * self.tree.size + 100)
        self.show_node(self.tree.root, ax, height, 1, self.get_fontsize())
        plt.axis('off')
        plt.title(title)
        plt.show()

    def get_left_length(self):
        temp = self.tree.root
        len = 1
        while temp:
            temp = temp.left
            len += 1
        return len

    def get_right_length(self):
        temp = self.tree.root
        len = 1
        while temp:
            temp = temp.left
            len += 1
        return len

    def get_fontsize(self):
        count = self.tree.size
        if count < 10:
            return 30
        if count < 20:
            return 20
        return 16

新建一个脚本文件test01.py

from RBTree import RBTree 
from Draw_RBTree import Draw_RBTree

t = RBTree()
t.put(10)
t.put(66)
t.put(77)
t.put(1)
t.put(2)
t.put(3)
t.put(4)
t.put(5)
t.put(6)
t.put(7)
t.put(8)
t.put(9)
t.put(88)
t.put(99)
t.put(100)
t.put(101)
d = Draw_RBTree(t)
d.show_rb_tree('红黑树示意图')
for i in t:
    print(i)

最终结果:

注意 如果插入的顺序不同，生成的红黑树结构不一定完全相同，但是高度保持的比较稳健

t = RBTree()
t.put(10)
t.put(77)
t.put(1)
t.put(2)
t.put(99)
t.put(66)
t.put(100)
t.put(3)
t.put(8)
t.put(88)
t.put(101)
t.put(4)
t.put(5)
t.put(9)
t.put(6)
t.put(7)
d = Draw_RBTree(t)
d.show_rb_tree('红黑树示意图')

最终结果:

红黑树的删除

红黑树的删除就十分复杂了，我们一步一步来，先回到普通二叉查找树的删除，二叉查找树的删除分为以下三种情况

• 1.删除叶子节点，直接删除
• 2.删除叶子节点有一个子节点，由子节点代替
• 3.删除叶子节点有两个子节点，那么此时需要获取对应的后继(或者前驱)节点来替代，然后把后继(前驱)节点删掉（删掉他们时会回到1、2两种情况)

先来实现找到前驱和后继节点

    # 寻找前驱节点,前驱节点是恰好比该节点小的节点，一定在该节点左节点的最右边
    def find_pred(self, node):
        # 如果有左or右子节点
        if node.hasright() or node.hasleft():
            temp = node.left
            while temp.right:
                temp = temp.right
            return temp
        # 如果要查找叶子节点的前驱节点(这种情况不会发生在删除操作中，只是完善功能罢了)
        else:
            p = node.parent
            # 也有可能没有前驱
            while p and p.val > node.val:
                p = p.parent
            return p
     # 寻找后继节点,后继节点是恰好比该节点大的节点，一定在该节点右节点的最左边
    def find_subsequent(self, node):
        # 如果有左or右子节点
        if node.hasright() or node.hasleft():
            temp = node.right
            while temp.left:
                temp = temp.left
            return temp
        # 如果要查找叶子节点的后继节点(这种情况不会发生在删除操作中，只是完善功能罢了)
        else:
            p = node.parent
            # 也有可能没有后继
            while p and p.val < node.val:
                p = p.parent
            return p

当红黑树采用了普通二叉查找树的删除操作时，对应回2-3-4树，其实会发现删除的都是2-3-4树的叶子节点，也就是红黑树最多删除最底下两层叶子节点（因为就算是删除根节点，我们也会去找他的后继(前驱)来替代，删掉的还是后继(前驱)),而对应2-3-4树的叶子节点被删除有这3种情况：

• 1.删除的是3-节点或4-节点中的元素，直接删除
• 2.删除的是2-节点，如果兄弟节点是3-节点或4-节点，父节点到删除节点位置，兄弟节点上升一个
• 3.删除节点是2-节点，如果兄弟节点也是2-节点，那就不合法，必须重构2-3-4树

我们先用上面测试二的结果来对应一颗2-3-4树

与之相对应的2-3-4树

• 1.如果删除的是5，6, 7这个4-节点的任何一个，直接删除即可
• 2.如果删除的是88这个2-节点，那么99下降到88的位置，100上升到99的位置，101到100的位置，由3-节点变为2-节点
• 3.如果接着第二步，继续删除99节点（因为99已经下沉到88节点位置，可以删除），那么他的兄弟节点都是2-节点，就必须重构2-3-4树（对于红黑树来说就是变色：因为2-3-4树的节点与红黑树的节点存在对应关系，变色可以改变节点类型

删除代码如下

    # 删除节点3种情况
    # 1.删除叶子节点，直接删除
    # 2.删除叶节点有一个子节点，由子节点来替代
    # 3.删除叶子节点有两个子节点，那么此时需要获取对应的后继节点来替代
    def _delete(self,node):
        # 有两个子节点
        if node.hasleft() and node.hasright():
            # 找到后继节点
            subsequent = self.find_subsequent(node)   
            node.val = subsequent.val
            # 那么要删除的就是后继节点了
            node = subsequent
        # 只有一个子节点的情况,就把子节点与当前节点替换，然后删掉当前节点
        if node.hasleft() or node.hasright():
            if node.hasleft():
                temp = node.left
                temp.parent = node.parent
                if node.isroot():
                    self.root = temp
                elif node.isleft():
                    node.parent.left = temp
                else:
                    node.parent.right = temp
            else:
                temp = node.right
                temp.parent = node.parent
                if node.isroot():
                    self.root = temp
                elif node.isleft():
                    node.parent.left = temp
                else:
                    node.parent.right = temp
            # 将node节点与红黑树脱离联系等待垃圾回收
            node.left = None
            node.right = None
            node.parent = None
            # 最后调整
            if node.color == 'black':
                self.fixAfterRemove(temp)
        # 如果没有子节点
        else:
            # 先调整
            if node.color == 'black':
                self.fixAfterRemove(node)
            if node.isroot():
                self.root = None
            elif node.isleft():
                node.parent.left = None
                node.parent = None
            else:
                node.parent.right = None
                node.parent = None

    #  2-3-4树叶子节点的删除有三种情况：
    #         1.删除的是3节点或4节点中的元素，直接删除 
    #         2.删除的是2节点，如果兄弟节点是3-节点或者4-节点，父节点到删除节点位置，兄弟节点上升一个
    #         3.删除的是2节点，如果兄弟节点也是2-节点，那就不合法，必须重构2-3-4树
    def fixAfterRemove(self, node):
        # 情况2和3
        while not node.isroot() and node.getcolor() == 'black':
            if node.isleft():
                # 查找兄弟节点
                temp = node.parent.right
                # 如果兄弟节点的颜色是红色，说明不是真正的兄弟节点，先将(假的)兄弟节点
                # 变为黑色，再将该节点的父节点变为红色，对父节点进行左旋
                if temp.getcolor() == 'red':
                    temp.setcolor('black')
                    node.parent.setcolor('red')
                    self.leftRotate(node.parent)
                    # 这样就能得到真正的兄弟节点
                    temp = node.parent.right
                # 如果兄弟节点的子节点都是黑色（都是2-节点）情况3
                # 或者是兄弟节点就是2-节点
                if (not temp.hasleft() or temp.left.getcolor() == 'black') and (not temp.hasright() or temp.right.getcolor() == 'black'):
                    # 需要递归地调整整颗树的结构
                    temp.setcolor('red')
                    node = node.parent
                # 情况2
                else:
                    # 如果兄弟节点存在左子节点,就对兄弟节点变为红色，其子节点变为黑色
                    # 对兄弟节点做右旋操作，让其子节点上升，自己下降，变为根右右型
                    if not temp.hasright() or temp.right.getcolor()=='black':
                        temp.setcolor('red')
                        temp.left.setcolor('black')
                        self.rightRotate(temp)
                        # 兄弟节点更新
                        temp = node.parent.right
                    # 现在兄弟节点存在右子节点
                    # 就让兄弟节点去成为父节点，兄弟节点的子节点代替其位置
                    # 父节点下沉为原本node节点所在位置
                    temp.setcolor(node.parent.getcolor())
                    node.parent.setcolor('black')
                    temp.right.setcolor('black')
                    self.leftRotate(node.parent)
                    node = self.root
            else:
                 # 查找兄弟节点
                temp = node.parent.left
                # 如果兄弟节点的颜色是红色，说明不是真正的兄弟节点，先将(假的)兄弟节点
                # 变为黑色，再将该节点的父节点变为红色，对父节点进行右旋
                if temp.getcolor() == 'red':
                    temp.setcolor('black')
                    node.parent.setcolor('red')
                    self.rightRotate(node.parent)
                    # 这样就能得到真正的兄弟节点
                    temp = node.parent.left
                # 如果兄弟节点的子节点都是黑色（都是2-节点）情况3
                if (not temp.hasleft() or temp.left.getcolor() == 'black') and (not temp.hasright() or temp.right.getcolor() == 'black'):
                    # 需要递归地调整整颗树的结构
                    temp.setcolor('red')
                    node = node.parent
                # 情况2
                else:
                    # 如果兄弟节点存在右子节点,就对兄弟节点变为红色，其子节点变为黑色
                    # 对兄弟节点做左旋操作，让其子节点上升，自己下降，变为根左左型
                    if not temp.hasleft() or temp.left.getcolor()=='black':
                        temp.setcolor('red')
                        temp.right.setcolor('black')
                        self.leftRotate(temp)
                        # 兄弟节点更新
                        temp = node.parent.left
                    # 现在兄弟节点存在右子节点
                    # 就让兄弟节点去成为父节点，兄弟节点的子节点代替其位置
                    # 父节点下沉为原本node节点所在位置
                    temp.setcolor(node.parent.getcolor())
                    node.parent.setcolor('black')
                    temp.left.setcolor('black')
                    self.rightRotate(node.parent)
                    node = self.root
        # 情况1: 替代的节点是红色，直接设置为黑色即可
        node.setcolor('black')

测试红黑树删除

依然沿用刚才的插入代码，先插入再删除

根据刚才的分析，验证一下代码是否如我们所愿，

• 1.删除5节点，整体没变化，只是5节点消失

• 1.1.因为我们采用的是删除节点用后继节点替代，删除4理应与删除5的效果一致，即只是4被5代替，5消失

• 2.删除88节点，99下降变黑，100上升变红，101上升变黑

• 2.1根据前面的思路，那么删除77与删除88应该是一样的，只是88替代了77的位置

• 3.在删除88后继续删除99，整个红黑树的结构就要改变

从图中看出，其实变化不大，是不是我们分析错了呢，不一定是，因为结构怎么变，不能只看局部，这个结构的变化在向上传导的过程中满足了2-3-4树的构成，就不会继续改变，我们把删除了88、99的2-3-4树画一下

• 3.1在删除88、99后继续删除66、77

而此时变化就很大了，如果我们假设2-3-4树结构不变，再画一下2-3-4树，发现这个2-3-4树是不合法的，在100节点下，缺少了一个子节点

而调整结构后的2-3-4树，应该是这样

测试代码

from RBTree import RBTree 
from Draw_RBTree import Draw_RBTree
t = RBTree()
t.put(10)
t.put(77)
t.put(1)
t.put(2)
t.put(99)
t.put(66)
t.put(100)
t.put(3)
t.put(8)
t.put(88)
t.put(101)
t.put(4)
t.put(5)
t.put(9)
t.put(6)
t.put(7)
# t.delete(5)
# t.delete(4)
# t.delete(88)
# t.delete(77)
t.delete(88)
t.delete(99)
t.delete(66)
t.delete(77)
d = Draw_RBTree(t)
d.show_rb_tree('红黑树删除88、99和66、77')

好啦，这就是红黑树的所有代码啦，至于删除时的情况三：是怎样将变化向爷爷节点传递的，需要仔细阅读代码，细心体会，天机不可泄露喔!!

完整代码，请到我的Github上获取，文件名为RBTree.py和Draw_RBTree.py