1. 平衡二叉树引入

  二叉查找树支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O(logn)。 不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 $log_2n$log2​n 的情况，极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。
  因此需要设计一种平衡二叉树，保证二叉树操作时间复杂度的稳定性。

2. 平衡二叉树定义

严格定义：二叉树中任意一个节点的左右子树的高度相差不能大于 1。
  从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。如下图：

  最先发明的平衡二叉查找树是AVL 树，它严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1。
  但实际应用中很多平衡二叉树并非严格的，本质上设计平衡二叉树是为了解决动态更新查找时间复杂度退化问题，而维持平衡也是一个复杂操作，因此近似平衡二叉树就是对这二者进行折中。
  所以只要树的高度不比$log_2n$log2​n大很多，尽管不严格符合平衡二叉树定义，依然算作合格，比如下面讲到的红黑树。

3. 红黑树

  “平衡”的意思可以等价为性能不退化，“近似平衡”就等价为性能不会退化的太严重。
  对于红黑树而言，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍，所以严格意义上它不是平衡二叉树。但是由于其特性，性能稳定，又趋近于平衡，因此工程上对它比较青睐，可以看到，工程和理论是可以折中考虑的。
  红黑树的定义：

1. 根节点是黑色的；
2. 每个叶子节点都是黑色的空节点（NIL），即叶子节点不存储数据；
3. 任何相邻的节点都不能同时为红色，即红色节点是被黑色节点隔开的；
4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
   如下图所示：
   

  红黑树的实现很复杂，这里并不要求掌握。学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树，也不例外。你如果能搞懂这几个问题，其实就已经足够了。

4. 红黑树的操作技巧

  红黑树的操作就像魔方一样，有固定的解法，遇到什么样的节点排布，我们就对应怎么去调整。
  介绍两个重要的操作，左旋（rotate left）、右旋（rotate right），左旋全称"围绕某个节点的左旋"，那右旋全称"围绕某个节点的右旋"。如下图所示：

  具体情形下的平衡操作比较复杂，这里不赘述了，有兴趣可找资料补充。
总结起来三点：

1. 把红黑树的平衡调整的过程比作魔方复原，不要过于深究这个算法的正确性只要按照固定的操作步骤，保持插入、删除的过程，不破坏平衡树的定义就行了。
2. 找准关注节点，不要搞丢、搞错关注节点。因为每种操作规则，都是基于关注节点来做的，只有弄对了关注节点，才能对应到正确的操作规则中。在迭代的调整过程中，关注节点在不停地改变，所以，这个过程一定要注意，不要弄丢了关注节点。
3. 插入操作的平衡调整比较简单，但是删除操作就比较复杂。针对删除操作，有两次调整，第一次是针对要删除的节点做初步调整，让调整后的红黑树继续满足第四条定义，“每个节点到可达叶子节点的路径都包含相同个数的黑色节点”。但是这个时候，第三条定义就不满足了，有可能会存在两个红色节点相邻的情况。第二次调整就是解决这个问题，让红黑树不存在相邻的红色节点。