最近花了些时间重拾数据结构的基础知识，先尝试了红黑树，花了大半个月的时间研究其原理和实现，下面是学习到的知识和一些笔记的分享。望各位多多指教。本次代码的实现请点击：红黑树实现代码 – gist
红黑树基础知识
定义
红黑树是带有 color 属性的二叉搜索树，color 的值为红色或黑色，因此叫做红黑树。
对红黑树的每个结点的结构体定义如下：
|
1 2 3 4 5 6 7 8 |
struct RBNode { int color; void *key; void *value; struct RBNode *left; struct RBNode *right; struct RBNode *parent; }; |
设根结点的 parent 指针指向 NULL，新结点的左右孩子 left 和 right 指向 NULL。叶子结点是 NULL。
定义判断红黑树颜色的宏为
|
1 |
#define ISRED(x) ((x) != NULL && (x)->color == RED) |
因此，叶子结点 NULL 的颜色为非红色，在红黑树中，它就是黑色，包括黑色的叶子结点。
黑高的定义，从某个结点 x 触发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高（black-height），记作 bh(x)。
红黑树的性质
- 每个节点不是红色就是黑色；
- 根节点是黑色；
- 每个叶子节点是黑色；
- 如果节点是红色，那么它的两个孩子节点都是黑色的；
- 对每个节点来说，从节点到叶子节点的路径包含相同数目的黑色节点。
下面是一个红黑树的例子
红黑树的旋转
旋转操作在树的数据结构里面很经常出现，比如 AVL 树，红黑树等等。很多人都了解旋转的操作是怎么进行的（HOW），在网上能找到很多资料描述旋转的步骤，但是却没有人告诉我为什么要进行旋转（WHY）？为什么要这样旋转？通过与朋友交流，对于红黑树来说，之所以要旋转是因为左右子树的高度不平衡，即左子树比右子树高或者右子树比左子树高。那么，以左旋为例，通过左旋转，就可以将左子树的黑高 +1，同时右子树的黑高 -1，从而恢复左右子树黑高平衡。
以右旋为例，α 和 β 为 x 的左右孩子，γ 为 y 的右孩子，因为 y 的左子树比右子树高度多一，因此以 y 为根的子树左右高度不平衡，那么以 y-x 为轴左旋使其左右高度平衡，左旋之后 y 和 β 同时成为 x 的右孩子，然而因为要旋转的是 x 和 y 结点，因此就让 β 成为 y 的左孩子即可。
旋转的算法复杂度：从图示可知，旋转的操作只是做了修改指针的操作，因此算法复杂度是 O(1)。
红黑树的算法复杂度分析
红黑树的所有操作的算法复杂度都是 O(lgn)。这是因为红黑树的最大高度是 2lg(n+1)。
证明如下：
设每个路径的黑色节点的数量为 bh(x)，要证明红黑树的最大高度是 2lg(n+1)，首先证明任何子树包含 2^bh(x) - 1 个内部节点。
下面使用数学归纳法证明。
当 bh(x) 等于 0 时，即有 0 个节点，那么子树包含 2^0 - 1 = 0 个内部节点，得证。
对于其他节点，其黑高为 bh(x) 或 bh(x) - 1，当 x 是红节点时，黑高为 bh(x)，否则，为 bh(x) - 1。对于下一个节点，因为每个孩子节点都比父节点的高度低，因此归纳假设每个子节点至少有 2^bh(x)-1 - 1 个内部节点，因此，以 x 为根的子树至少有 2^(bh(x)-1) - 1 + 2^(bh(x)-1) - 1 = 2^bh(x) - 1个内部节点。
设 h 是树高，根据性质 4 可知道，每一条路径至少有一半的节点是黑的，因此 bh(x) - 1 = h/2。
那么红黑树节点个数就为 n >= 2^h/2 - 1。
可得 n + 1 >= 2^h/2。两边取对数得：
|
1 2 3 4 5 |
log(n+1) >= h/2 => 2log(n+1) >= h => h <= 2log(n+1) |
由上面的证明可得，红黑树的高度最大值是 2log(n+1)，因此红黑树查找的复杂度为 O(lgn)。对于红黑树的插入和删除操作，算法复杂度也是 O(lgn)，因此红黑树的所有操作都是 O(lgn)的复杂度。
红黑树的插入操作分析
红黑树的插入操作，先找到要新节点插入的位置，将节点赋予红色，然后插入新节点。最后做红黑树性质的修复。
新节点赋予红色的原因
因为插入操作只可能会违反性质 2、4、5，对于性质 2，只需要直接将根节点变黑即可；那么需要处理的就有性质 4 和性质 5，如果插入的是黑节点，那么就会影响新节点所在子树的黑高，这样一来就会违反性质 5，如果新节点是红色，那么新插入的节点就不会违反性质 5，只需要处理违反性质 2 或性质 4 的情况。即根节点为红色或者存在两个连续的红节点。简而言之，就是减少修复红黑性质被破坏的情况。
插入算法伪代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
RB-INSERT(T, node) walk = T.root prev = NULL while (walk != NULL) prev = walk if (node.key < walk.key) walk = walk.left else walk = walk.right node.parent = walk if (walk == NULL) T.root = node else if (node.key < walk.key) walk.left = node else walk.right = node RB-INSERT-FIXUP(T, node) |
插入算法流程图
插入的修复
插入之后，如果新结点（node）的父结点（parent）或者根节点（root）是红色，那么就会违反了红黑树的性质 4 或性质 2。对于后者，只需要直接将 root 变黑即可。
而前者，违反了性质 4 的，即红黑树出现了连续两个红结点的情况。修复的变化还要看父结点是祖父结点的左孩子还是右孩子，左右两种情况是对称的，此处看父结点是祖父结点的左孩子的情况。要恢复红黑树的性质，那么就需要将 parent 的其中一个变黑，这样的话，该结点所在的子树的黑高 +1，这样就会破坏了性质 5，违背了初衷。因此需要将 parent->parent(grandparent)的另一个结点（uncle 结点）的黑高也 +1 来维持红黑树的性质。
如果 uncle 是红色，那么直接将 uncle 变为黑色，同时 parent 也变黑。但是这样一来，以 grandparent 为根所在的子树的黑高就 +1，因此将 grandparent 变红使其黑高减一，然后将 node 指向 grandparent，让修复结点上升两个 level，直到遇到根结点为止。
如果 uncle 是黑色，那么就不能将 uncle 变黑了。那么只能将红节点上升给祖父节点，即将祖父结点变红，然后将父结点变黑，这样一来，以父结点为根的子树的左右子树就不平衡了，此时左子树比右子树的黑高多 1，那么就需要通过将祖父结点右旋以调整左右平衡。
插入修复算法的伪代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
RB-INSERT-FIXUP(T, node) while IS_RED(node) parent = node->parent if !IS_RED(parent) break grandparent = parent->parent if parent == grandparent.left arget="_blank">专栏作者。 最近花了些时间重拾数据结构的基础知识，先尝试了红黑树，花了大半个月的时间研究其原理和实现，下面是学习到的知识和一些笔记的分享。望各位多多指教。本次代码的实现请点击：红黑树实现代码 – gist 红黑树基础知识定义红黑树是带有 color 属性的二叉搜索树，color 的值为红色或黑色，因此叫做红黑树。 对红黑树的每个结点的结构体定义如下：
设根结点的 parent 指针指向 NULL，新结点的左右孩子 left 和 right 指向 NULL。叶子结点是 NULL。 定义判断红黑树颜色的宏为
因此，叶子结点 NULL 的颜色为非红色，在红黑树中，它就是黑色，包括黑色的叶子结点。 黑高的定义，从某个结点 x 触发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高（black-height），记作 bh(x)。 红黑树的性质
下面是一个红黑树的例子
红黑树的旋转旋转操作在树的数据结构里面很经常出现，比如 AVL 树，红黑树等等。很多人都了解旋转的操作是怎么进行的（HOW），在网上能找到很多资料描述旋转的步骤，但是却没有人告诉我为什么要进行旋转（WHY）？为什么要这样旋转？通过与朋友交流，对于红黑树来说，之所以要旋转是因为左右子树的高度不平衡，即左子树比右子树高或者右子树比左子树高。那么，以左旋为例，通过左旋转，就可以将左子树的黑高 +1，同时右子树的黑高 -1，从而恢复左右子树黑高平衡。
以右旋为例，α 和 β 为 x 的左右孩子，γ 为 y 的右孩子，因为 y 的左子树比右子树高度多一，因此以 y 为根的子树左右高度不平衡，那么以 y-x 为轴左旋使其左右高度平衡，左旋之后 y 和 β 同时成为 x 的右孩子，然而因为要旋转的是 x 和 y 结点，因此就让 β 成为 y 的左孩子即可。 旋转的算法复杂度：从图示可知，旋转的操作只是做了修改指针的操作，因此算法复杂度是 O(1)。 红黑树的算法复杂度分析红黑树的所有操作的算法复杂度都是 O(lgn)。这是因为红黑树的最大高度是 2lg(n+1)。 证明如下： 设每个路径的黑色节点的数量为 bh(x) 下面使用数学归纳法证明。 当 bh(x) 等于 0 时，即有 0 个节点，那么子树包含 2^0 - 1 = 0 个内部节点，得证。 对于其他节点，其黑高为 bh(x) 或 bh(x) - 1，当 x 是红节点时，黑高为 bh(x)，否则，为 bh(x) - 1。对于下一个节点，因为每个孩子节点都比父节点的高度低，因此归纳假设每个子节点至少有 2^bh(x)-1 - 1 个内部节点，因此，以 x 为根的子树至少有 2^(bh(x)-1) - 1 + 2^(bh(x)-1) - 1 = 2^bh(x) - 1个内部节点。 设 h 是树高，根据性质 4 可知道，每一条路径至少有一半的节点是黑的，因此 bh(x) - 1 = h/2。 那么红黑树节点个数就为 n >= 2^h/2 - 1。 可得 n + 1 >= 2^h/2。两边取对数得：
由上面的证明可得，红黑树的高度最大值是 2log(n+1)，因此红黑树查找的复杂度为 O(lgn)。对于红黑树的插入和删除操作，算法复杂度也是 O(lgn)，因此红黑树的所有操作都是 O(lgn)的复杂度。 红黑树的插入操作分析
新节点赋予红色的原因因为插入操作只可能会违反性质 2、4、5，对于性质 2，只需要直接将根节点变黑即可；那么需要处理的就有性质 4 和性质 5，如果插入的是黑节点，那么就会影响新节点所在子树的黑高，这样一来就会违反性质 5，如果新节点是红色，那么新插入的节点就不会违反性质 5，只需要处理违反性质 2 或性质 4 的情况。即根节点为红色或者存在两个连续的红节点。简而言之，就是减少修复红黑性质被破坏的情况。 插入算法伪代码
插入算法流程图
插入的修复插入之后，如果新结点（node）的父结点（parent）或者根节点（root）是红色，那么就会违反了红黑树的性质 4 或性质 2。对于后者，只需要直接将 root 变黑即可。 而前者，违反了性质 4 的，即红黑树出现了连续两个红结点的情况。修复的变化还要看父结点是祖父结点的左孩子还是右孩子，左右两种情况是对称的，此处看父结点是祖父结点的左孩子的情况。要恢复红黑树的性质，那么就需要将 parent 的其中一个变黑，这样的话，该结点所在的子树的黑高 +1，这样就会破坏了性质 5，违背了初衷。因此需要将 parent->parent(grandparent)的另一个结点（uncle 结点）的黑高也 +1 来维持红黑树的性质。 如果 uncle 是红色，那么直接将 uncle 变为黑色，同时 parent 也变黑。但是这样一来，以 grandparent 为根所在的子树的黑高就 +1，因此将 grandparent 变红使其黑高减一，然后将 node 指向 grandparent，让修复结点上升两个 level，直到遇到根结点为止。 如果 uncle 是黑色，那么就不能将 uncle 变黑了。那么只能将红节点上升给祖父节点，即将祖父结点变红，然后将父结点变黑，这样一来，以父结点为根的子树的左右子树就不平衡了，此时左子树比右子树的黑高多 1，那么就需要通过将祖父结点右旋以调整左右平衡。 插入修复算法的伪代码
|
