平衡二叉查找树

为何需要

防止二叉查找树，在插入删除等操作后时间复杂度退化。

经典实现

AVL、红黑树

红黑树

要求

  1. 根节点黑。
  2. 叶子是黑色空节点。（方便代码实现）
  3. 相邻节点不同时为红色。
  4. 每个节点到达叶子节点的所有路径，都包含相同颜色的黑节点。

    保证平衡的原理

    要点一：根据上面第四条可得，把红色节点删掉。形成的全黑树是个完全树（多叉）。
    要点二：把红节点插入树中，根据第三条规则，即使所有黑色都被红节点隔开，最大深度也只有2log2n。最坏情况，比AVL数的log2n大了一倍。

    优缺点

    不是严格平衡所以维护成本比AVL低。频繁插入删除性能损耗更少。AVL查找更快，但是插入删除更慢（需要极限维护平衡）。

    参考资料

    https://www.zhihu.com/question/19856999
    https://www.cnblogs.com/skywang12345/p/3245399.html