AVL、红黑树

AVL树：高度平衡的二叉树
空树，或者任一结点左、右子树高度差的绝对值不超过1的二叉树

红黑树：一种特化的AVL树
在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能

1. 节点是红色或黑色
2. 根节点是黑色
3. 每个叶子节点都是黑色的空节点
4. 每个红色节点的两个子节点都是黑色，即一条路径不能连续出现红节点
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

由5->如果一个结点存在黑子结点，那么该结点肯定有两个子结点

红黑树并不是一个高度平衡二叉查找树，这种平衡为黑色完美平衡，总是通过旋转和变色达到自平衡

插入节点是红色的

• 红黑树为空树->直接插入并变为黑节点
• 插入结点的Key已存在->把插入结点设置为将要替代结点的颜色，再把结点的Value更新
• 插入结点的父结点为黑结点->直接插入
• 插入结点的父结点为红结点、兄弟结点存在且为红结点->变换颜色并移动插入节点指针（可能破坏了上层）

• 插入结点的父结点为红结点、兄弟结点不存在或为黑结点->先理成一边顺，再次左旋/右旋

**

红黑树不追求“完全平衡”，只要求部分达到平衡，但是提出了为节点增加颜色，红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多
插入节点导致树失衡的情况，AVL 和 RB-Tree 都是最多两次树旋转来实现复衡，旋转的量级是O(1)
删除节点导致失衡，AVL 需要维护从被删除节点到根节点 root 这条路径上所有节点的平衡，旋转的量级为O(logN)，而 RB-Tree 最多只需要旋转3次实现复衡，只需O(1)，RB-Tree删除节点的rebalance的效率更高

实际应用中，若搜索的次数远远大于插入和删除，选择AVL，如果搜索，插入删除次数几乎差不多，选择RB