平衡二叉树(AVL树）
# 平衡二叉树(AVL树）## 1、为什么要平衡二叉树
> 如果由数组{1, 2, 3, 4, 5}来构建一颗二叉排序树，得到的二叉树不仅没有体现其特点，反而还退化成了链表，且因为要判断左子树，查询效率比链表还低
## 2、平衡二叉树的介绍
- 平衡二叉树也叫平衡**二叉搜索树**（Self-balancing binary search tree）又被称为AVL树，可以保证**查询效率较高**
- 具有以下特点：
- **它是一棵空树**或**它的左右两个子树的高度差的绝对值不超过** **1**，并且**左右两个子树都是一棵平衡二叉树**
- 平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等
## 3、平衡二叉树的应用
### 3.1、左旋转
#### 3.1.1、应用场景
**右子树的高度高于左子树，且差值大于1**，所以需要进行**左旋转**，来降低右子树的高度
#### 3.1.2、思路分析
1. 创建一个`newRoot`新节点，值为当前节点`root`的值
2. 让新节点的左子树`newRoot.left`指向当前节点`root.left`的左子树
3. 让新节点的右子树`newRoot.right`指向当前节点的右子树的左子树`root.right.left`
4. 将当前节点的值`root.value`改为其右子树的值`root.right.value`
5. 将当前节点的右子树变为其右子树的右子树`root.right = root.right.right`
6. 让当前节点的左子树指向新节点`root.left = newRoot`
#### 3.1.3、代码实现
> 注意：
>
> 在获取树的高度的时候，精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，然后做递归
> 当左边的节点为null了，左边的递归就结束了，右边同理
```java
//核心代码
public void leftRotate() {
Node newRoot = new Node(root.value);
newRoot.left = root.left;
newRoot.right = root.right.left;
root.value = root.right.value;
root.right = root.right.right;
root.left = newRoot;
}
//取当前节点树的高度
public int getHeight() {
//精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，然后做递归
//当左边的节点为null了，左边的递归就结束了，右边同理
return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
}
//返回左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
} else {
return left.getHeight();
}
}
//返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
} else {
return right.getHeight();
}
}
```
### 3.2、右旋转
#### 3.1.1、应用场景
**左子树的高度高于右子树，且差值大于1**，所以需要进行**右旋转**，来降低左子树的高度
#### 3.1.2、思路分析(和左旋转完全相反)
1. 创建一个`newRoot`新节点，值为当前节点`root`的值
2. 让新节点的右子树`newRoot.right`指向当前节点`root.right`的右子树
3. 让新节点的左子树`newRoot.left`指向当前节点的左子树的右子树`root.left.right`
4. 将当前节点的值`root.value`改为其左子树的值`root.left.value`
5. 将当前节点的左子树变为其左子树的右子树`root.left = root.left.left`
6. 让当前节点的右子树指向新节点`root.right = newRoot`
#### 3.1.3、代码实现
```java
public void rightRotate(){
Node newRoot = new Node(root.value);
newRoot.right = root.right;
newRoot.left = root.left.right;
root.value = root.left.value;
root.left = root.left.left;
root.right = newRoot;
}
//取当前节点树的高度
public int getHeight() {
//精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，然后做递归
//当左边的节点为null了，左边的递归就结束了，右边同理
return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
}
//返回左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
} else {
return left.getHeight();
}
}
//返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
} else {
return right.getHeight();
}
}
```
### 3.3 双向旋转
#### 3.3.1、应用场景
某些时候，只进行左旋转或者右旋转，并不能将二叉排序树变为平衡二叉树。这时就需要进行**双旋转**，即**同时进行左旋转和右旋转**
#### 3.3.2、思路分析
- 进行左旋转时，如果root节点的右子树`root.right`的左子树`root.right.left`高于其右子树`root.right.right`，需要先把root节点的右子树`root.right.rightRotate()`进行右旋转，再把root节点进行左旋转`root.leftRotate()`
- 进行右旋转时，如果root节点的左子树`root.left`的右子树`root.left.right`，高于其左子树`root.left.left`，需要先把root节点的左子树`root.left.leftRotate`进行左旋转，再对root节点进行右旋转`root.rightRotate()`
#### 3.3.3、代码实现
```java
//右边比左边高，左旋转
if ((avlTree.getRoot().rightHeight() - avlTree.getRoot().leftHeight()) > 1) {
//左旋转判断是否要进行双向选择
/**
* 进行左旋转时，如果root节点的右子树`root.right`的左子树`root.right.left`高于其右子树`root.right.right`，
* 需要先把root节点的右子树`root.right.rightRotate()`进行右旋转，
* 再把root节点进行左旋转`root.leftRotate()`
*/
if (avlTree.getRoot().right.rightHeight() > avlTree.getRoot().right.leftHeight()){
//把root的右子树，进行右旋转
avlTree.rightRotate(avlTree.getRoot().right);
}
avlTree.leftRotate(avlTree.getRoot());
System.out.println(avlTree.getRoot().leftHeight());
System.out.println(avlTree.getRoot().rightHeight());
}
//左边比右边高，右旋转
if ((avlTree.getRoot().leftHeight() - avlTree.getRoot().rightHeight()) > 1) {
//右旋转判断是否要进行双向选择
/**
* 进行右旋转时，如果root节点的左子树`root.left`的右子树`root.left.right`，高于其左子树`root.left.left`，
* 需要先把root节点的左子树`root.left.leftRotate`进行左旋转，
* 再对root节点进行右旋转`root.rightRotate()`
*/
if (avlTree.getRoot().left.rightHeight() > avlTree.getRoot().left.leftHeight()){
//把root的左子树，进行左旋转
avlTree.leftRotate(avlTree.getRoot().left);
}
avlTree.rightRotate(avlTree.getRoot());
System.out.println(avlTree.getRoot().leftHeight());
System.out.println(avlTree.getRoot().rightHeight());
}
```
### 3.4 注意点
由于没有参照尚硅谷韩顺平老师的代码写，只按照思路，用自己的代码将其体现了出来。
由代码可以看出，多次获取了avlTree.getRoot，建议把root节点抽出来，这样子节省很多效率，而且代码更规范
`return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;`这一串代码老师讲述的不太清楚，我的理解如下：
在获取树的高度的时候，精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，递归了多少次，就有多少个+1，直到为null时，结束递归，最后加上本身的1，返回的就是层数，右边同理，最后把最大的那个值返回。 求解高度用向下递归感觉不好，不如从添加的这个节点向上遍历，上面节点层数逐个加一，计算量会少很多
页:
[1]