red-black-tree - 插入红黑树

Question

纯粹从概念上讲，我如何将 21 插入到这棵红黑树中？

标签： red-black-tree

Answer 1

1. 你找到了插入点。从根开始

Compare 21 with 25 => it is less => follow to left child
Compare 21 with 15 => it is more => follow to right child
Compare 21 with 22 => it is less => follow to left child
Compare 21 with 20 => it is more => there is no right child so you insert.

2. 将该节点作为 RED 节点插入。现在有一个红色的孩子-红色的父母违反父母是 20。祖父母是 22，叔叔是 24。当父母和叔叔都是红色时，您可以通过翻转父母、祖父母和叔叔的颜色来修复违规。现在将祖父母视为要修复的新节点 (22)。它的父母是 15 岁，也是 RED，一个新的违规行为。
3. 对于新的违规：Node 为 22，Parent 为 15，Grandparent 为 15，Uncle 为 35。当 Parent 为 RED 而 Uncle 为 BLACK 时，您轮流修复。您可以查看节点是否位于树的内部，并围绕父节点 15 向外旋转，向左旋转。22 成为 25 的新左子，颜色不变。
4. 现在在树 25 的根处向右旋转，加上交换根和它的右孩子的颜色来修复树。

你应该有