企业官网建设流程全解析

当我们用普通二叉搜索树查询数据的时候，最好情况是这是一棵平衡二叉树，时间复杂度可以达到O(log₂n)；最坏情况是数据全是升序或全是降序的情况，时间复杂度会达到O(n)。为了避免这种情况，我们引入了AVL树，它在二叉搜索树的基础上通过旋转操作来保持平衡，使得所有节点的左右子树高度差的绝对值不超过1。

具体思路如图

具体代码如下

//自己创建AVL树 public class AVL { static class TreeNode{ public int val; public int bf; 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 treeNode=new TreeNode(val); //先正常插入 if(root==null){ root=treeNode; return true; } //正常插入的时候定义了两个新变量，应该是p（parent），一个是cur TreeNode p=null; TreeNode cur=root; while(cur!=null){ if (val>cur.val){ p=cur; cur=cur.right; } else if (val==cur.val) { return false; } else { p=cur; cur=cur.left; } } //走完这里之后p走到了我们要放的地方的父亲节点，cur走到了空 if (val>p.val){ p.right=treeNode; }else { p.left=treeNode; } treeNode.parent=p; cur=treeNode; //插入完之后，要判断是否平衡，如果不平衡，要进行旋转 while (p!=null){ //先增加bf，然后再判断，最后再旋转 if(cur==p.left){ p.bf--; }else { p.bf++; } //开始判断平衡因子是否需要旋转 if(p.bf==0){ break; } else if (p.bf==1||p.bf==-1) { cur=p; p=cur.parent; } else { //这里是p的bf等于2或者-2，是需要调整的 if(p.bf==-2){ if (cur.bf==-1){ //我们需要右旋 RotateR(p); }else { //我们需要先左旋，再右旋 RotateLR(p); } }else { //p.bf==2 if (cur.bf==1) { //我们需要左旋 RotateL(p); }else { //我们需要先右旋，再左旋 RotateRL(p); } } break; } } return true; } private void RotateRL(TreeNode p) { TreeNode subR=p.right; TreeNode subRL=subR.left; int bf= subRL.bf; RotateR(p.right); RotateL(p); //重新调整bf if (bf==-1){ subR.bf=0; p.bf=0; subRL.bf=1; }else if (bf==1){ subR.bf=-1; p.bf=0; subRL.bf=0; } } private void RotateL(TreeNode p) { TreeNode subR=p.right; TreeNode subRL=subR.left; subR.left=p; p.right=subRL; //开始指向父亲节点 if (subRL!=null){ subRL.parent=p; } p.parent=subR; TreeNode Pp=p.parent; if(p==root) { root = subR; subR.parent = null; }else { if(Pp.left==p){ Pp.left=subR; }else { Pp.right=subR; } subR.parent=Pp; } //修改bf p.bf=0; subR.bf=0; } private void RotateLR(TreeNode p) { TreeNode subL=p.left; TreeNode subLR=subL.right; int bf= subLR.bf; //我们传入的这个参数都是要转的那一部分的头节点 RotateL(subL); RotateR(p); //重新调整bf if (bf==-1){ subLR.bf=0; subL.bf=0; p.bf=1; }else if (bf==1){ subLR.bf=0; subL.bf=-1; p.bf=0; } } //右旋 private void RotateR(TreeNode p) { TreeNode subL=p.left; TreeNode subLR=subL.right; //subLR可能是空的 //开始旋转 //先指向子结点 subL.right=p; p.left=subLR; //再指向父结点 if(subLR!=null){ subLR.parent=p; } TreeNode Pp=p.parent; p.parent=subL; //可能原来的p节点并不是根结点 if(p==root){ root=subL; subL.parent=null; }else { if (Pp.left==p){ Pp.left=subL; }else { Pp.right=subL; } subL.parent=Pp; } //调节平衡因子,根据我给的例子来看，可以对比一下旋转完的两张图，变了p.bg和subL.bf p.bf=0; subL.bf=0; } private int height(TreeNode root) { if(root == null) return 0; int leftH = height(root.left); int rightH = height(root.right); return leftH > rightH ? leftH+1 : rightH+1; } public boolean isBalanced(TreeNode root) { if(root == null) return true; int leftH = height(root.left); int rightH = height(root.right); if(rightH-leftH != root.bf) { System.out.println("这个节点："+root.val+" 平衡因子异常"); return false; } return Math.abs(leftH-rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right); } }

public class test { public static void main(String[] args) { int[] array = {4, 2, 6, 1, 3, 5, 15, 7, 16}; //int[] array = {30,20,90,60,180,40}; AVL avlTree = new AVL(); for (int i = 0; i < array.length; i++) { avlTree.insert(array[i]); } System.out.println(avlTree.isBalanced(avlTree.root)); } }