8.4.2 平衡二叉树

1.平衡二叉树概念（也叫 二叉排序树）

性质：
1. 左右子树都是 平衡二叉树
2. 左右子树的高度差的绝对值<1

平衡因子：
平衡因子=右子树-左子树

在插入和删除时都要调整二叉树，使之始终保持平衡状态。

2.平衡二叉树的插入

在一颗平衡二叉树中插入一个节点，如果破坏了二叉树的平衡性，既要调整一颗 最小不平衡子树，以达到新的平衡。
例如：

平衡二叉树的插入

3.调整平衡的模式

1. LL型调整

LL

2 . RR型调整

RR

3 . LR型调整

4 . RL型调整