数据结构之AVL树
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;//右子树高度 复制代码
旋转操作
左旋和右旋(旋转和红黑树一样，这一节可以略过)，旋转操作是很多树和堆的基础操作，很重要。
左旋转 得到右边的图，右旋转得到左边的图，左旋和右旋是相反的两个操作，旋转不会改变二叉查找树的性质。
/** * 左旋转代码实现 * * @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树的定义，就要进行平衡操作。下面这张图描述的是四种需要调整的不平衡状态，这四种不平衡状态最终都要调整为平衡状态
三角形表示是树，树有可能是空也有可能包含多个节点，圆圈表示单个节点
如上图所示
左上角图：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这四棵树为空），这样看起来会比较清晰，如下图
代码实现
主要针对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树主要败在维护高度平衡上；在使用范围上，红黑树使用更广泛。在它们进行抉择时，在大多数情况下红黑树是优秀的。
作者：QiShare
链接：https://juejin.cn/post/7026600438279602183