红黑树

什么是平衡二叉查找树？

• 严格定义：二叉树中任意一个节点的左右子树的高度相差不能大于1。从这个定义上看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也可能是平衡二叉树。
• 很多平衡二叉查找树并没有符合严格定义，比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
• 平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
• 所以如果我们要设计一个新的平衡二叉查找树，只要树的高度不比log2n大很多，尽管它不符合平衡二叉查找树的严格定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。

红黑树的定义要求

1、红黑树中的节点，一类被标记为黑色，一类被标记为红色。
2、根节点是黑色的。
3、每个叶子节点都是黑色的空节点（NIL）为了简化红黑树的代码实现而设置，也就是说，叶子节点不存储数据。
4、任何相邻的节点不可能同时为红色，也就是说，红色节点是被黑色节点隔开的。
5、每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

怎样判断红黑树是近似平衡的？

• 平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。
• 二叉查找树很多操作的性能都跟树的高度成正比。一棵及其平衡的二叉树（满二叉树或平衡二叉树）的高度大约是log2n，所以如果要证明红黑树是近似平衡的，只需要分析红黑树的高度是否比较稳定地趋近log2n就好了。

• 嘴推一波：看👇图，根据红黑树定义要求5，我们将所有红色节点拿开，那么最多会得到一个从根节点到各个叶子节点都等高的四叉树（根节点的左右节点都是红色时），通过从四叉树中抽取某些节点，放到叶子节点位置，可以将四叉树变为完全二叉树，并且这个完全二叉树仅仅包含黑色节点，还没算红色的，此时它的高度小于包含相同节点个数（红+黑）的完全二叉树的高度。而完全二叉树的高度近似log2n，所以此时仅包含黑色节点的完全二叉树的高度小于log2n。
  　　那么现在把红色节点再放回去，按照红黑树定义要求4，任何相邻节点不可能同时为红色，也就是说有一个红色节点至少就要有一个黑色节点，将它跟其他红色节点隔开。仅包含黑色节点的路径长度不会超过log2n，所以加入红色节点后，最长路径不会超过2*log2n，也就是说红黑树的高度近似2log2n。这在性能上，比高度平衡的AVL树仅仅大了1倍，相差的并不多。（实际上红黑树的性能更好）

  
  image

红黑树小结

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
　　因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，如果自己写代码实现，难度会有些高，这个时候，我们其实更倾向用跳表来替代它。