AVL树定义
AVL树任意节点的两棵子树的高度差绝对值最大为1（和红黑树相比简洁了很多）
与红黑树对比
相同点
- 都是平衡二叉树
不同点
- 平衡的定义不同，AVL树的平衡的因子是左右子树的高度差，红黑树的平衡因子是到叶子节点的黑色节点的个数
- 效率不同，AVL树查找效率高于红黑树，插入和删除效率低于红黑树
AVL树的节点信息
private int value;//节点Key值
private Node left;//左子树
private Node right;//右子树
private Node parent;//父节点
private int leftHeight;//左子树的高度
private int rightHeight;//右子树高度
旋转操作
左旋和右旋(旋转和红黑树一样，这一节可以略过)，旋转操作是很多树和堆的基础操作，很重要。
image.png
左旋转 得到右边的图，右旋转得到左边的图，左旋和右旋是相反的两个操作，旋转不会改变二叉查找树的性质。
/**
* 左旋转代码实现
*
* @param node
*/
public void leftRoate(Node node){
if(node == null){
return;
}
Node pNode =node.getParent();
if(pNode == null){
return;
}
Node lChild =node.getLeft();
node.setParent(pNode.getParent());
if(pNode.getParent()!=null) {
if (pNode.getParent().getLeft() == pNode) {
pNode.getParent().setLeft(node);
}else {
pNode.getParent().setRight(node);
}
}
pNode.setParent(node);
node.setLeft(pNode);
pNode.setRight(lChild);
if(lChild!=null)
lChild.setParent(pNode);
}
/**
* 右旋转代码实现
*
* @param node
*/
public void rightRoate(Node node){
if(node ==null){
return;
}
Node pNode =node.getParent();
if(pNode ==null){
return;
}
Node rChild =node.getRight();
node.setParent(pNode.getParent());
if(pNode.getParent()!=null) {
if (pNode.getParent().getLeft() == pNode) {
pNode.getParent().setLeft(node);
}else {
pNode.getParent().setRight(node);
}
}
pNode.setParent(node);
node.setRight(pNode);
pNode.setLeft(rChild);
if(rChild!=null)
rChild.setParent(pNode);
}
AVL树的平衡
根据AVL树的定义可知，只有左右子树高度差大于1，才会引起不平衡。插入和删除有可能会导致树的高度发生变化，从而破坏平衡状态。当节点的左右子树高度差不满足AVL树的定义，就要进行平衡操作。下面这张图描述的是四种需要调整的不平衡状态，这四种不平衡状态最终都要调整为平衡状态
image.png
<center>三角形表示是树，树有可能是空也有可能包含多个节点，圆圈表示单个节点</center>
如上图所示
- 左上角图：A的左子树的高度比A的右子树高度大2，同时B的左子树高度比右子树大1，称之为LL型。解决方案：以节点B为轴心右旋
- 右上角图：右上角图和左上角图是对称的，C节点的右子树高度比左子树大2，同时B节点的右子树比左子树大1，称之为RR型。解决方案：以B为轴心左旋
- 左下角图：C的右子树的高度比左子树大2，，A的左子树的高度比右子树大1，称之为RL型。解决方案：以B为轴心右旋转得到RR型，然后按RR型进行处理
- 右下角图：A的左子树比比右子树大2，C的右子树高度比左子树大2，称之为LR型。解决方案：以B为轴心左旋转得到LL型，然后按LL型进行后续处理
上述的LL,RR，RL，LR这四种就是插入和删除节点后可能遇到的所有不平衡的情况。如果上面那张图内感觉容比较多的话，可以简化成下面这张图（也就是abcd这四棵树为空），这样看起来会比较清晰，如下图
image.png
代码实现
主要针对LL型、LR型、RR型、RL型的不平衡状况通过旋转进行平衡操作，
//节点更新树高度，left.getMaxHeight（）获取的是当前节点左右子树的最大高度
public void updateHeight(){
if(left!=null){
leftHeight = left.getMaxHeight()+1;
}else {
leftHeight =0;
}
if(right!=null){
rightHeight =right.getMaxHeight()+1;
}else {
rightHeight =0;
}
}
//进行平衡调整
//节点旋转后，有的子节点会变成父节点，父节点会变成子节点，一定要搞清楚，旋转后谁是父节点，谁是子节点。还有旋转后，
//注意节点左右孩子高度发生变化，要及时更新
@Override
public void blanceTree(Node node) {
if(node ==null){
return;
}
node.updateHeight();
Node leftChild = node.getLeft();
Node rightChild = node.getRight();
if(node.getLeftHeight() -node.getRightHeight()>1){//左子树高于右子树
if(leftChild.getLeftHeight()>leftChild.getRightHeight()){//LL类型
rightRoate(leftChild);
node.updateHeight();
leftChild.updateHeight();
blanceTree(leftChild);
}else {//LR类型
leftRoate(leftChild.getRight());
leftChild.updateHeight();
rightRoate(leftChild.getParent());
node.updateHeight();
leftChild.getParent().updateHeight();
blanceTree(leftChild.getParent());
}
}else if (node.getLeftHeight() -node.getRightHeight()<-1){//右子树高于左子树
if(rightChild.getRightHeight()>rightChild.getLeftHeight()) {//RR型
leftRoate(rightChild);
node.updateHeight();
rightChild.updateHeight();
blanceTree(rightChild);
}else {//RL型
rightRoate(rightChild.getLeft());
rightChild.updateHeight();
rightChild.getParent().updateHeight();
leftRoate(rightChild.getParent());
node.updateHeight();
rightChild.getParent().updateHeight();
blanceTree(rightChild.getParent());
}
}else {
blanceTree(node.getParent());
}
}
平衡操作是本篇文章核心内容，也是AVL树删除和插入节点的灵魂步骤，这一节是重点。
节点插入
AVL树也是二叉树，其插入和二叉树的插入一样,插入之后为了保持AVL树特性，要做好节点高度更新以及平衡处理
public void insert(int key) {
Node node = createNode(key);
if (tree == null) {//如果树为空
tree = node;
return;
}
Node insertNode = insertNode(node, getRoot());
if(insertNode ==null){
return;
}
System.out.println("插入节点："+insertNode.getValue());
try{
updateTreeheight(insertNode);
blanceTree(insertNode);
}catch (Exception e){
e.printStackTrace();
}
}
//将节点插入树中
public Node insertNode(Node node,Node root){
if(root.getValue()>node.getValue()){//插入左子树
if(root.getLeft()!=null){
return insertNode(node,root.getLeft());
}else {
root.setLeft(node);
node.setParent(root);
return node;
}
}else if (root.getValue() <node.getValue()){//插入右子树
if(root.getRight() !=null){
return insertNode(node,root.getRight());
}else {
root.setRight(node);
node.setParent(root);
return node;
}
}else{//这个节点废弃掉
return null;
}
}
总结
AVL树和红黑树都是平衡二叉树，难易程度上，个人感觉，AVL树相对简单些；在效率上，各有侧重，AVL树主要败在维护高度平衡上；在使用范围上，红黑树使用更广泛。在它们进行抉择时，在大多数情况下红黑树是优秀的。
网友评论