背景

• 在传统的平衡二叉查找树（Binary Search Tree）中，最坏的情况下树可能退化成链表，这时候查找效率大大降低，时间复杂度直接降到O(n);
• 此后，AVL树诞生了，它是一种严格的自平衡二叉查找树，它可以保证树在进行操作时保持O(logn)，但是它在插入和删除节点需要进行较多的旋转操作来维持平衡，使得维护成本较高；
• B树 –> 2-3树 ，他们都来自于红黑树的实现概念。

平衡条件

1. 每个节点非黑即红
2. 根节点是黑色
3. 叶节点（NIL）是黑色
4. 如果一个节点是红色，则它的两个子节点都是黑色
5. 从根节点出发到所有叶节点路劲上，黑色节点数量相等

思考

• 红黑树中，最长路径和最短路径长度的关系？
• 怎么理解条件3中的NIL节点？ –对于梳理结构有作用就使用，否则我们可无视

算法实现思路

平衡调整法门

• 插入调整站在祖父节点看
• 删除调整站在父节点看
• 插入和删除的情况处理一共5种

23232342342343322