红黑树算法复杂度_红黑树删除的四种情况

树结构知识汇总 　　树结构 　　树的高度，深度，层 　　
image.png 　　二叉树 　　二叉树每个节点只能有两个叉。 　　满二叉树 　　
image.png 　　完全二叉树
image.png
image.png 　　除最后一层，其它层节点个数都要达到最大，最后一层叶子节点靠左排列（如果只有一个叉那就靠左，即优先靠左排列） 　　二叉树的遍历 　　前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。 　　遍历口诀 　　前序 　　先根节点 左顺 右顺 　　中序 　　左子树：左逆 根节点 右顺 最终到父节点 右子树：左逆 根节点 右顺 　　后续 　　左逆 右逆 根节点
image.png 　　code 　　递推公式 　　BinarySortTreeNode 　　二叉树的存储 　　二叉树的存储可以有两种方式存储 数组（顺序二叉树） 链表 　　顺序二叉树（BinarySortTree） 　　二叉树的顺序存储是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单中（数组），一般针对完全二叉树。
image.png
image.png code 　　BinarySortTreeDemo 　　输出 　　
image.png 　　二叉查找树 　　二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值
image.png 二叉查找树的查找，新增，删除 　　两种存储方式的对比 　　二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。 　　支持重复数据的二叉查找树 　　我们利用对象的某个字段作为键值（key）来构建二叉查找树。我们把对象中的其他字段叫作卫星数据。 　　针对的都是不存在键值相同的情况，有两种方式来解决： 　　1.同一个节点存储多个数据 　　利用链表或者支持动态扩容的数组。 　　2.把这个新插入的数据当作大于这个节点的值来处理 　　每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树。
image.png 查找 　　遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。
image.png 删除 　　对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。
image.png 　　二叉树的时间复杂度 　　二叉树的插入，查找，删除都和树的高度成正比，如果求出二叉树的层数公式，也就是求出二叉树数据操作的时间复杂度。 　　高度和节点的关系推导过程 　　在包含 n 个节点的满二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。 　　如果是完全二叉树中，最后一层节点小于2^(K-1)。 　　这是一个等比数列求和。 　　根据等比公式 　　
image.png 　　求L的取值范围为： 　　完全二叉树的层数小于等于 log2n +1，也就是说，完全二叉树的高度小于等于 log2n 　　通过大O理论可知其数据操作时间复杂度为:O(logn)。 　　可以看出二叉树的数据操作时间复杂度很稳定且高效，但是这个时间复杂度只适用于完全二叉树，或者满二叉树，二叉树在极端情况下可能退化成链表，所以需要对二叉树这种数据结构进行升级，让他的数据操作的时间复杂度永远符合O(logn)。 　　也就是在二叉查找树的基础上进行平衡，使之数据操作的时间复杂度永远符合时间复杂度公式O(logn)，这种升级版的二叉树结构为: 　　平衡二叉树 　　二叉查找树和散列表的对比 　　散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)。 　　二叉查找树的优势 　　散列表顺序输出困难，需要额外排序； 　　a. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。 散列表扩容代价比较大； 　　a. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。 散列表查询效率不一定比二叉树高； 　　a. 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。 散列表涉及更复杂； 　　a. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。 由于装载因子，会浪费内存； 　　a. 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。 　　平衡二叉查找树 　　
image.png 　　发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。 　　平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 　　AVLTree(Adelson-Velsky-Landis Tree) 　　一种高度平衡二叉搜索树 　　AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。 AVL树调整平衡的方式 　　左旋转
image.png 　　右旋转
image.png 　　双旋转 　　略 左旋右旋口诀 　　左旋动右给左 　　右旋动左给右 code 　　node 　　AVLTree 　　AVLTreeDemo 　　红黑树（RB-Tree） 　　为何要引入红黑树？ 　　AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。 　　红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。 红黑树的应用 　　红黑树（Red-Black Tree，以下简称RBTree）的实际应用非常广泛，比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等，各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。 　　RBTree也是函数式语言中最常用的持久数据结构之一，在计算几何中也有重要作用。值得一提的是，Java 8中HashMap的实现也因为用RBTree取代链表，性能有所提升。 红黑树的定义 任何一个节点都有颜色，黑色或者红色 根节点是黑色的 任何相邻的节点都不能同时为红色 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等（据不平衡，从而保持整体平衡） 空节点被认为是黑色的，即叶子节点是黑色的。 notice 红黑树的高度 　　红黑树是在原先的二叉查找树的基础上引入黑色节点来平衡二叉树高度，即如果将红色节点构成的树比作BSTree，其高度近似于㏒₂ⁿ 　　，那么引入红色节点的红黑树，根据红黑树的定义3,4可知，红黑树中的的最长路径（从根节点到叶子节点）即此路径上红黑节点数量相等，那么红黑树最多比BSTree高一般，即红黑树的高度近似于2㏒₂ⁿ。 　　所以，红黑树的高度只比高度平衡的 AVL 树的高度㏒₂ⁿ仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。 　　红黑树的插入 　　红黑树的插入操作可以分为两步： 　　1.插入 　　2.插入后的平衡调整 插入后的修复操作有三种情况 节点（a），父节点，叔叔节点均为红色。 　　a. 将节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色； 　　b. 将节点 a 的祖父节点 c 的颜色设置成红色； 　　c. 节点变成 a 的祖父节点 c； 　　d. 跳到 CASE 2 或者 CASE 3。
image.png 　　2.节点（a）和父节点均为红色，叔叔节点为黑色，且的节点是父节点的右子节点。 　　a. 节点变成节点 a 的父节点 b； 　　b. 围绕新的节点b 左旋； 　　c. 跳到 CASE 3。
image.png 　　3.节点(a)和父节点均为红色，叔叔节点为黑色，节点 a 是其父节点 b 的左子节点 　　a. 围绕节点 a 的祖父节点 c 右旋； 　　b. 将节点 a 的父节点 b、兄弟节点 c 的颜色互换。 　　c. 调整结束。 　　
image.png code 　　红黑树的删除 　　红黑树的删除也是分为两步： 　　1.指定节点的删除 　　2.删除节点后的平衡修复 删除修复操作分为四种情况(删除黑节点后)： 待删除的节点的兄弟节点是红色的节点。 待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。 待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的(兄弟节点在右边)，如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的。 待调整的节点的兄弟节点是黑色的节点，且右子节点是是红色的(兄弟节点在右边)，如果兄弟节点在左边，则就是对应的就是左节点是红色的。 修复完毕标志： 　　删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。 notice： 红黑树删除后的平衡实质是节点的借调 　　删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。 　　删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。 删除操作-case 1 　　由于兄弟节点是红色节点的时候，无法借调黑节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，根据RBTree的定义，兄弟节点的子节点是黑色的，就可以从它的子节点借调了。 　　case 1这样转换之后就会变成后面的case 2，case 3，或者case 4进行处理了。上升操作需要对C做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。 　　之所以要做case 1操作是因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。
image.png 删除操作-case 2 　　case 2的删除操作是由于兄弟节点可以消除一个黑色节点，因为兄弟节点和兄弟节点的子节点都是黑色的，所以可以将兄弟节点变红，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点，继续向上调整，直到整颗树的颜色符合RBTree的定义为止。 　　case 2这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合RBTree的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到了局部的平衡了，但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。
image.png 删除操作-case 3 　　case 3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成case 4状态了，在case 4状态下可以将D，E节点都阶段过来，通过将两个节点变成黑色来保证红黑树的整体平衡。 　　之所以说case-3是一个中间状态，是因为根据红黑树的定义来说，下图并不是平衡的，他是通过case 2操作完后向上回溯出现的状态。之所以会出现case 3和后面的case 4的情况，是因为可以通过借用侄子节点的红色，变成黑色来符合红黑树定义4.
image.png 删除操作-case 4 　　Case 4的操作是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的，这样的话，整棵树还是符合RBTree的定义的。 　　Case 4这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义。 　　
image.png 　　实际上这张图是错误的，最终需要将C节点变成黑色节点，因为原先节点的兄弟节点是黑色，如果变成红色则影响局部平衡了。 code