红黑树

概述

红黑树是在 AVL 的基础上发展来的. 红黑树也是一种平衡二叉树, 但是其没有 AVL这么严格. 从而避免了AVL的大量的翻转. 红黑树包含以下特性:

1. 节点只有红黑两色
2. 根节点是黑色
3. 叶子节点(准确的说是空节点,是不真实存在的节点)是黑色
4. 红色节点的儿子是黑色
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点.(定义为黑高)

红黑树插入最多两次旋转, 删除最多三次旋转.

插入

红黑树的插入分两部分, 第一部分是直接插入, 就像普通的BST一样, 第二部分是维护性质的调整. 这里着重研究第二部分.

首先第一个节点, 也就是根节点, 直接插入一个黑色节点即可. 在调整函数的最后一行就是无论根节点是什么颜色(因为可能涉及到选择) 第二层的节点(也就是根节点的儿子), 插入一个红色节点即可. 以上两点我们可以直接简化为, 插入一个红色节点, 调整完将根节点置黑即可.

因此我们讨论的重点是第三层及以后的节点, 也就是每个节点一定有 祖父 , 可能有 叔父 , 这就是我们讨论的核心.

我们仔细思考插入一个红色节点带来的效应. 其实对于上述的五个规则, 只可能破坏第四个, 也就是插入节点的父节点可能也是红色的. 只有这一种可能, 如果父节点是黑色, 那么我们的插入不需要任何更改.

父节点是红色, 也就注定了祖父节点是黑色(同样是基于第四点, 两个红色不能为父子关系).

感悟

其实插入的话最重要的就是维护 红色节点的儿子是黑色 和 任何节点到它叶子节点的高度都相同

我们不难发现, 对于祖父子树来说, 无论是父子树还是叔父子树, 其黑高都相同. 而且我们的原则是新插入的节点, 除非是根节点, 其他情况肯定是红色.

• 如果父节点是黑色, 那么插入新节点不会有任何影响, 因为红色节点不会影响黑高.

• 如果父节点是红色, 肯定祖父节点是黑色. 因为我们不改变刚插入的节点的颜色, 那么势必要将父节点变色. 但是变色就必然影响黑高.

  • 如果叔父节点也是红色, 我们就发现, 祖父节点, 父节点, 叔父节点同时将颜色反过来, 不会影响黑高(对于这三个子树). 而带来的唯一问题就是祖父节点和它父亲的问题, 这个就可以递归处理了(以下内容是递归实现, 并非真正编码), 毕竟对于祖父上面的树来说, 祖父子树的黑高没变, 还是只可能仅违反了红色的儿子是黑色的原则.(后续的递归是否完全等价还得进一步思考), 这样后续的问题就是祖父节点的父节点的变色问题, 这里的问题还需要讨论祖父节点的位置是内侧还是外侧.
    • 如果是外侧, 解决这个问题完全可以把祖父子树看成一个整体(或者说是一个黑高比较大的红色节点, 无需考虑内部结构),因为在后续的旋转中不会受影响.
    • 如果是内侧, 虽然经过了一次旋转(下文提到)调整到外侧, 一个子树被挪给了父节点, 但是由于自身和父节点都是红色的, 所以还是没影响树高,就转换为了上述的外侧情况. 问题得以递归处理.
  • 如果叔父节点是黑色. 刚才的变色的方法就无效了. 因为如果变色的话, 假如原来祖父子树黑高是h, 父子树和叔父子树的黑高都是h-1. 那我们就干脆别动叔父节点了, 我们只修改父节点和祖父节点的颜色, 也就是父子树黑高h, 叔父子树黑高h-1, 祖父节点变成红色. 然后现在还是不平均, 我们就右旋祖父子树, 让父节点成为这个子树的根, 然后现在的左右子树黑高都是h-1了(注意父节点也可能在之前有右子树, 黑高为h-1, 旋转过程中右子树会跑到另一边, 但是可见其黑高和父节点左子树也就是旋转后的左子树相同, 而祖父节点又是红色的, 所以不会影响整体黑高), 整体的黑高是h, 然后根也是黑色的, 不存在向上的冲突, 问题解决.

关于上述的分析在叔父节点黑色的情况下少了一个过程: 就是如果插入到二叉树内侧, 需要通过旋转来转换到外侧. 以左子树内侧为例, 这个是因为, 叔父节点如果是黑色, 就必须面临祖父节点的右旋, 而右旋的时候, 就不可避免的接管父节点的右子树, 而根据上面的递归问题(也就是矛盾向上传导), 如果一个具有很大黑高的红色节点(或者红色子树)被交换到另一侧, 势必导致黑高的不等. 所以要通过旋转保证插入到外侧(也就是交换父子关系, 也就是转化为新的节点是原来的父节点, 然后刚插入的节点是现在的父节点).

• Previous
  「CodeNote」 AVL
• Next
  「计算机网络」 计算机网络基础知识