Root of AVL Tree

• 这是关于AVL即二叉平衡查找树的基本操作，包括旋转和插入

• 这里的数据结构主要在原来的基础上加上节点的高度信息。

  import java.util.*;

  /**

  • @Author WaleGarrett

  • @Date 2020/9/5 10:41
    */
    public class PAT_1066 {
    public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    int n=scanner.nextInt();
    AVLNode root=null;
    while(n!=0){
    int value=scanner.nextInt();
    root=insert(root,value);
    // printTree(root);
    n--;
    }
    System.out.println(root.value);
    }
    static void printTree(AVLNode root){
    List list=new ArrayList<>();
    list.add(root);
    while(list.size()!=0){
    AVLNode temp=list.remove(0);
    System.out.print(temp.value+" ");
    if(temp.left!=null)
    list.add(temp.left);
    if(temp.right!=null)
    list.add(temp.right);
    }
    System.out.println();
    }

    /**

    • 顺时针旋转
    • @param root
    • @return
      */
      public static AVLNode rightRotate(AVLNode root){
      AVLNode temp=root.left;
      root.left=temp.right;
      temp.right=root;
      temp.updateHeight();
      root.updateHeight();
      return temp;
      }

    /**

    • 逆时针旋转
    • @param root
    • @return
      / public static AVLNode leftRotate(AVLNode root){ AVLNode temp=root.right; root.right=temp.left; temp.left=root; temp.updateHeight(); root.updateHeight(); return temp; } /*
    • 向平衡二叉排序树里插入一个节点
    • @param value
      */
      public static AVLNode insert(AVLNode root,int value){
      if(root==null){
      root=new AVLNode(null,null,value,1);
      return root;
      }
      if(value1){//当前节点不平衡
      if(root.left.getBalanceFactor()>0){//LL插入
      root=rightRotate(root);
      }else if(root.left.getBalanceFactor()<0){//LR插入 root.left=leftRotate(root.left); root=rightRotate(root); } } }else if(value>root.value){
      root.right=insert(root.right,value);
      root.updateHeight();
      if(root.getBalanceFactor()<-1){//当前节点不平衡 if(root.right.getBalanceFactor()<0){//RR插入 root=leftRotate(root); }else if(root.right.getBalanceFactor()>0){//RL插入
      root.right=rightRotate(root.right);
      root=leftRotate(root);
      }
      }
      }
      return root;
      }
      }
      class AVLNode{
      AVLNode left;
      AVLNode right;
      int value;
      private int height;//该结点的高度
      public AVLNode(){
      left=right=null;
      value=-1;
      height=0;
      }
      public AVLNode(AVLNode left,AVLNode right,int value,int height){
      this.value=value;
      this.left=left;
      this.right=right;
      this.height=height;
      }
      public int getHeight() {
      return height;
      }
      public int getBalanceFactor(){
      int leftHeight,rightHeight;
      if(left==null)
      leftHeight=0;
      else leftHeight=left.getHeight();
      if(right==null)
      rightHeight=0;
      else rightHeight=right.getHeight();
      return leftHeight-rightHeight;
      }
      void updateHeight(){
      int leftHeight,rightHeight;
      if(left==null)
      leftHeight=0;
      else leftHeight=left.getHeight();
      if(right==null)
      rightHeight=0;
      else rightHeight=right.getHeight();
      height=Math.max(leftHeight,rightHeight)+1;
      }
      }