删除|字节算法大神熬了三个通宵整理的数据结构与算法笔记（万字长文）( 六 )

2. 二叉树的遍历方式有三种：前序、中序和后序遍历；在二叉树中，二叉查找树最常用，可以快速查找、插入、删除一个元素；
3. 堆是一种特殊的树：它是完全二叉树；且每个节点的值都大于等于（或小于等于）子树中每个节点的值（分别为大顶堆和小顶堆）。
数据结构与算法笔记（四）平衡二叉树
二叉查找树支持快速插入、删除、查找操作，各个操作时间跟树的高度成正比，理想情况下，时间复杂度为O(logn) 。但是，在极端的情况下，二叉树会退化成链表（比如按顺序插入一组数据），时间复杂度会退化到O(n) 。
为了解决这种问题，就有了平衡二叉树，红黑树就是平衡二叉树中的一种。
平衡二叉树的严格定义：二叉树中任意一个节点的左右子树的高度差不能大于 1 。示意图如下：

最先被发明的平衡二叉查找树是 AVL 树，它严格符合上述定义，是一种高度平衡的二叉查找树。但是，很多平衡二叉查找树并未严格符合上述定义，比如经典的红黑树。
PS: 平衡二叉树发明的初衷是为了解决普通二叉查找树在极端情况下退化成链表，插入、删除等操作复杂度增加的问题。而“平衡”的意思就是让整棵树的左右子树比较均衡，从而使整棵树的高度相对低一些，插入、删除等操作效率更高。因此，尽管有些二叉树没有严格符合平衡二叉查找树的定义，但只要树的高度没有比logn大很多，仍然可以认为它是一棵平衡二叉树。
红黑树
红黑树（Red-Black Tree），简称R-B Tree ，它的每个节点都有颜色（红与黑）属性，是“出场率”很高的二叉树，它是一种不严格的平衡二叉树。示意图如下：

红黑树需要满足以下几个约束：
1. 节点是红色或黑色；
2. 根节点是黑色；
3. 所有叶子节点都是黑色（叶子是 NIL 节点）；
4. 每个红色节点必须有两个黑色的子节点（从每个叶子到根节点的所有路径上不能有两个连续的红色节点）；
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
PS: 上面说的“叶节点”或“NIL节点” ，不包含数据而只是充当树在此结束的指示，绘图中通常被省略。
平衡性调整
红黑树在插入或删除节点的过程中，上述第 3、4 点性质可能会被破坏，为了让它重新保持红黑树的性质，需要进行平衡性调整。
平衡性调整操作主要包括旋转（结构调整）和着色（红黑转换），其中旋转又分为左旋（rotate left）和右旋（rotate right）两个操作，左旋指的是围绕某个节点的左旋，右旋同理。左旋和右旋的操作示意图如下：

插入操作
红黑树规定，插入的节点必须是红色的。插入的情况分为多种，下面两种情况无须进行旋转操作：
1. 若插入节点的父节点是黑色的，则无需操作，仍满足红黑树的定义；
2. 若插入节点是根节点，那么直接将它变为黑色即可。
除此之外的其他情况都会违背红黑树的定义，需要进行平衡性调整（旋转和着色）。
case1
关注节点为 a ，它的叔叔节点 d 为红色。则进行如下操作：
1. 将 a 的父节点 b、叔叔节点 d 的颜色都设置为黑色；
2. 将 a 的祖父节点 c 的颜色设置为红色；
3. 关注节点变成 a 的祖父节点 c；
4. 跳到 case2 或 case3 。
操作示意图如下：

case2
关注节点是 a ，它的叔叔节点 d 是黑色， a 是其父节点 b 的右子节点。则进行如下操作：
1. 关注节点变成 a 的父节点 b；
2. 围绕 b 左旋；
3. 跳到 case3 。