DS-408-新增考点-红黑树

红黑树发明的原因

为什么AVL树适合查，而红黑树适合插入、删除呢？
这是因为红黑树不是严格的平衡二叉树，对树的高度的限制比AVL树低，由于AVL树对左右子树的高度差有严格的限定，必须保证左右子树高度差不超过1，这个特性导致了插入/删除操作很容易导致了破环平衡特性，因此开销大，但是这样也有其优点，保证了高度尽可能的低，使得查找效率高。
而红黑树的任一结点的左右子树高度差不超过一倍，只要保证左根右、根叶黑、不红红、黑路同的特性，那么就是红黑树，因此限制不AVL小，导致了其高度可能会比AVL树高，导致了其查找效率比AVL树低。但是同样的红黑树的不严格特性，也有它的优点，可以使得删除、插入操作不容易破环其平衡的特性，那么就很大程度的降低了调整的开销。

红黑树的性质-左根右、根叶黑、不红红、黑路同

红黑树的插入操作

红黑树的删除操作–不大可能考

回顾

习题

性质

①②红黑树满足左<根<右，因此满足BST
③④得看情况，因为红黑树要满足左根右、根叶黑、不红红、黑路同特性，而每一颗子树必定满足 左根右、不红红、黑路同的特性，但是其子树的颜色可能是黑色、也可能是红色，导致了可能不满足根叶黑的特性，因此如果其子树的根黑色则是红黑树，否则则不是红黑树

B错误，未必是红色，黑色也是可能的。
如果所有节点都是黑色，那么要满足 黑路同特性 ，就必须是满二叉树。

①内部节点最少的红黑树情况是，全部节点都是黑色，因为如果有红色节点，是不会导致更改黑高的值的，因此如果有红色节点，那么可能树高会增加。而最少的情况是，黑高为h，那么是只有黑色节点的满二叉树，最少为2^h-1,A正确
②而黑高为h，内部节点最多的情况是，红黑树的每一条从根节点到叶子节点的路径都是红黑相间的，红黑树黑高为h，在内部节点最多的情况下，从根节点到叶节点(失败节点)的，黑色节点数是h 1个，红色节点是h个，因此内部结点最多为2^2h-1
③由于红色结点不能连续出现，因此关键字为n个，黑高>=h/2，再由①可知，n>=2^(h/2)-1,所以h<=2log2(n 1)
④红黑树是每一条路径的红色结点不会超过每一条路径的结点数目的一半，但是红色结点时有可能超过内部结点数目的一半的，因为每一层的结点数目指数倍增长，上层黑色，下层红色，交替是有可能超过内部结点数目的一半的。

红黑树的查找效率是和AVL树同一个数量级的，但是红黑树的树高是有可能比AVL树高的，导致了其查找效率降低，而插入、删除效率是比AVL树高的。
C错误

红黑树插入只需要看是否违反了不红红特性

插1，插入位置为根结点，直接染黑

插2，根据BST规则左根右插入，非根结点，直接染红。插入后判断情况调整

插3：由于插了3后，出现了2，3连续红色，违反了红黑树的不红红特性，且该插入结点的叔叔是黑色，因此需要旋转 染色，其旋转类型是RR型，调整爷(失衡结点)结点，父节点左旋，父换爷，父爷染色

旋转 染色(颜色反转)后

插入4：违反不红红特性，插入的红节点的叔叔是红色，因此父叔爷全部染色(变色)，爷结点变新结点，从新判断是否违反不红红。

染色后

而根结点不能为红色，根结点直接染黑

插入5：违反不红红特性，且插入的红节点的叔叔(父结点的兄弟结点)为黑色，该结点相对于爷结点来说是RR型，父左旋，父换爷，父爷染色。

旋转 染色后

插入6：违反不红红特性。结点6的叔叔结点3为红色，因此父叔爷染色，爷变新结点，重新判断(是否又违反不红红，根节点必为红)

染色后

插入7:违反不红红特性，结点7的叔结点为黑色，该结点相对于其爷结点，结点5来说是RR型，父结点6左旋，父换爷，父爷染色

旋转 染色后

。因此最终结果为3个红结点。

插5:根结点为黑色

插4:非根结点插入为红色

插3:违反不红红，插入结点的结点3的叔叔为黑色，因此需旋转 染色。类型为LL型，父换爷，父爷染色

旋转染色后。

插入2：违反不红红特性，结点2的叔叔为红色，因此父叔爷染色（颜色反转），爷变新，从新判断

旋转 染色后

违反根叶黑特性
根结点直接染黑

插1：违反不红红特性，结点1的叔叔为黑色，需旋转 染色。父换爷，父爷染色

旋转 染色后

因此答案为D

覆盖全部的插入情况的例子

红黑树插入：20, 10, 5, 30, 40, 57, 3, 2, 4, 35, 25, 18, 22, 23, 24, 19, 18

插入20：插入位置为根结点，直接染黑

插入10：无违反特性

插入5:违反不红红特性，其插入结点5的叔叔为黑色，需旋转 染色。为LL型，父换爷，父爷染色。

旋转

染色

插入30：违反不红红特性，插入结点的叔叔为红色（5）,父叔爷染色，爷变新，重新判断。

染色后

违反根叶黑特性，且违反的是根结点，直接染黑

插入40:违反不红红，其插入结点的叔叔为黑色，需旋转 染色，为RR型。父换爷，父爷染色

旋转后

染色后

插入57：违反不红红特性，且其插入结点的叔叔为红色，父叔爷染色，爷变新，重新判断。

染色后

插入3：没有违反不红红

插入2：违反不红红，插入结点的叔叔为黑色，需旋转 染色，类型为LL，父换爷，父爷染色

旋转后

染色后

插入4:违反不红红，插入结点4的叔叔为红色，父叔爷染色，爷变新，再判断

染色后

插入35：无违反特性

插入25:无违反红黑树特性

插入18：无违反红黑树特性

插入22：违反不红红，插入结点的叔叔为红色，父叔爷染色，爷变新，再判断

染色后：再次违反不红红特性，20的叔叔为3，为红色，父叔叔爷染色，爷变新，再判断

染色后：违反根叶黑特性，需对根结点染黑

根节点染黑

插入23：违反不红红特性，其叔叔为黑色，需旋转 染色，类型为LR型，需要两次旋转，新插入的结点先左旋，再右旋，儿换爷，儿爷染色

左旋后

右选后

儿爷染色后

插入24：违反不红红特性，插入结点的叔叔为红色，父叔爷染色，爷变新，重新判断。

染色后：再次违反不红红特性。其结点23的叔叔为40(黑色)，需旋转 染色，为LR型，23(儿)先左旋，再右旋，儿换爷，儿爷染色

左旋后

右旋后：需儿爷染色

儿爷染色后

插入19：无违反不红红特性

插入18:违反不红红特性，插入结点的叔叔为黑色，需旋转 染色，类型为RL型。18(儿结点)需先右旋，再左旋，儿换爷(18.)，儿爷染色

右旋后

左选后

儿爷染色后

该例子涵盖了所有的类型。够啦！！！！

这篇好文章是转载于：学新通技术网