1回答

liuyubobobo

2022-06-18

首先明确一点，红黑树中说的平衡，不是 AVL 树中定义的平衡，而是红黑树自己定义的平衡，即黑平衡。（既能按照课程中的方式，转换成一棵 2-3 树。）

打破这种黑平衡的方式，就是“同时出现了两个红节点”，这两个红节点或者以"左右"的形式出现，或者以“左左”的形式出现，或者以一个黑节点的左右节点的形式出现，即下面 ppt 中的 2，3，4 三种情况。

（为什么只有这三种情况？因为我们的红黑树是左倾的，如果有一个本身）有一个红节点，这个红节点一定在一个黑节点的左边。即图1的情况。）

我们的逻辑将所有这种打破黑平衡的情况，最终都在当前子树的范围内，调整成了根节点是红节点的情况，即上面图 5 的情况。即我们把两个红节点化成了一个红节点。

那么这个根节点是红节点的子树，往上回溯，对应到上一层，如果不平衡，一定是在上一层的范围里，再次出现了上图中2,3,4的情况之一，那么就继续这样调整（否则平衡了，就不用调整了。）。

因此一直往上回溯上去，就保持了平衡。

继续加油！：）

0

3

qq_马猴_03603137

回复

liuyubobobo

原来如此,每一次方法弹出栈就会继续执行递归下面的代码.对递归不是很熟

2022-06-20

共3条回复