红黑树、二叉树

红黑树应用比较广泛，主要用于存储有序的数据，插入、删除、查找的事件复杂度O(lgn)，效率非常之高。例如：Linux虚拟内存管理、Java中的TreeMap和TreeSet、以及JDK1.8之后的HashMap也有用到红黑树数据结构

20

10

相关术语：- 结点：包含一个数据元素以及指向子树的连接- 子结点：结点的子树- 父结点：与子结点相逆- 兄弟结点：属于同一个父结点的两个子结点互为兄弟结点- 根结点：二叉树最上层的结点- 叶子结点：二叉树最底层的结点- 树的高度：又称深度，结点的层数，根结点为第一层- 结点的度：结点的子结点个数- 树的度：最大的结点度

NIL

完全二叉树

X

u

92

gp

二叉树概念：二叉树是一种数据结构，每个结点最多右两个子树的树结构

3.3.2

左旋

x(p)

结点插入：1. 二叉查找树的方式查找新结点位置并插入2. 新结点染成红色3. 按情况修复红黑树 3.1 插入结点无父结点： 说明插入的结点是根结点，直接做根结点染黑的操作即可 3.2 插入结点的父结点是黑色： 未破坏红黑树，无需额外的操作 3.3 插入结点的父结点是红色： 会破坏红黑树，需要额外操作以恢复红黑规则，中心思想是将新插入的多余的红色因子往上移，直至根部，在上移的过程中，可能会有以下三种情况分别处理（以父结点是祖父结点的左子结点为例） 1）叔叔是红色： a. 父结点和叔叔结点染黑 b. 祖父结点染红 c. 祖父结点设为当前结点（达到红色因子上移的效果） 2）叔叔是黑色，当前结点是右子结点 a. 以父结点为支点，左旋操作 b. 父结点和当前结点角色互换（变成了第三种情况） 3）叔叔是黑色，当前结点是左子结点（该情况下可以恢复规则，结束循环） a. 父结点染黑、祖父结点染红 b. 以祖父结点为支点，右旋操作，恢复红黑规则

#2

82

YL

93

YR

Y

#1

二叉树总结

p(x)

红黑树的主要操作有左旋、右旋、结点插入、结点删除等。左旋：当红黑树向右偏斜时（右子结点较重），需要使用左旋操作使其平衡，具体的操作步骤如下1. 断开右子结点和当前结点的关系，并将右子结点的左结点移到当前结点的右结点位置2. 处理分离的右子结点分支和当前结点的父结点关系（代替当前结点成为父结点的子分支）3. 处理分离的右子结点分支和当前结点关系（成为当前结点的父结点）右旋：当红黑树向左偏移时的操作，和左旋一样只是方向相反

80

81

40

3.3.3

90

满二叉树

p

右旋

x

91

XL

50

变色

红黑树是一种二叉查找数，每个结点都有颜色（红或黑），红黑树需要满足下面五个特性：1. 每个结点都是红色或者黑色2. 根结点是黑色3. 红色结点的子结点必须是黑色4. 每个叶子结点都是黑色（叶子结点都是指空NIL的叶子结点）5. 从根结点到达每个叶子结点的路径上黑色结点的数量是相同的（这样可以确保最长的路径不会多于最短路径的一倍，因此红黑树是相对平衡的二叉树）

60

特殊的二叉树：- 完全二叉树： 1）第1~n-1层的结点数达到最大个数 2）第n层的叶子结点从左到右依次排布- 满二叉树：第n层也达到最大个数的完全二叉树- 平衡二叉树： 1）左右两个子树的高度差不超过1 2）左右子树也都是平衡二叉树

红黑树总结

#3

结点删除：1. 二叉树的方式删除结点，分以下三种情况： a）被删除结点没有子结点，即叶结点，直接删除 b）被删除结点有一个子结点，直接删除该结点，并用子结点顶替它 c）被删除结点右两个子结点，①先找出它的后继结点；②将后继结点的内容复制给该结点；③删除后继结点；**因为当前结点有两个子结点所以它的后继结点一定在他的右子分支上而且后继结点最多有一个子结点(右)，所以在删除后继结点时按\"情况①\"或\"情况②\"处理即可。2. 按情况旋转着色修复红黑树，删除结点y之后，结点x替代原来结点y的位置，如果删除的结点y是红色不会破坏红黑树的结构，所以我们只考虑y是黑色的情况。既然删除的y是黑色也就意味着路径上会少一个黑色的数目，那么我们在x上增加一个额外的黑色以保证路径上的黑色数目，这样可以概括为三种情况： 2.1 x是\"红+黑\"结点：直接设置x为黑色，恢复规则 2.2 x是\"黑+黑\"且是根结点：直接设置x为黑色，恢复规则 2.3 x是\"黑+黑\"结点且不是根结点，又可以分成四种子情况分别处理（以x为其父结点的左分支为例）： 1）x的兄弟结点是红色：转化成#2、#3或#4的情况 a. 兄弟结点染黑，父结点染红 b. 以父结点为支点左旋 c. 左旋后，x的兄弟结点变成了原兄弟的左子结点（原兄弟结点为红色，其子结点必为黑色，因此转成了#2、#3或#4的情况） 2）x的兄弟结点是黑色，且兄弟的两个子结点都是黑色 a. 兄弟结点染红 b. 父结点设为当前结点（将额外的黑色因子上移到父结点上） 3）x的兄弟结点是黑色，且兄弟的左子结点是红色，右子结点是黑色 a. 兄弟结点染红，兄弟的左子染黑 b. 以兄弟结点为支点右旋 c. 右旋后，x的兄弟结点变成了原兄弟的左子结点，原兄弟结点变成了现兄弟结点的右子结点且为红色（转成了#4的情况） 4）x的兄弟结点是黑色，且兄弟的右子结点是红色 a. 兄弟结点染成父结点颜色，父结点染黑 b. 兄弟的右子结点染黑 c. 以父结点为支点左旋 d. 设置x为根结点，跳出循环（转成2.2的情况）