首先来介绍一下什么是AVL（平衡搜索二叉树），我们都知道BST（搜素二叉树）在查询某个值的时候时间复杂度可以达到O(logn)，但这个时间复杂度是最好的，如果按照BST树的插入，我要按顺序插入1，2，3，4，5这几个数字，那么最终的BST树是这样的
这棵树的所有节点的左孩子都为空，这样不就成了一个链表了，如果要搜索一个数字，那么时间复杂度就为O(n)，AVL就是使这棵BST树平衡的一种策略，所以AVL也可以理解为平衡的BST树。
AVL树的定义是：该树的所有节点的左右子树高度不超过1
举个例子，下图就是一个平衡的BST树
现在来了解一下AVL树是怎么样保持平衡的
了解AVL树之前，先了解AVL树的几个旋转操作
- 左孩子的左子树高
Java实现AVL：平衡搜索二叉树 首先需要注意这里的x不管有没有都可以定义为左孩子的左子树太高了。
左孩子的左子树太高时，该节点需要进行右旋，也就是40旋转下来，这时为了保持BST树的性质，所以x就得插到40的左边
伪代码：
child = node.left;
node.left = child.right;
chlid.right = node;
- 右孩子的右子树高 右孩子的右子树太高了，该节点进行左旋，也就是40从左边旋转下来，x插入到40的右边以保证BST树的性质。
Java实现AVL：平衡搜索二叉树
伪代码：
child = node.right;
node.right = child.left;
child.left = node;
- 左孩子的右子树高 可以看到导致不平衡的原因是40的左孩子的右子树，这时候如果对node直接进行右旋操作，那么旋转完还是不平衡的，见下图：
Java实现AVL：平衡搜索二叉树 解决方法是我们需要先对node的左孩子进行左旋转，然后再对node进行右旋转，也叫左平衡。见下图： Java实现AVL：平衡搜索二叉树 Java实现AVL：平衡搜索二叉树 -
右孩子的左子树高
与情况3同理，不能一次旋转就达到平衡，需要先对node的右孩子进行右旋，然后node左旋，也就是右平衡
Java实现AVL：平衡搜索二叉树
分析完了这四个过程，我们来把这四个过程封装成方法
/**
* 以参数node为根节点进行左旋操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> leftRotate(AVLNode<T> node){
AVLNode<T> child = node.getRight();
node.setRight(child.getLeft());
child.setLeft(node);
return child;
}
/**
* 以参数node为根节点进行右旋操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> rightRotate(AVLNode<T> node){
AVLNode<T> child = node.getLeft();
node.setLeft(child.getRight());
child.setRight(node);
return child;
}
/**
* 以参数node为根节点进行左平衡操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> leftBalance(AVLNode<T> node){
node.setLeft(leftRotate(node.getLeft()));
return rightRotate(node);
}
/**
* 以参数node为根节点进行右平衡操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> rightBalance(AVLNode<T> node){
node.setRight(rightRotate(node.getRight()));
return leftRotate(node);
}
接下来我们需要定义AVL树的数据结构，AVL树比BST树的节点就多了一个高度属性，所以数据结构的定义可以参照BST树来定义。
节点数据结构的定义：
class AVLNode<T extends Comparable<T>>{
private T data;
private AVLNode<T> left;
private AVLNode<T> right;
private int height; // 记录节点当前的高度值
public AVLNode(T data, AVLNode<T> left, AVLNode<T> right, int height) {
this.data = data;
this.left = left;
this.right = right;
this.height = height;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public AVLNode<T> getLeft() {
return left;
}
public void setLeft(AVLNode<T> left) {
this.left = left;
}
public AVLNode<T> getRight() {
return right;
}
public void setRight(AVLNode<T> right) {
this.right = right;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
}
AVL树数据结构的定义：
public class AVL<T extends Comparable<T>> {
private AVLNode<T> root;
public AVL(){
this.root = null;
}
}
方便起见，封装几个工具函数
/**
* 获取node为根节点的树的高度，如果该节点为null，则返回0，如果不为null，则返回实际高度
* @param node
* @return
*/
private int height(AVLNode<T> node){
return node == null ? 0 : node.getHeight();
}
/**
* 返回以node1和node2为根节点的子树高度的最大值
* @param node1
* @param node2
* @return
*/
private int maxHeight(AVLNode<T> node1, AVLNode<T> node2){
int l = height(node1);
int r = height(node2);
return l > r ? l : r;
}
定义了数据结构以后，我们就要对上面的四个旋转过程封装的函数做一些修正，因为在刚才的过程中我们只对怎么样旋转做了描述，而没有去管高度如何变化，所以在这个过程中我们需要加上高度的部分。
/**
* 以参数node为根节点进行左旋操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> leftRotate(AVLNode<T> node){
AVLNode<T> child = node.getRight();
node.setRight(child.getLeft());
child.setLeft(node);
//这里计算高度是从下往上计算，旋转后的node在下面
node.setHeight(maxHeight(node.getLeft(), node.getRight()) + 1);
child.setHeight(maxHeight(child.getLeft(), child.getRight()) + 1);
return child;
}
/**
* 以参数node为根节点进行右旋操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> rightRotate(AVLNode<T> node){
AVLNode<T> child = node.getLeft();
node.setLeft(child.getRight());
child.setRight(node);
node.setHeight(maxHeight(node.getLeft(), node.getRight()) + 1);
child.setHeight(maxHeight(child.getLeft(), child.getRight()) + 1);
return child;
}
/**
* 以参数node为根节点进行左平衡操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> leftBalance(AVLNode<T> node){
node.setLeft(leftRotate(node.getLeft()));
return rightRotate(node);
}
/**
* 以参数node为根节点进行右平衡操作，把旋转后的树的根节点返回
* @param node
* @return
*/
private AVLNode<T> rightBalance(AVLNode<T> node){
node.setRight(rightRotate(node.getRight()));
return leftRotate(node);
}
增加删除的过程就是套用BST的过程，只不过需要注意旋转和高度的变化
/**
* 递归实现AVL树的插入操作
* @param data
*/
public void insert(T data){
this.root = insert(this.root, data);
}
/**
* 以参数root为起始节点，搜索一个合适的位置添加data，然后把子树的根节点返回
* @param root
* @param data
* @return
*/
private AVLNode<T> insert(AVLNode<T> root, T data) {
if(root == null){
return new AVLNode<>(data, null, null, 1);
}
if(root.getData().compareTo(data) > 0){
root.setLeft(insert(root.getLeft(), data));
// 判断root节点是否失衡 #1
if(height(root.getLeft()) - height(root.getRight()) > 1){
if(height(root.getLeft().getLeft())
>= height(root.getLeft().getRight())){
// 左孩子的左子树太高
root = rightRotate(root);
} else {
// 左孩子的右子树太高
root = leftBalance(root);
}
}
} else if(root.getData().compareTo(data) < 0){
root.setRight(insert(root.getRight(), data));
// 判断root节点是否失衡 #2
if(height(root.getRight()) - height(root.getLeft()) > 1){
if(height(root.getRight().getRight())
>= height(root.getRight().getLeft())){
// 右孩子的右子树太高
root = leftRotate(root);
} else {
// 右孩子的左子树太高
root = rightBalance(root);
}
}
}
// 递归回溯过程中，更新节点的高度值 #3
root.setHeight(maxHeight(root.getLeft(), root.getRight()) + 1);
return root;
}
/**
* 实现AVL树的递归删除
* @param data
*/
public void remove(T data){
this.root = remove(this.root, data);
}
private AVLNode<T> remove(AVLNode<T> root, T data) {
if(root == null){
return null;
}
if(root.getData().compareTo(data) > 0){
root.setLeft(remove(root.getLeft(), data));
// #1
if(height(root.getRight()) - height(root.getLeft()) > 1){
if(height(root.getRight().getRight())
>= height(root.getRight().getLeft())){
root = leftRotate(root);
} else {
root= rightBalance(root);
}
}
} else if(root.getData().compareTo(data) < 0){
// #2
root.setRight(remove(root.getRight(), data));
if(height(root.getLeft()) - height(root.getRight()) > 1){
if(height(root.getLeft().getLeft())
>= height(root.getLeft().getRight())){
root = rightRotate(root);
} else {
root= leftBalance(root);
}
}
} else {
if(root.getLeft() != null && root.getRight() != null){
// #3 左右子树哪个高，删除哪个，为了防止删除带来的旋转操作，提高效率
if(height(root.getLeft()) >= height(root.getRight())){
// 用前驱替换
AVLNode<T> pre = root.getLeft();
while(pre.getRight() != null){
pre = pre.getRight();
}
root.setData(pre.getData());
root.setLeft(remove(root.getLeft(), pre.getData())); //删除前驱
} else {
// 用后继替换
AVLNode<T> post = root.getRight();
while(post.getLeft() != null){
post = post.getLeft();
}
root.setData(post.getData());
root.setRight(remove(root.getRight(), post.getData())); // 删除后继
}
} else {
if(root.getLeft() != null){
return root.getLeft();
} else if(root.getRight() != null){
return root.getRight();
} else {
return null;
}
}
}
// 递归回溯过程中，更新节点的高度值 #4
root.setHeight(maxHeight(root.getLeft(), root.getRight()) + 1);
return root;
}