什么是平衡二叉树

• “平衡因子”（Balance Factor，BF）：左子树高度减右子树高度的值BF(T)=HL-HR
• 平衡二叉树（Balance Binary Tree）也叫AVL树，可以是空树，否则任一结点的左右子树高度差的绝对值不超过1，即 |BF(T)| ≤1
• 结点数为 n 的AVL树，最大高度为$O(log_2n)$，查找效率也为$O(log_2n)$

平衡二叉树的调整

• RR右单旋

• LL左单旋

• LR旋转

• RL旋转

• 无需调整