文章目录
- 22.1.3 平衡二叉树
- 22.1.3.1 LL
- 22.1.3.2 LR
- 22.1.3.3 RR
- 22.1.3.4 RL
22.1.3 平衡二叉树
平衡二叉树的特点：
- 二叉树左右两个子树的高度差不超过1
- 任意节点的左右两个子树都是一颗平衡二叉树
在原来的平衡二叉树中，新增数据会破坏平衡性，所以需要进行旋转最小不平衡子树保持平衡。
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点。
右旋：
1.以不平衡的点作为支点
2.将根节点的左侧往右拉
3.原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点。
左旋：
1.以不平衡的点作为支点
2.将根节点的右侧往左拉
3.原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点。
22.1.3.1 LL
左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡。
以不平衡的点作为支点，进行一次右旋即可。
如图：分别新增数据 1 和 3在根节点左子树的左子树 ，破环了原有的平衡性，需要右旋一次。可知 7 为不平衡的节点，将7 作为支点进行右旋
右旋一次后，如图：
22.1.3.2 LR
左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡。
需要先局部左旋，再整体右旋。
如图，新插入 数据6 在根节点左子树的右子树，破环平衡，需要先局部左旋，再整体右旋。
先局部左旋：
再整体右旋：
22.1.3.3 RR
右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡。
以不平衡的点作为支点，进行一次左旋即可。
22.1.3.4 RL
右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡。
需要先局部右旋，再整体左旋。
如图，新插入 数据68在根节点右子树的左子树，破环平衡，需要先局部右旋，再整体左旋。
先局部右旋，如图：
再整体左旋，如图：
