平衡二叉树，又称avl树，用于解决二叉排序树高度不确定的情况，如果二叉排序树的子树间的高度相差太大，就会让二叉排序树操作的时间复杂度升级为o(n)，为了避免这一情况，为最坏的情况做准备，就出现了平衡二叉树，使树的高度尽可能的小，其本质还是一棵二叉搜索树。
平衡二叉树的性质：
- 左子树和右子树的高度之差的绝对值小于等于1
- 左子树和右子树也是平衡二叉树
为了方便起见，给树上的每个结点附加一个数字，给出该结点左子树与右子树的高度差，这个数字称为结点的平衡因子（bf）
平衡因子=结点左子树的高度-结点右子树的高度。
因此平衡二叉树所有结点的平衡因子只能是-1、0、1，如下图，是一个平衡二叉树
平衡二叉树的高度为logn
当我们在一个平衡二叉树上插入一个结点时，有可能会导致失衡，即出现平衡因子绝对值大于1 的结点，如下图，当插入结点后，其中key为53的结点失去了平衡，我们称该结点为失衡结点，我们必须重新调整树的结构，使之恢复平衡。
不一定只有一个结点失去平衡，有可能插入一个结点会让多个结点失衡。这时候找
最小的失衡子树的根节点作为失衡结点。
那如何去恢复平衡，使得二叉搜索树依然成立为一棵平衡树？先来看平衡调整的四种类型：
举个例子：如第一个，当平衡二叉树为ab时，插入一个c结点，使得失衡了，失衡结点为a，此时因为c结点插入的位置为失衡结点的左孩子的左孩子，所以是ll型，以此类推。
为了恢复平衡，针对每一种都不一样，但目的都是调整为平衡的，且不能违背二叉搜索树的性质：如下图是每种失衡类型的解决方法，每个都不太一样，目的都是一样的，把key的值为中等的变为树的根，最小的放在左孩子，做大的放右孩子，通过这一目的，降低树的高度，也不用死记硬背。
如书上所说，这一操作被称为树的旋转，如ll型被称为右旋，rr型称为左旋，lr型是先左旋，再右旋，rl型先右旋再左旋。
3.1ll型调整
如下，在实际情况中，调整的内容可能看起来更复杂，如下方块的表示省略了n个结点，调整的方式如下(右旋)：
步骤为：
- b结点带左子树(α和新添加的c结点)一起上升
- a结点成为b的右子树
- 原来的b的右子树成为a的左子树，因为a的左子树是b，上升了，所以空着的
可以看成是a右旋为b的右子树
3.2rr型
ll型和rr型是最简单的几种情况，所以放在了前面。rr型即插入的结点位置在失衡结点的右子树的右子树中，如下图：
调整的步骤和ll的差不多
步骤为：
- b结点和它的右子树(β和新添加的c结点)一起上升
- a结点变为b结点的左子树
- 原来b的左子树α变为a的右子树
可以看成是a左旋至b的左子树
3.3lr型调整
lr型的跳转如下(左旋再右旋)：
- 首先让b和它的子树(除了c)左旋至c的左子树，把c为根的树接入a的左子树
- 然后让a右旋，成为c的右子树
其过程就是把中位数的c上升，成为ab的双亲
3.4rl型调整
rl型如下(先右旋再左旋)：
- 首先让b和它的子树(除了c)右旋至c的右子树，把c为根的树接入a的右子树
- 然后让a左旋，成为c的左子树
和lr差不多
例题：输入关键字序列(16，3，7，11 ，9，26，18，14，15)给出avl树
参考答案：
public class avltree {
private avlnode root;
public class avlnode {
public int data;
public int height;
public avlnode parent;
public avlnode left;
public avlnode right;
public avlnode(int data) {
this.data = data;
this.height = 1;
}
@override
public string tostring() {
return "avlnode{"
"data=" data
'}';
}
public void inorder() {//中序遍历
if (this.left != null) {
this.left.inorder();
}
system.out.println(this);
if (this.right != null) {
this.right.inorder();
}
}
}
private int calcheight(avlnode root) {
if (root.left == null && root.right == null) {
return 1;
} else if (root.right == null) {
return root.left.height 1;
} else if (root.left == null) {
return root.right.height 1;
} else {
return root.left.height > root.right.height ? root.left.height 1 : root.right.height 1;
}
}
private int calcbf(avlnode root) {
if (root == null) {
return 0;
} else if (root.left == null && root.right == null) {
return 0;
} else if (root.right == null) {
return root.left.height;
} else if (root.left == null) {
return -root.right.height;
} else {
return root.left.height - root.right.height;
}
}
public avlnode leftrotate(avlnode root) {
avlnode oldroot = root;
avlnode newroot = root.right;
avlnode parent = root.parent;
//1.newroot 替换 oldroot 位置
if (null != parent) {
if (oldroot.parent.data > oldroot.data) {
parent.left = newroot;
} else {
parent.right = newroot;
}
}
newroot.parent = parent;
//2.重新组装 oldroot (将 newroot 的左子树 给 oldroot 的右子树)
oldroot.right = newroot.left;
if (newroot.left != null) {
newroot.left.parent = oldroot;
}
//3. oldroot 为 newroot 的左子树
newroot.left = oldroot;
oldroot.parent = newroot;
//刷新高度
oldroot.height = calcheight(oldroot);
newroot.height = calcheight(newroot);
return newroot;
}
public avlnode rightrotate(avlnode root) {
avlnode oldroot = root;
avlnode newroot = root.left;
avlnode parent = root.parent;
//1.newroot 替换 oldroot 位置
if (null != parent) {
if (oldroot.parent.data > oldroot.data) {
parent.left = newroot;
} else {
parent.right = newroot;
}
}
newroot.parent = parent;
//2.重新组装 oldroot (将 newroot 的右子树 给 oldroot 的左子树)
oldroot.left = newroot.right;
if (newroot.right != null) {
newroot.right.parent = oldroot;
}
//3. oldroot 为 newroot 的左子树
newroot.right = oldroot;
oldroot.parent = newroot;
//刷新高度
oldroot.height = calcheight(oldroot);
newroot.height = calcheight(newroot);
return newroot;
}
public void insert(int data) {
if (null == this.root) {
this.root = new avlnode(data);
return;
}
this.root = insert(this.root, data);
}
public avlnode insert(avlnode root, int data) {
//插入左子树
if (data < root.data) {
if (null == root.left) {
root.left = new avlnode(data);
root.left.parent = root;
} else {
insert(root.left, data);
}
}
//插入右子树
else if (data > root.data) {
if (null == root.right) {
root.right = new avlnode(data);
root.right.parent = root;
} else {
insert(root.right, data);
}
}
//刷新高度
root.height = calcheight(root);
//旋转
//1. ll 型 右旋转
if (calcbf(root) == 2) {
//2. lr 型 先左旋转
if (calcbf(root.left) == -1) {
root.left = leftrotate(root.left);
}
root = rightrotate(root);
}
//3. rr型 左旋转
if (calcbf(root) == -2) {
//4. rl 型 先右旋转
if (calcbf(root.right) == 1) {
root.right = rightrotate(root.right);
}
root = leftrotate(root);
}
return root;
}
public void inorder() {
root.inorder();
}
}
测试：
avltree tree = new avltree();
tree.insert(16);
tree.insert(3);
tree.insert(7);
tree.insert(11);
tree.insert(9);
tree.insert(26);
tree.insert(18);
tree.insert(14);
tree.insert(15);
tree.inorder();结果如下：
avlnode{data=3}
avlnode{data=7}
avlnode{data=9}
avlnode{data=11}
avlnode{data=14}
avlnode{data=15}
avlnode{data=16}
avlnode{data=18}
avlnode{data=26}就是上面例题中的平衡二叉树。