插入红黑树

Question

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

​

​

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.

1. 将节点作为红色节点插入。现在有一个红色的孩子-红色的父母违规父母是20。祖父母是22，叔叔是24。当父母和叔叔都是红色时，你可以通过反转父母，祖父母和叔叔的颜色来修复违规。现在考虑祖父母作为要修复的新节点(22)。它的父节点是15，也是红色，这是一个新的违规。新违规的
2. ：节点是22，父母是15，祖父母是15，叔叔是35。当Parent为红色而Uncle为黑色时，可以通过旋转进行修复。您可以看到Node是否位于树的内部，并围绕父15向外旋转，向左旋转。22成为25的新的左子树，颜色不变。
3. 现在在树25的根部向右旋转，加上交换树根和它的右子树的颜色来修复树。

你应该有

​

​