数据结构学习，AVL树（java语言）
数据结构学习，AVL树（java语言）
1.AVL树基础
AVL树是一种自平衡的二叉树，AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
2.AVL树的实现
2.1底层
本次学习的AVL树底层是一个二分搜索树（BST），要实现AVL树，要在每个节点中添加每个节点的高度值height
private class Node {
public K key;
public V value;
public Node left, right;
public int height;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
height = 1;
}
}
2.2平衡因子的引入
有了每个node高度值之后，我们就可以很轻易的计算出每个节点的平衡因子（balanceFactor），我们只需要将节点的左子树的高度减去右子树的高度即可得出每个节点的平衡因子，因此我们封装一个私有方法用来获取平衡因子
private int getBalanceFactor(Node node){
if(node == null){
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
2.3平衡需要维护的时机
当我们进行node增加或者node删除时需要从插入的节点回溯计算各个父节点的平衡因子，当遇到第一个平衡因子的绝对值大于1的节点时，需要在这个节点进行操作以维护平衡
插入：
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if (key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else {
node.value = value;
}
//更新height
node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
//计算平衡因子
int balanceFactor = getBalanceFactor(node);
if(Math.abs(balanceFactor)>1){
System.out.println("unbalance: "+balanceFactor);//此时进行平衡维护
}
return node;
}
删除：
Node remove(Node node, E e){
if( node == null )
return null;
//在以下的操作中都直接将处理过的节点return这样是不合理的，因此我们引入一个retNode来储存删除过后的节点
Node retNode = new Node();
if( e.compareTo(node.e) < 0 ){
node.left = remove(node.left , e);
retNode = node;
}
else if(e.compareTo(node.e) > 0 ){
node.right = remove(node.right, e);
retNode = node;
}
else{ // e.compareTo(node.e) == 0
// 待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
retNode = rightNode;
}
// 待删除节点右子树为空的情况
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
retNode = leftNode;
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = new Node(minimum(node.right).e);
size ++;
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
size --;
retNode = successor;
}
return retNode;
}
2.3.1右旋转（LL情况）
当我们在一个平衡的树中插入一个节点时，如果新插入的节点在左子树的左侧，并破坏了平衡
如图，我们插入了z节点之后，可以计算出平衡因子
此时从z开始回溯发现y节点的平衡被打破，且此时新添加的节点是在y节点的左子树的左边（LL），此时我们只需要将y节点向右旋转
然后将x节点即y节点的左侧节点返回就完成了平衡的调整
一般情况：
//对接点y进行向右旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// x T4 向右旋转(y) z y
// / \ -------------> / \ / \
// z T3 T1 T2 T3 T4
// / \
//T1 T2
private Node rightRotate(Node y){
Node x = y.left;
Node T3 = x.right;
//旋转
x.right=y;
y.left = T3;
//更新Height
y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
return x;
}
2.3.2左旋转（RR情况）
RR情况与LL情况对称，需要的操作也基本相似
private Node leftRotate(Node y){
Node x = y.right;
Node T2 = x.left;
//向左旋转
x.left = y;
y.right = T2;
y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
return x;
}
2.3.3LR和RL
当插入的节点在左子树的右侧时（LR），我们需要先将左孩子进行一下左旋转操作，然后再对需要维护平衡的节点进行右旋转，同样，当插入的节点在右子树的左侧时（RL），我们需要先将右孩子进行右旋转操作，然后再对需要维护平衡的节点进行左旋转
LR：
RL：
2.4插入时的平衡维护
通过LL、RR、LR、RL四种情况，我们以将所有可能需要维护的情况的解决方案都写出来了，利用之前写的左右旋转的方法，可以轻易实现平衡的维护
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if (key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else {
node.value = value;
}
//更新height
node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
//计算平衡因子
int balanceFactor = getBalanceFactor(node);
// if(Math.abs(balanceFactor)>1){
// System.out.println("unbalance: "+balanceFactor);
// }
//平衡维护
//LL
if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
return rightRotate(node);
}
//RR
if(balanceFactor < -1 && getBalanceFactor(node.right) <=0){
return leftRotate(node);
}
//LR
if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
node.left = leftRotate(node.left);
return rightRotate(node);
}
//RL
if(balanceFactor < -1 && getBalanceFactor(node.right) > 0 ){
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
2.5删除时的平衡维护
删除一个node时可能会出现平衡维护的情况与加入node时的情况完全相同，都是LL、RR、LR、RL四种，所以我们在返回node之前对这四种状况进行一下判断即可。不过此时会有一点小bug，由于之前在二分搜索树中的时候，我们removeMin方法在使用时并没有进行平衡维护，所以我们有两种解决方法
- 在removeMin中加入维护平衡的方法
- 用remove方法代替removeMin（由于successor节点即是右子树中最小节点，可直接remove(node.right,successor.key)）
在以下代码中采用的是第二种方法
Node remove(Node node, K key) {
if (node == null)
return null;
Node retNode;
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
retNode = node;
} else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
retNode = node;
} else { // e.compareTo(node.e) == 0
// 待删除节点左子树为空的情况
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
retNode = rightNode;
}
// 待删除节点右子树为空的情况
else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
retNode = leftNode;
}
else {
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = new Node(minimum(node.right).key, minimum(node.right).value);
size++;
successor.right = remove(node.right, successor.key);
successor.left = node.left;
node.left = node.right = null;
size--;
retNode = successor;
}
}
retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right)+1);
int balanceFactor = getBalanceFactor(retNode);
//平衡维护
//LL
if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
return rightRotate(retNode);
}
//RR
if(balanceFactor < -1 && getBalanceFactor(retNode.right) <=0){
return leftRotate(retNode);
}
//LR
if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
//RL
if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0 ){
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
3.总结
- AVL树作为最早出现的自平衡二叉树，其中的旋转操作十分经典，值得学习；
- 此时的AVL树还有一些瑕疵，即新增\删除一个节点之后在某个节点进行平衡维护之后，他的父节点就不用再进行维护，可是此时还进行了判断，可以通过改善平衡需要维护的时机对AVL树进行优化；
- 此时，对所有的新增、删除、查询操作AVL树的时间复杂度都是O（logn）级别。