红黑树,add那里,加入节点之后,经过了几个if之后,怎么向上面传递保持平衡,这里还是不明白

Answer 1

liuyubobobo 2022-06-18 00:00:29

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

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

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

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

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

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

继续加油！：）

• 提问者 qq_马猴_03603137 #1

  但是add方法里面哪里有写到向上继续判断. 好像做完那三步if的判断以及翻转之后,就将x返回了,没有向上继续判断的操作了啊?

• liuyubobobo 回复 提问者 qq_马猴_03603137 #2

  https://git.imooc.com/coding-207/coding-207/src/master/13-Red-Black-Tree/08-The-Performance-of-Red-Black-Tree/src/RBTree.java 在第 k 层调用 108 行或者 110 行以后，进入第 k + 1 层的 add。在第 k + 1 层执行完 114-121 行的调整以后，执行 123 行的 return，会回到第 k 层，之后继续执行第 k 蹭的 114-121 行的调整，以此类推。
  
  返回即向上继续判断。整个递归过程是一个先从上到下之后在回去的过程。
  
  你可以再体会一下深度优先遍历的过程，为什么访问完一个节点的左子树以后，还会从左子树的孩子节点“向上回来”，去访问这个节点的右子树？
  
  如果你对此还有疑问，说明你对递归的理解有问题。请再仔细回顾一下这一小节，体会一下这一小节深入分析的递归的运行机制：https://coding.imooc.com/lesson/207.html#mid=13441 之后用这一小节的方式，找一个小的测试用例，实际单步跟踪一下，这个代码是如何一步一步运转的。最简单的方式是按照 10， 9， 8， 7， 6， 5， 4， 3， 2， 1， 的顺序添加节点，就会不断触发这个调整机制。你可以先用纸笔写一下你认为这个代码会如何运转？运转以后的树是什么样子？然后去实际单步跟踪，看一下实际是怎么运转的？哪里和你认为的不一样，自己哪里想错了？或者没有考虑到。进步就在这个过程中哦。
  
  继续加油！：）

• 提问者 qq_马猴_03603137 回复 liuyubobobo #3

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