为啥要有avl树
avl树是在二叉搜索树下的一种进阶形式,是为了防止二叉搜索树在极端情况下产生的链表化的场景,从而在二叉搜索树的基础上,加上了某些条件来阻止这种极端情况的产生,但不是保证完全平衡,而是放开了一定的条件,使得这种情况不那么难以满足.(条件:左右子树的高度差的绝对值不大于1) ,我们在发现大于1的时候可以使用左右旋转的方式来调整数的形态,从而保证了查找的时候有近似于O(logN)的性能.
缺点:
当然,有得必有失,这样也带来了一定的损耗:浪费了空间来保存新的变量,每次插入都判断是否满足条件,这样导致了插入的效率变低,这也使得这种二叉树不适合连续多次的插入和修改数据.
如果我们需要持续多次的插入数据,那么也有更进一步的数据结构 --- 红黑树
AVL树的定义
平衡因子
定义为每个节点的左子树和右子树的高度差(左减去右,右减去左都可以表示)
本文使用右减左表示高度差的定义
例如空树的高度差就是0,这就代表着平衡,
当高度差达到-1,就表示左子树高了,但是还在允许的范围之间,无需调整
当高度差达到1,就代表右子树高了,也在允许的范围之内
当左右子树的高度差超过这个范围(绝对值大于2的时候),那么我们就得需要实现左右旋转来满足这种结构的查找效率.
节点代码结构
static class TreeNode{ public int val; public int bf;//balance factor 平衡因子 public TreeNode left;//左孩子 public TreeNode right;//右孩子 public TreeNode parent;//父节点 public TreeNode(int val) { this.val = val; } }
实现插入功能
总体思路:
1.按照平衡二叉树的比较方式去寻找到应该插入在的节点
2.插入完了修改一下bf(平衡因子)的值
3.判断是否平衡
3.1 bf = 0直接跳出循环即可
3.2 bf = 1 或 bf = -1就继续向上寻找
3.3 bf = 2考虑左旋右旋修改avl树的结构
以下会包含四种失衡以及解决方案
1.LL类型
我们能很容易发现这种不平衡式因为左子树太深而导致的,此时我们要使用右旋来保证结构的正确.
具体步骤就是
1.将subL作为根节点
2.subLR作为parent的左孩子
3.parent作为subL的右孩子
此时我们发现subL和parent的平衡因子都会变成0
2.RR类型
此时我们明显发现右子树的深度要高于左子树两个节点
此时我们就需要进行左旋来调整整体结构的状态
整体步骤与之前类似
1.将subR提出来当根节点
2.subRL作为parent的右子树
3.parent作为subR的左子树
3.RL类型
这个你可以理解是在右子树深的情况下子树是左子树比较深,而前面的方式是左右子树的子树也是呈现同一趋势的.
执行方式
1.先对右子树进行一次右旋,这时候我们发现总体又一次呈现了RR型状态
左旋即可达成平衡的目标
这里如果我们插入的是节点值是55又会有不一样的平衡值
4.LR类型
执行方式也是一样的,我们对左子树进行左旋,再对整体进行右旋即可
这里我直接给出操作形式,其实这里插入的是25也会有另一种结果,在代码中有所体现,读者可自行画图推导
完整avl树插入代码
public class AVLTree { static class TreeNode{ public int val; public int bf;//balance factor 平衡因子 public TreeNode left;//左孩子 public TreeNode right;//右孩子 public TreeNode parent;//父节点 public TreeNode(int val) { this.val = val; } } public TreeNode root;//根节点 public boolean insert(int val){ TreeNode node = new TreeNode(val); if(root == null) { root = node; return true; } TreeNode cur = root; TreeNode parent = null; while(cur != null){ if(val < cur.val){ parent = cur; cur = cur.left; }else if(val == cur.val){ return false; }else{ parent = cur; cur = cur.right; } } if(parent.val>val){ parent.left = node; }else{ parent.right = node; } node.parent = parent; //调节负载因子 cur = node; //负载因子的修改 while(parent != null){ //先看cur是parent的左还是右 //平衡因子为右 - 左 if(cur == parent.right){ //右树高,因子++ parent.bf++; }else{ //左树高 parent.bf--; } //检查平衡因子变化完了是多少 if(parent.bf == 0){ break; }else if(parent.bf == 1 || parent.bf == -1){ //继续向上判断修改平衡因子 //因为等于1和-1只代表当前子树平衡 cur = parent; parent = parent.parent; }else{ //2或者-2的情况,考虑左旋右旋 if(parent.bf == 2){ if(cur.bf == 1){ rotateLeft(parent); }else{ //-1的情况 rotateRL(parent); } }else{ //-2的情况 if(cur.bf == 1){ rotateLR(parent); }else{ //-1的情况 rotateRight(parent); } } break; } } return true; } //左单旋 private void rotateLeft(TreeNode parent) { TreeNode subR = parent.right; TreeNode subRL = subR.left; parent.right = subRL; subR.left = parent; if(subRL != null){ subRL.parent = parent; } TreeNode pParent = parent.parent; parent.parent = subR; if(root == parent){ root = subR; root.parent = null; }else{ if(pParent.left == parent){ pParent.left = subR; }else{ pParent.right = subR; } subR.parent = pParent; } subR.bf = parent.bf = 0; } //右单旋 private void rotateRight(TreeNode parent){ //画图便于理解 TreeNode subL = parent.left; TreeNode subLR = subL.right; parent.left = subLR; subL.right = parent; if(subLR != null){ subLR.parent = parent; } //必须先记录 TreeNode pParent = parent.parent; parent.parent = subL; //检查当前是否为根节点 if(parent == root){ root = subL; root.parent = null; }else{ //此刻的parent也不一定是根节点,还是有左右树的 if(pParent.left == parent){ pParent.left = subL; }else{ pParent.right = subL; } subL.parent = pParent; } subL.bf = 0; parent.bf = 0; } //左右双旋 private void rotateLR(TreeNode parent){ TreeNode subL = parent.left; TreeNode subLR = subL.right; int bf = subLR.bf; rotateLeft(parent.left); rotateRight(parent); if(bf == -1){ subL.bf = 0; subLR.bf = 0; parent.bf = 1; }else if(bf == 1){ subL.bf = -1; subLR.bf = 0; parent.bf = 0; } } //右左双旋 private void rotateRL(TreeNode parent) { TreeNode subR = parent.right; TreeNode subRL = subR.left; int bf = subRL.bf; rotateRight(parent.right); rotateLeft(parent); if(bf == 1){ parent.bf = -1; subR.bf = 0; subRL.bf = 0; }else if(bf == -1){ parent.bf = 0; subR.bf = 0; subRL.bf = 1; } } //验证当前树 public void inorder(TreeNode root){ if(root == null){ return; } inorder(root.left); System.out.println(root.val+" "); inorder(root.right); } private int height(TreeNode root){ if(root == null){ return 0; } int left = height(root.left); int right = height(root.right); return Math.max(left+1,right+1); } public boolean isBalanced(TreeNode root){ if(root == null){ return true; } int left = height(root.left); int right = height(root.right); //判断平衡因子是否有问题 if (right-left != root.bf){ System.out.println("这个节点" + root.val +"平衡因子异常"); return false; } return Math.abs(left-right)<=1&& isBalanced(root.left) && isBalanced(root.right); } public static void main(String[] args) { int[] arr= new int[]{4, 2, 6, 1, 3, 5, 15, 7, 16,14}; AVLTree avl = new AVLTree(); for (int i = 0; i < arr.length; i++) { avl.insert(arr[i]); } System.out.println(avl.isBalanced(avl.root)); } }
