平衡二叉查找树

二叉查找树

二叉查找树在最好的情况下是$O(logN)$但在最坏的情况下是$O(N)$，因此需要对其进行优化。当二叉查找树中存在很多数据时，可能会出现如下的情况，如下图是一个极端的不平衡二叉查找树的例子。

AVL树

失衡处理

四种失衡情况如下图所示：

1. LL型（左左进行右旋）

   • 简单情况：

   • 复杂情况：

2. RR型（右右进行左旋）

   • 

3. LR型（左右进行左旋再右旋）

   新插入的节点位于失衡节点的左孩子的右子树上，先将失衡节点的左子树左旋，再对整体右旋

   • 

4. RL型（右左进行右旋再左旋）

总结：

参考：https://andrewpqc.github.io/2018/01/09/binary-search-tree-avl/

红黑树

参考：https://www.cnblogs.com/gaochundong/p/self_balancing_binary_search_tree.html