AVL树的实现（Java版）

当我们用普通二叉搜索树查询数据的时候最好情况是这是一棵平衡二叉树时间复杂度可以达到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 treeNodenew TreeNode(val); //先正常插入 if(rootnull){ roottreeNode; return true; } //正常插入的时候定义了两个新变量应该是pparent一个是cur TreeNode pnull; TreeNode curroot; while(cur!null){ if (valcur.val){ pcur; curcur.right; } else if (valcur.val) { return false; } else { pcur; curcur.left; } } //走完这里之后p走到了我们要放的地方的父亲节点cur走到了空 if (valp.val){ p.righttreeNode; }else { p.lefttreeNode; } treeNode.parentp; curtreeNode; //插入完之后要判断是否平衡如果不平衡要进行旋转 while (p!null){ //先增加bf然后再判断最后再旋转 if(curp.left){ p.bf--; }else { p.bf; } //开始判断平衡因子是否需要旋转 if(p.bf0){ break; } else if (p.bf1||p.bf-1) { curp; pcur.parent; } else { //这里是p的bf等于2或者-2是需要调整的 if(p.bf-2){ if (cur.bf-1){ //我们需要右旋 RotateR(p); }else { //我们需要先左旋再右旋 RotateLR(p); } }else { //p.bf2 if (cur.bf1) { //我们需要左旋 RotateL(p); }else { //我们需要先右旋再左旋 RotateRL(p); } } break; } } return true; } private void RotateRL(TreeNode p) { TreeNode subRp.right; TreeNode subRLsubR.left; int bf subRL.bf; RotateR(p.right); RotateL(p); //重新调整bf if (bf-1){ subR.bf0; p.bf0; subRL.bf1; }else if (bf1){ subR.bf-1; p.bf0; subRL.bf0; } } private void RotateL(TreeNode p) { TreeNode subRp.right; TreeNode subRLsubR.left; subR.leftp; p.rightsubRL; //开始指向父亲节点 if (subRL!null){ subRL.parentp; } p.parentsubR; TreeNode Ppp.parent; if(proot) { root subR; subR.parent null; }else { if(Pp.leftp){ Pp.leftsubR; }else { Pp.rightsubR; } subR.parentPp; } //修改bf p.bf0; subR.bf0; } private void RotateLR(TreeNode p) { TreeNode subLp.left; TreeNode subLRsubL.right; int bf subLR.bf; //我们传入的这个参数都是要转的那一部分的头节点 RotateL(subL); RotateR(p); //重新调整bf if (bf-1){ subLR.bf0; subL.bf0; p.bf1; }else if (bf1){ subLR.bf0; subL.bf-1; p.bf0; } } //右旋 private void RotateR(TreeNode p) { TreeNode subLp.left; TreeNode subLRsubL.right; //subLR可能是空的 //开始旋转 //先指向子结点 subL.rightp; p.leftsubLR; //再指向父结点 if(subLR!null){ subLR.parentp; } TreeNode Ppp.parent; p.parentsubL; //可能原来的p节点并不是根结点 if(proot){ rootsubL; subL.parentnull; }else { if (Pp.leftp){ Pp.leftsubL; }else { Pp.rightsubL; } subL.parentPp; } //调节平衡因子,根据我给的例子来看可以对比一下旋转完的两张图变了p.bg和subL.bf p.bf0; subL.bf0; } private int height(TreeNode root) { if(root null) return 0; int leftH height(root.left); int rightH height(root.right); return leftH rightH ? leftH1 : rightH1; } 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)); } }