AVL樹（Java語言）

平衡二叉樹

平衡二叉樹也叫平衡二叉查找樹，又被稱為AVL樹，可以保證查詢效率較高，它的特點是：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹，
結點的平衡因子定義為：結點的左子樹高度與右子樹高度之差，顯然，對一棵AVL樹而言，其所有結點的平衡因子只能是-1，0，1.擋在一棵AVL樹上插入一個結點時，有可能導致失衡，即出現絕對值大于1的平衡因子，

單旋轉（左旋轉）

插入70后失去平衡，調整程序如下：，

思路：
1、創建一個新的結點，值等于當前根節點的值，
2、把新節點的左子樹設定為當前結點的左子樹，
3、把新節點的右子樹設定為當前節點的右子樹的左子樹，
4、把當前結點的值換為右子節點的值
5、把當前節點的右子樹設定為當前節點右子樹的右子樹，
6、把當前結點的左子樹（左子節點）設定為新節點

單旋轉（右旋轉）

插入15后失去平衡，調整程序如下：

思路：
1、創建一個新的結點，值等于當前根節點的值，
2、把新節點的右子樹設定為當前結點的右子樹，
3、把新節點的左子樹設定為當前節點的左子樹的右子樹，
4、把當前結點的值換為左子節點的值
5、把當前節點的左子樹設定為當前節點左子樹的左子樹，
6、把當前結點的右子樹（右子節點）設定為新節點

雙旋轉

情況一：當符合左旋轉條件時

1、如果它的右子樹的左子樹高度大于它的右子樹的右子樹的高度
2、先對當前結點的右節點（右子樹）進行右旋轉
3、再對當前結點進行左旋轉的操作即可
情況二：當符合右旋轉條件時

1、如果它的左子樹的右子樹高度大于它的左子樹的左子樹的高度
2、先對當前結點的左節點（左子樹）進行左旋轉
3、再對當前結點進行右旋轉的操作即可，

代碼實作：

Node類：

package com.Tree.AVL;

public class Node {
    int value;
    Node left;
    Node right;

    public Node() {
    }

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

    public int getValue() {
        return value;
    }
    //回傳左子樹的高度
    public int leftHeight() {
        if(left == null) {
            return 0;
        } else {
            return left.height();
        }
    }
    //回傳右子樹的高度
    public 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;
    }
    //左旋轉的方法
    private void leftRotate() {
        //創建一個新節點,值為當前根節點的值
        Node newNode = new Node(value);
        //把新節點的左子樹設定為當前節點的左子樹
        newNode.left = left;
        //把新節點的右子樹設定為當前節點右子樹的左子樹
        newNode.right = right.left;
        //把當前節點的值替換為右子節點的值
        value = right.value;
        //把當前節點的右子樹設定成為當前節點右子樹的右子樹
        right = right.right;
        //把當前節點的左子樹(左子節點)設定為新的節點
        left = newNode;

    }
    //右旋轉的方法
    private void rightRotate() {
        //創建一個新節點，值為當前根節點的值
        Node newNode = new Node(value);
        //把新節點的右子樹設定為當前節點的右子樹
        newNode.right = right;
        //把新節點的左子樹設定為當前節點左子樹的右子樹
        newNode.left = left.right;
        //把當前節點的值替換為左子節點的值
        value = left.value;
        //把當前節點的左子樹設定成為當前節點左子樹的左子樹
        left = left.left;
        //把當前節點的右子樹(右子節點)設定為新的節點
        right = newNode;
    }
    //中序遍歷
    public void infixOrder() {
        if(this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.infixOrder();
        }
    }
    //添加節點
    public void add(Node node) {
        if(node ==null) {
            return;
        }
        if(node.value < this.value) {
            //如果當前結點的左子節點為null，則將node添加到當前結點的左子節點上
            if(this.left == null) {
                this.left = node;
            } else { //遞回向左子樹添加
                this.left.add(node);
            }
        } else { //傳入結點的值大于等于當前子樹的根節點的值
            if(this.right == null) {
                this.right = node;
            } else { //遞回向右子樹添加
                this.right.add(node);
            }
        }
        //當添加完一個節點后，如果右子樹的高度-左子樹的高度大于1，左旋轉
        if(rightHeight() - leftHeight() > 1) {
            //如果他的右子樹的左子樹的高度大于它的右子樹的右子樹的高度
            if(right != null && right.leftHeight() > right.rightHeight()) {
                //先對當前節點的右節點(右子樹)進行右旋轉
                right.rightRotate();
                //然后再對當前節點進行左旋轉
                leftRotate();
            } else {
                //直接進行左旋轉即可
                leftRotate();
            }
            return;
        }
        //當添加完一個節點后，如果左子樹的高度-右子樹的高度大于1，右旋轉
        if(leftHeight() - rightHeight() > 1) {
            //如果它的左子樹的右子樹高度大于它的左子樹的左子樹的高度
            if(left != null && left.rightHeight() > left.leftHeight()) {
                //先對當前節點的左節點(左子樹)進行左旋轉
                left.leftRotate();
                //再對當前節點進行右旋轉
                rightRotate();
            } else {
                //直接進行右旋轉即可
                rightRotate();
            }
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

AVLTree類：

package com.Tree.AVL;


public class AVLTree {
    Node root;

    //添加節點
    public void add(Node node) {
        if(root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    //中序遍歷
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("null");
        }
    }
}

測驗類：

package com.Tree.AVL;

public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {2,1,6,5,7,3};
        AVLTree avl = new AVLTree();
        for (int i = 0; i < arr.length; i++) {
            avl.add(new Node(arr[i]));
        }
        avl.infixOrder();
        System.out.println(avl.root.height());
        System.out.println(avl.root.leftHeight());
        System.out.println(avl.root.rightHeight());
    }
}

二叉排序樹的運行結果：

AVL樹的運行結果：

從以上兩個運行結果可以看出：樹的高度、樹的左、右子樹高度經過處理后，原來的二叉排序樹變為了一棵AVL樹，