2023年6月22日发(作者：)

AVL算法分析⼀、何为AVL平衡树？具有以下特点：1.⼆叉查找树结构（左孩⼦结点 < ⽗结点 < 右孩⼦结点）2.结点左右两边的⾼度差(平衡因⼦balance)为[-1,1]=> balance = | Deep（LeftChild） - Deep（RightChild）| <= 13.失衡：balance > 1==> balance == 2 ==> 左平衡(Deep(LeftChild)-Deep(RightChild) == 2)balance < -1==> balance == -2 ==> 右平衡(Deep(LeftChild)-Deep(RightChild) == -2)⼆、AVL平衡树----插⼊结点左平衡右平衡public class AviTree1> implements ITreeFactory {private TreeNode mRoot;private final int EQ = 0;private final int EL = 1;private final int ER = -1;@Overridepublic TreeNode generaTree(T[] arrays) { arrays = (arrays,); for (T t : arrays){ insertTree(mRoot,t); printTreeNode(mRoot); n(""); } return mRoot;}private void insertTree(TreeNode parent,T data){ TreeNode node = createTreeNode(data); if(mRoot == null){ mRoot = node; }else { int com = eTo(data); if(com == 0) return; if(com > 0){ if( != null){ if( != null){ insertTree(,data); }else { = node; = parent; adjustTreeStruct(node); } }else { if( != null){ insertTree(,data); }else { = node; = parent; adjustTreeStruct(node); } } }}private void printTreeNode(TreeNode root){ if(root == null) return; ( +" , " ); printTreeNode(); printTreeNode();}private TreeNode getBalanceRootNode(TreeNode node){ TreeNode parent = ; while (parent != null){ if(eTo() > 0){ ++; }else { --; } if(()>=2){ break; } parent = ; } return parent;}private void adjustTreeStruct(TreeNode node){ TreeNode parent = getBalanceRootNode(node); if(parent == null) return; switch (){ case 2: leftAdjust(parent); break; case -2: rightAdjust(parent); break; }}private void leftAdjust( TreeNode parent){ TreeNode left = ; TreeNode right = ; // ⼀个⼦节点 parent left lLeft 结点 -> parent右旋 = = 0 // ⼀个⼦节点 parent left lRight 结点 -> 先right左旋后parent右旋 = = 0 // 两个⼦节点 left 两个⼦节点（注意以parent为根，且parent有两个结点时，left必须只有2个结点，否则parent就会下移为left） //3.1 > 0 -> parent右旋 = = 0; //3.2 < 0 > 0 -> 先left左旋 后parent右旋 = = 0 =-1 //3.3 < 0 < 0 -> 先left左旋 后parent右旋 = = 0 =1 if(right == null || >0){ if( < 0){ leftRotate(left); } rightRotate(parent); = EQ; = EQ; }else { TreeNode leftChild = ; if( > 0){ = ER; = EQ; = EQ; }else { = EQ; = EL; = EQ; } leftRotate(left); rightRotate(parent); }}private void rightAdjust( TreeNode parent){ TreeNode right = ; TreeNode left = ; if(left == null || <0){ if( > 0){ rightRotate(right); } leftRotate(parent); = EQ; = EQ; }else { TreeNode rightChild = ; if( < 0){ = EL; = EQ; = EQ; }else { = EQ; = ER; = EQ; } rightRotate(right); leftRotate(parent); }}private TreeNode createTreeNode(T data){ TreeNode node = new TreeNode<>(); TreeNode node = new TreeNode<>(); = data; =0; return node;}private void leftRotate(TreeNode root){ TreeNode parent = ; TreeNode right = ; TreeNode rLeft = ; = parent; if(parent != null){ if(eTo()>0){ = right; }else { = right; } }else { mRoot = right; } = rLeft; if(rLeft != null){ = parent; } = right; = root;}private void rightRotate(TreeNode root){ TreeNode parent = ; TreeNode left = ; TreeNode lRight = ; = parent; if(parent != null){ if(eTo()>0){ = left; }else { = left; } }else { mRoot = left; } = lRight; if(lRight != null){ = root; } = left; = root;}}java_base/src/main/java/com/zy/java_base/arithmetic/tree/avl/