- 平衡查找树（AVL树）
AVL树是一种左右子树高度之差不超过1,且左右子树内部也符合高度差不超过1的性质。
下图有节点的左右子树高度差都超过了1，所有不是AVL树。
平衡因子： 某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。如果某一结点的平衡因子绝对值大于1则说明此树不是平衡二叉树。为了方便计算每一结点的平衡因子我们可以为每个节点赋予height这一属性，表示此节点的高度。
最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。
引起不平衡的情况
在AVL树中插入删除节点可能会导致不平衡情况产生，分为以下四种。
- 对平衡树中A节点的左子树的左孩子插入一个节点（LL）
- 对平衡树中A节点的右子树的右孩子插入一个节点（RR）
- 对平衡树中A节点的左子树的右孩子插入一个节点（LR）
- 对平衡树中A节点的右子树的左孩子插入一个节点（RL）
下面用图的方式给出这四种情况怎么旋转
AVL树代码，节点的实现比较简单代码与二叉树节点代码一样只是增加了height属性，如下。
节点结构
//省略了get/set方法和构造函数 public class AVLNode>{ public int height; public AVLNode parent; public AVLNode left; public AVLNode right; public K key; }
工具类代码
//获取子树高度
private int GetHeight(AVLNode avlNode){
if (avlNode == null)
return 0;
else
return avlNode.getHeight();
}
//设置子树高度
private int SetHeight(AVLNode a,AVLNode b){
return GetHeight(a) > GetHeight(b) ? GetHeight(a) + 1 : GetHeight(b) + 1;
}
//前序遍历
void PreOrder(AVLNode avlNode){
if (avlNode == null){
return;
}
System.out.println(avlNode.getKey());
PreOrder(avlNode.getLeft());
PreOrder(avlNode.getRight());
}
AVL树的平衡就是通过一次或者多次左旋右旋进行调整。
左旋右旋
private AVLNode left_change(AVLNode avlNode) {
AVLNode lnode = avlNode.right;
avlNode.right = lnode.left;
if (avlNode.right != null){
avlNode.right.parent = avlNode;
}
lnode.parent = avlNode.parent;
if (avlNode.parent != null){
if (avlNode == avlNode.parent.left){
avlNode.parent.left = lnode;
} else {
avlNode.parent.right = lnode;
}
}else {
root = lnode;
}
lnode.left = avlNode;
avlNode.parent = lnode;
lnode.height = SetHeight(lnode.left,lnode.right);
avlNode.height = SetHeight(avlNode.left,avlNode.right);
return lnode;
}
private AVLNode right_change(AVLNode avlNode) {
AVLNode rnode = avlNode.left;
avlNode.left = rnode.right;
if (avlNode.left != null){
avlNode.left.parent = avlNode;
}
rnode.parent = avlNode.parent;
if (avlNode.parent == null){
root = rnode;
}else if (avlNode == avlNode.parent.left){
avlNode.parent.left = rnode;
} else {
avlNode.parent.right = rnode;
}
rnode.right = avlNode;
avlNode.parent = rnode;
rnode.height = SetHeight(rnode.left,rnode.right);
avlNode.height = SetHeight(avlNode.left,avlNode.right);
return rnode;
}
插入节点：每个节点中height属性中存储的值是以该节点为根节点树的高度（如下图），所以在每次插入节点后会涉及到更新一些节点的高度值，而且当某个节点的左子树和右子树高度差超过1，那么就破环了平衡需要进行左旋右旋调整，调整后有些点的height也需要更新。通过上述分析AVL树在插入节点时不仅要找插入位置同时插入后还要更新一些节点的高度信息，所以可以考虑用递归的方式查找插入位置插入后然后逐步向上层更新相关节点高度信息，具体看代码.
//插入节点
void InsertNode(K key){
root = InsertNode(key, root);
}
//实现了查找插入位置以及更新高度
private AVLNode InsertNode(K key,AVLNode avlNode){
//表示该树是空
if (avlNode == null){
avlNode = new AVLNode(key);
}else {//不为空有根节点
int cmp = key.compareTo((K) avlNode.key);
if (cmp > 0){
//递归，查找插入节点位置，插入向后执行到SetHeight()函数就可以做到更新高度信息。
//逐步向上层返回，逐步执行上层的SetHeight()函数更新高度信息
avlNode.right = InsertNode(key, avlNode.right);
avlNode.right.parent = avlNode;
//某节点的右孩子上插入节点（RR和RL）
if (GetHeight(avlNode.right) - GetHeight(avlNode.left) ==2){
if (GetHeight(avlNode.right.right) >= GetHeight(avlNode.right.left)){
//RR直接左旋
avlNode = left_change(avlNode);
}else {
//RL先右旋再左旋
right_change(avlNode.right);
avlNode = left_change(avlNode);
}
}
}else if (cmp < 0){
avlNode.left = InsertNode(key,avlNode.left);
avlNode.left.parent = avlNode;
//某节点的左孩子上插入节点（LL和LR）
if (GetHeight(avlNode.left) - GetHeight(avlNode.right) ==2){
if (GetHeight(avlNode.right.left) >= GetHeight(avlNode.right.right)){
//LL直接右旋
avlNode = right_change(avlNode);
}else {
//LR先左旋再右旋
left_change(avlNode.right);
avlNode = right_change(avlNode);
}
}
}else {
System.out.println("树中已存在该key值的节点");
}
}
//更新高度
avlNode.height = SetHeight(avlNode.left,avlNode.right);
return avlNode;
}
删除节点: 同理删除节点后部分节点的height值也会变化，所以还是采用递归的方式，找到删除位置删除后逐步执行每一层的SetHeight()函数更新高度信息。但是在删除中找到删除的节点后可以参考二叉树的中的方式——删除前驱或者后继节点。
private AVLNode Predecessor(AVLNode node){
AVLNode r = node.left;
if (node == null){
return null;
}
else if (r !=null){
while (r.right != null){
r = r.right;
}
return r;
}else {//进入这一步就是p(node)节点没有左孩子,可能是以下两种情况
AVLNode p = node.parent;
AVLNode q = node;
while (p!=null && q == p.left){
q = p;
p = p.parent;
}
return p;
}
}
private AVLNode Successor(AVLNode node){
AVLNode r = node.right;
if (node == null){
return null;
}
else if (r!=null){
while (r.left != null){
r = r.left;
}
return r;
}else {
AVLNode p = node.parent;
AVLNode q = node;
while (p!=null && q == p.right){
q = p;
p = p.parent;
}
return p;
}
}
//删除
void Remove(K key){
AVLNode cmnode = this.root;
AVLNode renode = null;
if (key == null){
return;
}
int cmp;
//查找是否存在删除位置
do {
cmp = key.compareTo((K) cmnode.key);
if (cmp > 0){
cmnode = cmnode.right;
}else if (cmp < 0){
cmnode = cmnode.left;
}else {
renode = cmnode;
}
}while (cmnode != null && renode == null);
if (renode == null){
System.out.println("该树不存在key值的节点");
return;
}
root = Remove(key,root);
}
private AVLNode Remove(K key,AVLNode avlNode){
if (avlNode == null){
return null;
}
int cmp = key.compareTo((K) avlNode.key);
if (cmp > 0){
//递归查找
avlNode.right = Remove(key,avlNode.right);
//(LL和LR)
if (GetHeight(avlNode.left) - GetHeight(avlNode.right) == 2){
if (GetHeight(avlNode.left.left) > GetHeight(avlNode.left.right)){
avlNode = right_change(avlNode);
}else {
left_change(avlNode.left);
avlNode = right_change(avlNode);
}
}
}else if (cmp < 0){
avlNode.left = Remove(key,avlNode.left);
//RR和RL
if (GetHeight(avlNode.right) - GetHeight(avlNode.left) == 2){
if (GetHeight(avlNode.right.right) > GetHeight(avlNode.right.left)){
avlNode = left_change(avlNode);
}else {
right_change(avlNode.right);
avlNode = right_change(avlNode);
}
}
}else {
//进入这一步也就是找到了删除节点
//判断删除节点左右子树如果都不为空，左子树高就删除前驱节点，右子树高就删除后继节点。
//这么做是避免破坏平衡
if (avlNode.left != null && avlNode.right != null){
if (GetHeight(avlNode.left) > GetHeight(avlNode.right)){
AVLNode prenode = Predecessor(avlNode);
avlNode.key = prenode.key;
avlNode.left = Remove((K) prenode.key,avlNode.left);
}else {
AVLNode sucnode = Successor(avlNode);
avlNode.key =sucnode.key;
avlNode.right = Remove((K) sucnode.key, avlNode.right);
}
}else {
avlNode = avlNode.left != null ? avlNode.left : avlNode.right;
}
}
avlNode.height = SetHeight(avlNode.left,avlNode.right);
return avlNode;
}
GAME OVER!!!
