【算法】二叉搜索树与红黑树

二叉搜索树与红黑树

动态集合（Dynamic Sets）

动态集合是满足这样条件的数据结构：

• 集合中每个元素有一个 key 和数据；

• 支持以下操作：Search(S, k), Minimum(S), Maximum(S), Successor(S, x), Predecessor(S, x)。

• 可能也需要支持修改操作：

  Insert(S, x), Delete(S, x)

二叉搜索树 (Binary Search Tree)

定义：是一种结点值之间具有一定数量级次序的二叉树，对于树中每个节点：

• 若其左子树存在，则其左子树中每个结点的值都不大于该结点值；
• 若其右子树存在，则其右子树中每个结点的值都不小于该结点值。

二叉树的三种遍历方式：

• 先根序：root->left->right

• 中根序：left->root->right

• 后根序：left->right->root

以中根序打印二叉搜索树时，必定是递增序列。

BST: 搜索操作

TreeSearch(x, k)
	if (x == NULL or k == key[x])
		return x; 
	if (k < key[x]) 
    return TreeSearch(left[x], k); 
	else 
    return TreeSearch(right[x], k);

另一种方式：

TreeSearch(x, k)
	while (x != NULL and k != key[x])
		if (k < key[x])
	  	x = left[x];
	  else
	  	x = right[x];
  return x;

BST: 插入操作

搜索操作中，会找到一个 NULL 位置。插入到 NULL 位置即可。（如果遇到了相同的元素呢？）

搜索和插入操作的时间复杂度为 O(h)，h 为树的高度。最坏情况下 h=n，此时时间复杂度为 O(n)。最优情况下则为 O(lgn)

BST: 后继与前驱结点

在讨论二叉搜索树结点的删除之前，需要先讨论后继结点的判定。当我们以中根序遍历 BST 时，将得到一个递增（非严格递增）序列。在这个序列中，后一个结点就是前一个结点的后继（successor）。前驱结点同理。

在 BST 中确定结点 x 的后继结点，有两种情况：

• 结点 x 有右子树：那么右子树中最左侧结点就是结点 x 的后继

• 结点 x 没有右子树：寻找 x 的祖先结点，如果有一个结点 y 是 x 的祖先，且 y 的左子结点仍然是 x 的祖先，那么满足条件的距离 x 最近的 y 就是 x 的后继。

  这样考虑的直觉是：只要向树的左侧移动，就会访问更小的结点。

BST: 删除操作

从 BST 中删除结点 x ，分三种情况讨论：

1. x 没有子结点：直接删除即可

2. x 有一个子结点：将子结点拼接到 x 的父结点即可

3. x 有两个子结点：将 x 的值与其后继结点 y 的值交换。然后删除 y（重复着三个步骤，总会得到前两点的）

为什么 情况3 总是会到达 情况2、1？

因为如果结点 x 有两个子结点，那么它的后继总是其右子树中的最小值。最小值不可能有左子树，因为这样它就不是最小的了。

也可以替换前驱结点。

红黑树

在 BST 的基础上，给结点添加颜色。每个操作都确保树高为 h=O(lgn)

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

红黑树的效率证明

定理：一棵含有n个节点的红黑树的高度至多为 2log(n+1).

逆否命题是：”高度为 h 的红黑树，它的包含的内节点个数至少为 $2^{h/2}-1$ 个”，证明其逆否命题即可。

定义： bh(x) 表示从结点 x 出发（不包括该结点），到达其每一个叶结点的路径上，黑色结点的个数。（由性质 5 可知，bh(x) 是唯一的）

数学归纳法证明：

1. 树高 h=1 时，$2^{\frac{1}{2}}-1\approx0.414$，至少有 0.414 个结点，由于树高为 1 时有一个结点，命题成立

2. 当树的高度为 h=x>0 时：

   假设树高为 x-1 时，结点数至少是 $2^{\frac{x-1}{2}}-1$

   证明树高为 x 时，结点数至少是 $2^{\frac{x}{2}}-1$ 。
   $$
   2 \cdot( 2^{\frac{x-1}{2}}-1)+1=\sqrt{2}\cdot2^{\frac{x}{2}}-1>2^{\frac{x}{2}}-1
   $$

因此，由于树高为 O(lgn)，那么对于红黑树的插入查找，后继前驱等操作的时间复杂度都是 O(lgn)

红黑树：旋转

在对红黑树进行插入和删除操作后，树的结构可能发生改变，这会导致不满足红黑树的性质。所以需要通过旋转操作，使其重新成为红黑树。

• 左旋：将一个（右）结点变为左结点（降低一级，变为子结点）。
• 右旋：将一个（左）结点变为右结点（降低一级，变为子结点）

左旋操作

LEFT-ROTATE(root, X)
	sub_r = X.right() // sub_r 表示结点 X 的右子结点
  X.right = sub_r.left // 
  
  // 将结点 X 和 结点 X.right 交换，这样 X 就变为了左结点
  prev = get_prev(X) 
	// （交换时需要判断 X 是左结点还是右结点 ...
  if prev.left == X:
		prev.left = sub_r
  else if prev.right == X:
		prev.right = sub_R
      
  // 
	sub_r.left = X

红黑树：插入操作

插入操作分为三步：

1. 以 BST 的方式插入数据。得到的结果是一个 BST 毋庸置疑，但不能保证它是一个红黑树。所以需要旋转和重新染色。

2. 将插入的结点着色为红色：原因是这样不会破坏“从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点”这条性质。

3. 但这样，可能违背的性质是：“如果一个节点是红色的，则它的子节点必须是黑色的”，即插入结点的父结点是红色的情况。

插入结点的父结点是红色时，分类讨论：

（定义：叔叔结点：当前节点的祖父节点的另一个子节点）

• 如果叔叔结点是黑色，那么可以通过旋转来解决
• 如果叔叔结点是红色，那么调整叔叔结点和父结点都是黑色，将祖父结点调整为红色，然后对祖父结点重复上述染色操作。