前文介绍了，二叉树、二叉排序树，需要了解的不妨关注下小JIA。

算法--平衡二叉树AVL原理分析以及代码实现

AVL是一种高度平衡的二叉排序树。对于任意节点左子树与右子树高度差不超过1，AVL的高度与节点数量为O（logn）关系。平衡因子等于左子树高度减去右子树高度。AVL所有节点的平衡因子只可能是-1、0、1。因此当添加元素或删除元素时有可能会破会这种平衡，所以需要维护。失去平衡主要有四种情况，分别为LL、LR、RR和RL。

AVL 的节点定义

public class AVLTreeNode<T extends Comparable<T>> {
 private T key; //关键字(键值)
 private int height; //高度
 private AVLTreeNode<T> left; //左孩子
 private AVLTreeNode<T> right; //右孩子
 public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
 this.key = key;
 this.left = left;
 this.right = right;
 this.height = 0;
 }
 ......
 }

LL

LL,平衡因子大于1，左子树平衡因子大于等于0，需要将A顺时针向下右旋转，B做为父节点

右旋转操作，首先保存B右子树K3，将A做为B的右子树，K3做为A的左孩子，并更新A，B的高度值，完成旋转。

/* LL：左旋转 */
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> node) {
 AVLTreeNode<T> tempNode;
 
 tempNode = node.getLeft();
 node.setLeft(tempNode.getRight());
 tempNode.setRight(node);
 
 node.setHeight(max(height(node.getLeft()), height(node.getRight())) + 1);
 tempNode.setHeight(max(height(tempNode.getLeft()), node.getHeight()) + 1);
 return tempNode;
}

RR

RR，平衡因子小于-1，右子树平衡因子小于等于0，需要将A逆时针向下左旋转，B做为父节点

左旋转操作，首先保存B左子树K2，将A做为B的左子树，K2做为B的右孩子，并更新A、B的高度值，完成旋转

/* RR：右旋转 */
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> node) {
 AVLTreeNode<T> tempNode;
 
 tempNode = node.getRight();
 node.setRight(tempNode.getLeft());
 tempNode.setLeft(node);
 node.setHeight(max( height(node), height(node.getRight())) + 1);
 tempNode.setHeight(max( height(tempNode.getRight()), node.getHeight()) + 1);
 return tempNode;
}

LR

LR，平衡因子大于1，左子树平衡因子小于0，首先将B进行左旋转，在将A进行右旋转

/* LR：左双旋转 */
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> node) {
 node.setLeft(rightRightRotation(node.getLeft()));
 return leftLeftRotation(node);
}

RL

RL，平衡因子大于-1，右子树平衡因子大于0，首先将B进行右旋转，在将A进行左旋转

/* RL：右双旋转 */
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> node) {
 node.setRight(leftLeftRotation(node.getRight()));
 return rightRightRotation(node);
}

插入节点

原则：根据二叉查找树BST的规定插入数据，再来判断是否失去平衡；若失去平衡再根据文上介绍的旋转规则平衡数据；最后再设置树高。

/* 将结点插入到AVL树中 */
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
 if (tree == null) {
 //新建节点
 tree = new AVLTreeNode<T>(key, null, null);
 } else {
 int cmp = key.compareTo(tree.getKey());
 if (cmp < 0) { //将key插入到tree的左子树
 tree.setLeft(insert(tree.getLeft(), key));
 
 //插入节点后，若AVL树失去平衡，则进行相应的调节。
 if (height(tree.getLeft()) - height(tree.getRight()) > 1) {
 if (key.compareTo(tree.getLeft().getKey()) < 0)
 tree = leftLeftRotation(tree);
 else
 tree = leftRightRotation(tree);
 }
 } else if (cmp > 0) {//将key插入到tree的右子树
 tree.setRight(insert(tree.getRight(), key)); 
 
 //插入节点后，若AVL树失去平衡，则进行相应的调节。
 if (height(tree.getRight()) - height(tree.getLeft()) > 1) {
 if (key.compareTo(tree.getRight().getKey()) > 0)
 tree = rightRightRotation(tree);
 else
 tree = rightLeftRotation(tree);
 }
 }
 }
 tree.setHeight(max(height(tree.getLeft()), height(tree.getRight())) + 1);
 return tree;
}

删除节点

同理，先找到删除节点的位置，再进行AVL平衡调节。找到要删除的节点Z后，如果Z的左右孩子都非空，

a)若Z的左子树高于右子树，找出左子树中的最大节点K(maxNum方法)，使用K的值替换掉Z的值，并删除K；

b)若Z的左子树矮于或等于右子树，找出右子树中最小节点K(minNum方法)，使用K的值替换掉Z的值，并删除K。

这种方式的好处是删除后AVL树仍然是平衡的。

/* 删除结点 */
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> delNode) {
 //根为空 或者 没有要删除的节点，直接返回null。
 if (tree == null || delNode == null)
 return null;
 int cmp = delNode.getKey().compareTo(tree.getKey());
 if (cmp < 0) { //待删除的节点在tree的左子树中
 tree.setLeft(remove(tree.getLeft(), delNode));
 
 // 删除节点后，若AVL树失去平衡，则进行相应的调节。
 if (height(tree.getRight()) - height(tree.getLeft()) > 1) {
 AVLTreeNode<T> r = tree.getRight();
 if (height(r.getLeft()) > height(r.getRight()))
 tree = rightLeftRotation(tree);
 else
 tree = rightRightRotation(tree);
 }
 } else if (cmp > 0) { //待删除的节点在tree的右子树中
 tree.setRight(remove(tree.getRight(), delNode));
 
 // 删除节点后，若AVL树失去平衡，则进行相应的调节。
 if (height(tree.getLeft()) - height(tree.getRight()) > 1) {
 AVLTreeNode<T> l = tree.getLeft();
 if (height(l.getRight()) > height(l.getLeft()))
 tree = leftRightRotation(tree);
 else
 tree = leftLeftRotation(tree);
 }
 } else { // tree是对应要删除的节点。
 // tree的左右孩子都非空
 if ((tree.getLeft() != null) && (tree.getRight() != null)) { 
 //如果tree的左子树比右子树高；
 if (height(tree.getLeft()) > height(tree.getRight())) { 
 AVLTreeNode<T> max = maxNum(tree.getLeft());
 tree.setKey(max.getKey());
 tree.setLeft(remove(tree.getLeft(), max));
 //如果tree的左子树矮于或等于右子树
 } else {
 AVLTreeNode<T> min = minNum(tree.getRight());
 tree.setKey(min.getKey());
 tree.setRight(remove(tree.getRight(), min));
 }
 } else {
 AVLTreeNode<T> tmpNode = tree;
 tree = (tree.getLeft() != null) ? tree.getLeft() : tree.getRight();
 tmpNode = null;
 }
 }
 return tree;
}

胜象大百科