平衡二叉树AVL

概念

• 是特殊的BST二叉排序树

• 左右两个子树的高度差绝对值不超过1

当root.rightHeight() - root.leftHeight() > 1,左旋

左旋步骤

1. 创建一个新节点，值为root.value,新节点的左节点为root.left

   Node newNode = new Node(root.value);
   newNode.left = root.left
   

2. 新节点的右节点为root的右子树的左节点

   newNode.right = root.right.left
   

3. 把root的值换成右子节点

   root.value = root.right.value
   

4. root的右子节点换成右子节点的右子节点

   root.right = root.right.right
   

5. root的左子树设置成新节点

   root.left = newNode;
   

以[4,3,6,5,7,8]演示左旋，当插入8时，高度差大于1，左旋

平衡二叉树图解.png

当root.leftHeight() - root.rightHeight() > 1,右旋

左旋步骤

1. 创建一个新节点，值为root.value,新节点的右节点为root.right

   Node newNode = new Node(root.value);
   newNode.right = root.right;
   

2. 新节点的左节点为root的左子树的右节点

   newNode.left = root.left.right;
   

3. 把root的值换成左子节点

   root.value = root.left.value
   

4. root的左子节点换成左子节点的左子节点

   root.left = root.left.left
   

5. root的右子树设置成新节点

   root.right = newNode;
   

右旋同左旋，不画图了

双旋

当满足右旋时

如果（root的左子树）的右子树高度大于（root的左子树）的左子树高度，

1. 先对root的左子树进行左旋操作。
2. 针对root右旋

当满足左旋时 同上

如果（root的右子树）的左子树高度大于（root的右子树）的右子树高度，

1. 先对root的右子树进行右旋操作。

2. 对root左旋

   
   双旋.png

添加节点代码（主要是rebalance）

public class AVLTree {

  public static void main(String[] args) {
//    int[] arr = {4, 3, 6, 5, 7, 8};
//    int[] arr = {10, 12, 8,9,7,6};
    int[] arr = {10, 11, 7, 6, 8, 9};
    Tree tree = new Tree();
    for (int i = 0; i < arr.length; i++) {
      tree.add(new Node(arr[i]));
    }
    tree.infixOrder();
    System.out.println(tree.root.height());
    System.out.println(tree.root.leftHeight());
    System.out.println(tree.root.rightHeight());

  }
}


class Tree {

  Node root;

  void add(Node node) {
    if (root == null) {
      root = node;
    } else {
      root.add(node);
    }
  }

  public void infixOrder() {
    if (root != null) {
      root.infixOrder();
    }
  }
}


class Node {

  int value;
  Node left;
  Node right;
  Node parent;

  public Node(int value) {
    this.value = value;
  }

  int leftHeight() {
    if (left == null) {
      return 0;
    } else {
      return left.height();
    }
  }

  int rightHeight() {
    if (right == null) {
      return 0;
    } else {
      return right.height();
    }
  }

  public int height() {
    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
  }

  void leftRotate() {
    // 1. 创建一个新节点，值为root.value,新节点的左节点为root.left
    Node newNode = new Node(value);
    newNode.left = left;
    // 2. 新节点的右节点为root的右子树的左节点
    newNode.right = right.left; // 不用判空，最多是null
    // 3. 把root的值换成右子节点
    value = right.value;
    // 4. root的右子节点换成右子节点的右子节点
    right = right.right;
    // 5. root的左子树设置成新节点
    left = newNode;

  }

  void rightRotate() {
    Node newNode = new Node(value);
    newNode.right = right;
    newNode.left = left.right; // 不用判空，最多是null
    value = left.value;
    left = left.left;
    right = newNode;
  }

  void add(Node node) {
    if (node == null) {
      return;
    }
    if (node.value < this.value) {
      if (this.left == null) {
        this.left = node;
        this.left.parent = this;
      } else {
        this.left.add(node);
      }
    } else {
      if (this.right == null) {
        this.right = node;
        this.right.parent = this;
      } else {
        this.right.add(node);
      }
    }

    // 当添加完一个节点后，如果右子树-左子树高度 > 1 左旋
    if (rightHeight() - leftHeight() > 1) {
//      如果（当前节点的右子树）的左子树高度大于（当前节点的右子树）的右子树高度，则先对当前节点的右子树进行右旋操作。
      if(right!= null && right.leftHeight() > right.rightHeight()) {
        right.rightRotate();
      }
      leftRotate();
      return;
    }

    if (leftHeight() - rightHeight() > 1) {
  //      如果（当前节点的左子树）的右子树高度大于（当前节点的左子树）的左子树高度，则先对当前节点的左子树进行左旋操作。
      if (left != null && left.rightHeight() > left.leftHeight()) {
        left.leftRotate();
      }
      rightRotate();
    }
  }

  void infixOrder() {
    if (this.left != null) {
      this.left.infixOrder();
    }
    System.out.println(this.value);
    if (this.right != null) {
      this.right.infixOrder();
    }
  }

}