平衡二叉搜索树

一、常见的平衡树

• AVL Tree
• RB Tree

二、AVL树

2.1 最小不平衡子树

• 平衡因子

图解

2.2 AVL树的失衡调整

• 调节的宗旨——

1. 消灭平衡因子
2. 保证依然是搜索二叉树

2.3 左单旋(RR)

2.4 右单旋(LL)