数据结构之红黑树

数据结构
,

红黑树是平衡搜索树的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度为 O(logn)

二叉查找树

二叉查找树（BST），又称二叉排序树、二叉搜索树。叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为 o(logn)。二叉查找树中序遍历一遍的结果是单调递增的，可以用于二分搜索。

  1. 没有键值相等的节点
  2. 若左子树不为空，则左子树上节点值均小于根节点的值
  3. 若右子树不为空，则右子树上节点值均大于根节点的值
  4. 任意节点的左、右子树也是二叉查找树

二叉排序树的性能取决于二叉树的层数：

  • 最好的情况是 O(logn)，存在于完全二叉排序树情况下，其访问性能近似于折半查找；
  • 最差时候会是 O(n)，比如插入的元素是有序的，二叉查找树退化为单链表时，需要遍历全部元素。

红黑树

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

红黑树具有五条性质：

  1. 每个结点要么是红的，要么是黑的。
  2. 根结点是黑的。
  3. 每个叶结点（叶结点即指树尾端 NIL 指针或 NULL 结点）是黑的。
  4. 如果一个结点是红的，那么它的俩个儿子都是黑的。
  5. 对于任一结点而言，其到叶结点树尾端 NIL 指针的每一条路径都包含相同数目的黑结点。

五大性质总结：

  1. 对每个红色节点，子节点只有两种情况：要么都没有，要么都是黑色的。（不然会违反特征四）
  2. 对黑色节点，如果只有一个子节点，那么这个子节点，必定是红色节点。（不然会违反特征五）
  3. 假设从根节点到叶子节点中，黑色节点的个数是 h, 那么树的高度 H 范围 h <= H <= 2H（特征四五决定）， 因此红黑树的查找不会退化到线性查找，时间复杂度为 O(logn)。

树的旋转

当对红黑树进行插入或删除操作时，可能会破坏红黑树的结构。为了保持红黑树的性质，可以对结点重新着色，及对树进行旋转操作，修改树中某些结点的颜色及指针结构。

树的旋转包括左旋和右旋，红黑树左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。

左旋

pivot 的左旋是： 把 pivot 变成它右孩子 Y 的左孩子，右孩子 Y 的左孩子变成它的右孩子；左旋是把右子树里的一个节点 (Y) 移动到左子树

右旋

pivot 的右旋是： 把 pivot 变成它左孩子 Y 的右孩子，左孩子 Y 的右孩子变成它的左孩子

对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。

红黑树的插入

  1. 首先和二叉查找树的插入一样，查找到结点插入的位置、插入
  2. 然后调整结构，保证满足红黑树状态:
    • 对结点进行重新着色
    • 以及对树进行相关的旋转操作

二叉查找树的插入

1
2
3
4
5
6
7
8
9
def insert(self, root, x):
    if not root:
        root = TreeNode(x)
    else:
        if x < root.val:
            root.left = self.insert(root.left, x) # 递归的去查找插入点
        elif x > root.val:
            root.right = self.insert(root.right, x)
    return root

红黑树定义：

1
2
3
4
5
6
7
class RBTreeNode:
    def __init__(self, x, color="R"):
        self.val = x
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

红黑树的插入红黑树的插入在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。插入的节点一般设定为红色然后再调整。

  1. 若插入的是根节点，直接变成黑色

  2. 若插入节点的父节点是黑色，则不调整颜色

  3. 若插入节点的父节点为红色（违反性质四），且父节点的兄弟节点也为红色。
    1) 把父节点及其兄弟节点变成黑色，把祖父节点变成红色（使其不违反性质五）。
    2) 再检查祖父节点是否违反红黑树的性质（一或四）

  4. 若插入节点的父节点为红色（违反性质四），且父节点的兄弟节点为黑色，且插入节点，父节点，及祖父节点同侧：把父节点变成黑色节点，把祖父节点变成红色节点，同时反向旋转祖父节点（同左则，右旋； 同右则左旋）

  5. 若插入节点的父节点为红色（违反性质四），且父节点的兄弟节点为黑色，且插入节点，父节点，及祖父节点不同侧： 旋转父节点，使期变成同侧（第 4 种情况），再根据情况 4 来处理。

具体的图解请参考：理解红黑树并实现(python3)

红黑树的删除

【参考资料】
理解红黑树并实现(python3)
教你透彻了解红黑树