1.问题概述
我们在介绍二分搜索树的时候提到时间复杂度为O(logn),但是这并不是绝对的,有些时候树可能退化为链表,时间复杂度回到O(n)级别,所以为了性能考虑,应尽量避免这种退化,这就用到了平衡树。
2.什么是平衡二叉树
平衡二叉树的定义是,对于任意一个节点,左子树和右子树的高度差不能超过1,且平衡二叉树的高度和节点的数量之间的关系一是O(logn)的。我们前面介绍的满二叉树、完全二叉树和线段树都是平衡二叉树,如下图中的这棵二叉树看似不太像平衡二叉树,但它满足平衡二叉树的定义,根节点的左子树的高度3,有子树的高度2,高度差为1;8的左子树的高度为2,右子树的高度为1,高度差为1;5的左子树的高度为1,右子树高度为0,高度差为1;18的左子树高度为1,右子树高度为0,高度差为1;4,11,17都是叶子节点,其没有左子树和右子树,高度差为0,所以这棵树是一棵平衡二叉树。
给上图这棵平衡二叉树插入两个元素2和7,则得到下图这棵二叉树(这里的二叉树是二叉排序树),根据平衡二叉树的定义,显然得到的这棵二叉树不是平衡二叉树,因为8这个节点的左子树高度为3,右子树高度为1,高度差为2,超过了1,同理根节点12的左右子树高度差也是2,所以它不是一棵平衡二叉树。
如果要想让一棵平衡二叉树添加节点后依然一棵平衡二叉树,那么不能只在左边添加,右边也需要添加相应的节点来维持整棵树的平衡关系。
那么如何判断一棵二叉树是否是平衡二叉树呢?就是比较左右子树的高度差是否大于1,大于1就不是平衡二叉树。这里涉及到一个概念叫做平衡因子,平衡因子其实就是左右子树的高度差。通过计算平衡因子就可以判断一棵树是否是平衡二叉树。
3.什么是AVL树
AVL树是自平衡的二分搜索树,是一种经典的平衡树的种类。要注意的是AVL树首先要是一棵二分搜索树,其次还得是一棵平衡树,也就是要求AVL树的任何节点的左右子树高度差的绝对值不超过1。
既然AVL是自平衡的,那么AVL树是如何来维持这种平衡的呢?答案是通过旋转,即左旋和右旋。在加入节点后,要沿着这个节点向上维护平衡性。
3.1、右旋转(LL): 当插入的元素在不平衡节点的左侧的左侧时,进行右旋转,如图,将发生不平衡节点y的左子节点x的右子树变为以y为根的子树,再把 先前x的右子树T3连接到当前y的左子节点上,此时就变成了一棵以x为根节点的平衡二分搜索树。
代码实现
private Node rightRotate(Node y){
Node x = y.left;
Node T3 = x.right;
//向右旋转
x.right = y;
y.left = T3;
//更新height值,旋转后只有x和y的高度值发生变化
y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
3.2、左旋转(RR): 当插入的元素在不平衡节点的右侧的右侧时,进行左旋转,如图,将发生不平衡节点的右子节点x的左子树变为以y为根的子树,再把先前x的左子节点T3连接到当前y的右子节点上。此时变成了一棵以x根节点的二分搜索树。
代码实现:
private Node leftRotate(Node y){
Node x = y.right;
Node T3 = x.left;
//向左旋转
x.left = y;
y.right = T3;
//更新height值,旋转后只有x和y的高度值发生变化
y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
3.3、LR: 当插入元素在不平衡节点的左侧的右侧时,需要先对x进行一次左旋转,再对y进行一次右旋转,如下图:
代码实现:
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 // key.compareTo(node.key) == 0
node.value = value;
//更新height
node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
//计算平衡因子
int balanceFactor = getBalanceFactor(node);
//平衡维护
//LL
if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
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;
}
3.4、RL:当插入元素在不平衡节点右侧的左侧时,需要先对x进行一次右旋转,再对y进行一次左旋转,如下图:
代码实现:
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 // key.compareTo(node.key) == 0
node.value = value;
//更新height
node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
//计算平衡因子
int balanceFactor = getBalanceFactor(node);
//平衡维护
//LL
if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
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;
}
上面我们介绍了添加元素时维护平衡性的方法和代码实现,其实在删除元素时也需要维护下平衡性,方法和添加类似。下面贴出删除元素的方法实现:
private Node remove(Node node, K key){
if( node == null )
return null;
Node retNode; //要返回的node节点,
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{ // key.compareTo(node.key) == 0
// 待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
retNode = node;
}
// 待删除节点右子树为空的情况
else if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
retNode = node;
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
else {
Node successor = minimum(node.right);
successor.right = remove(node.right, successor.key);
successor.left = node.left;
node.left = node.right = null;
retNode = node;
}
}
if(retNode == null)
return null;
//更新height
retNode.height = 1 + Math.max(getHeight(retNode.left),getHeight(retNode.right));
//计算平衡因子
int balanceFactor = getBalanceFactor(retNode);
//平衡维护
//LL
if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
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;
}
4.总结:
这篇介绍了平衡树和AVL树的概述,在二分搜索树的基础上,重点实现了AVL树添加和删除元素后平衡性的维护,下篇将AVL树的实现代码贴出来。