平衡二叉樹的基本原理和實作方法（Java）

平衡二叉樹（AVL樹）的來源：

看一個案例(說明二叉排序樹可能的問題)

給你一個數列{1,2,3,4,5,6}，要求建立一顆二叉排序樹(BST), 并分析問題所在.

BST 存在的問題分析:

1）、左子樹全部為空，從形式上看，更像一個單連結清單.

2）、插入速度沒有影響

3)、查詢速度明顯降低(因為需要依次比較), 不能發揮BST的優勢，因為每次還需要比較左子樹，其查詢速度比單連結清單還慢

解決方案-平衡二叉樹(AVL)

平衡二叉樹（AVL樹）的基本介紹：

1）、平衡二叉樹也叫平衡二叉搜尋樹（Self-balancing binary search tree）又被稱為AVL樹， 可以保證查詢效率較高。（二叉排序樹演化而來）

2）具有以下特點：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用實作方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。

案例分析：

要求: 給你一個數列，建立出對應的平衡二叉樹.數列 {4,3,6,5,7,8}==>左旋轉

要求: 給你一個數列，建立出對應的平衡二叉樹.數列 {10,12, 8, 9, 7, 6}==>右旋轉

思路分析：

左旋轉：

1、 建立一個新的節點 newNode (以4這個值建立),建立一個新的節點，值等于目前 根節點的值

Node newNode = new Node(value);

2、把新節點的左子樹設定了目前節點的左子樹

newNode.left = left

3、把新節點的右子樹設定為目前節點的右子樹的左子樹

newNode.right =right.left;

4、把目前節點的值換為右子節點的值

value=right.value;

5、把目前節點的右子樹設定成右子樹的右子樹

right=right.right;

6、把目前節點的左子樹設定為新節點

left=newLeft;

（左旋轉後的二叉樹的示意圖如下：）

右旋轉：

1、 建立一個新的結點，值等于目前子節點的值

Node newNode = new Node(value);

2、 把新結點的右子樹設定為目前結點的右子樹

newNode.right = right;

3、 把新結點的左子樹設定為目前結點的左子樹的右子樹

newNode.left = left.right;

4、把目前節點的值換為左子節點的值

newNode.value = left.value;

5、 把目前節點的左子樹設定成左子樹的左子樹

left = left.left;

6、把目前節點的右子樹設定為新節點

right = newNode;

（右旋轉後二叉樹的示意圖如下：）

注意：

當int[] arr = { 10, 11, 7, 6, 8, 9 }; 運作原來的代碼可以看到，并沒有轉成 AVL樹，此時的二叉樹轉換成了如圖所示的非平衡二叉樹

解決方法：

1. 1).當符号右旋轉的條件時：

   如果它的左子樹的右子樹高度大于它的左子樹的高度

   2. 先對目前這個結點的左節點進行左旋轉

   3. 在對目前結點進行右旋轉的操作即可

2. 2).當符号左旋轉的條件時：

   1.如果它的右子樹的左子樹高度大于它的右子樹的右子樹的高度

   2.先對目前這個結點的右節點進行右旋轉

   3. 在對目前結點進行左旋轉的操作即可

詳細代碼：

package Tree.avl;

public class AVLTreeDemo {

	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 };  
		AVLTree avlTree = new AVLTree();
		for (int i = 0; i < arr.length; i++) {
			avlTree.add(new Node(arr[i]));
		}
		System.out.println("中序周遊");
		avlTree.infixOrder();
		System.out.println("平衡處理：");
		System.out.println("樹的高度：" + avlTree.getRoot().height());
		System.out.println("左子樹的高度" + avlTree.getRoot().left.height());
		System.out.println("右子樹的高度" + avlTree.getRoot().right.height());
	}

}

//建立二叉樹
class AVLTree {
	private Node root;

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	// 向二叉樹中添加元素
	public void add(Node node) {
		if (root == null) {
			root = node;
		} else {
			root.add(node);
		}
	}

	// 中序周遊二叉樹
	public void infixOrder() {
		if (root == null) {
			System.out.println("樹為空");
		} else {
			root.infixOrder();
		}
	}
}

//建立二叉樹的結點類
class Node {
	int value;
	Node left;
	Node right;

	public Node(int value) {
		this.value = 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;
		// 把目前結點的值替換為右子結點的值
		newNode.value = right.value;
		// 把目前結點的右子樹設定成右子樹的右子樹
		right = right.right;
		// 把目前結點的左子樹設定成新節點
		left = newNode;

	}

	// 右旋轉方法
	private void rightRotate() {
		// 建立一個新的結點，值等于目前子節點的值
		Node newNode = new Node(value);
		// 把新結點的右子樹設定為目前結點的右子樹
		newNode.right = right;
		// 把新結點的左子樹設定為目前結點的左子樹的右子樹
		newNode.left = left.right;
		// 把目前節點的值換為左子節點的值
		newNode.value = left.value;
		// 把目前節點的左子樹設定成左子樹的左子樹
		left = left.left;
		// 把目前節點的右子樹設定為新節點
		right = newNode;

	}

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

	public void add(Node node) {
		if (node == null) {
			return;
		}
		if (this.value > node.value) {// 要添加的node的值小于目前樹的根節點的值
			if (this.left == null) {// 判斷this的左節點是否為空
				this.left = node;// 為空就直接賦給左節點
			} else {
				// 開始從目前結點的左節點遞歸
				this.left.add(node);
			}
		} else {// 如果node大與this
			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();// 右旋轉
			}
		}
	}

	// 中序周遊二叉樹
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this);
		if (this.right != null) {
			this.right.infixOrder();
		}
	}
}