資料結構-----平衡二叉樹

平衡二叉樹

有些情況下我們的二叉排序樹更像單連結清單，什麼情況呢？

如果有一個數列為1,2,3,4,5,6，那麼他的二叉排序樹是不是就不怎麼好看了

雖然不怎麼影響添加删除的速度，但是可能會影響我們的查詢速度的

存在的問題

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

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

基本介紹

平衡二叉樹也叫平衡二叉搜尋樹(Self- balancing binary search tree)又被稱為AVL樹，可以保證查詢效率較高。

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

舉例：說說下面那個是平衡二叉樹

第一個第二個都是平衡二叉樹，第三個不是平衡二叉樹

注意：二叉排序樹的前提是滿足二叉排序樹

建立平衡二叉樹

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

本例采用視訊教學的左旋轉

思路：

簡單代碼

package 平衡二叉樹;

public class avl {
	public static void main(String[] args) {
		int[] arr = {4,3,6,5,7,8};
		AVLTree avlTree = new AVLTree();
		//添加節點
		for(int i = 0;i<arr.length;i++){
			avlTree.addNode(new Node(arr[i]));
		}
		//周遊
		System.out.println("中序周遊");
		avlTree.infixOrder();
		System.out.println("在做平衡旋轉後");
		System.out.println(avlTree.getRoot().height());//4
		System.out.println("左子樹的高度"+avlTree.getRoot().leftHeight());//1
		System.out.println("右子樹的高度"+avlTree.getRoot().rightHeight());//3
		//是以需要右子樹左旋轉
		
	}
	
}

//建立avl樹
class AVLTree{
	private Node root;
	
	public Node getRoot() {
		return root;
	}
	public void setRoot(Node root) {
		this.root = root;
	}
	//添加節點的方法
	public void addNode(Node node){
		if(root == null){
			root = node;
		}else{
			root.addNode(node);
		}
	}
	//中序周遊
	public void infixOrder(){
		if(root != null){
			root.infixOrder();
		}else{
			System.out.println("空樹");
		}
	}
	//查找要删除的節點
	public Node search(int value){
		if(root == null){
			return null;
		}else{
			return root.search(value);
		}
	}
	//查找待删除節點的父節點
	public Node searchParent(int value){
		if(root == null){
			return null;
		}else{
			return root.searchParent(value);
		}
	}
	//編寫方法
	/**
	 * 傳回最小節點值，并且删除以node為根節點的二叉排序樹的最小節點
	 * @param node	當做一顆二叉排序樹的根節點
	 * @return		傳回的以node為根節點的二叉排序樹的最小節點的值
	 */
	public int delRightTreeMin(Node node){
		Node target = node;
		//循環查找左子節點，就會找到最小值
		while(target.left != null){
			target = target.left;
		}
		//這是target就指向了最小節點
		//删除最小節點
		delNode(target.value);
		return target.value;
	}
	
	//删除葉子結點的方法
	public void delNode(int value){
		if(root == null){
			return;
		}else{
			//1.需要先去找到待删除節點
			Node targetNode = search(value);
			//如果沒有找到
			if(targetNode == null){
				return;
			}
			//如果目前這課二叉排序樹隻有一個節點
			if(root.left == null&& root.right == null){
				root = null;
				return;
			}
			//去查找targetNode的父節點
			Node parent = searchParent(value);
			//如果待删除的節點是葉子結點
			if(targetNode.left == null && targetNode.right == null){
				//如果targetNode是parent的左子節點
				if(parent.left != null && parent.left.value == targetNode.value){
					parent.left = null;
				}else if(parent.right != null && parent.right.value == targetNode.value){
					parent.right = null;
				}
			}else if(targetNode.left!=null && targetNode.right != null){
				int minValue = delRightTreeMin(targetNode.right);
				targetNode.value = minValue;
			}else{
				//删除隻有一個子樹的節點
				//如果删除的節點有左子節點
				if(targetNode.left != null){
					if(parent.left.value == targetNode.value){
						parent.left = targetNode.left;
					}else{
						parent.right = targetNode.left;
					}
				}else{
					//要删除的節點有右子節點
					if(parent.left.value == targetNode.value){
						parent.left = targetNode.right;
					}else{
						parent.right = targetNode.right;
					}
				}
			}
		}
	}
}







class Node{
	int value;
	Node left;
	Node right;
	public Node(int value) {
		super();
		this.value = value;
	}
	
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}
	//傳回目前節點的高度=以根節點為樹的高度
	public int height(){
		return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height())+1;
	}
	//傳回左子樹的高度
	public int leftHeight(){
		if(left == null){
			return 0;
		}
		return left.height();
	}
	//傳回右子樹的高度
	public int rightHeight(){
		if(right == null){
			return 0;
		}
		return right.height();
	}
	//左旋轉方法
	private void leftRotate(){
		//建立新節點，是目前的根節點的值
		Node node = new Node(value);
		//把新的節點的左子樹，指向目前節點的左子樹
		node.left = left;
		//把新的節點的右子樹設定成目前節點的右子樹的左子樹
		node.right = right.left;
		//把目前節點的值，替換成右子節點的值
		value = right.value;
		//把目前節點的右子樹設定成右子樹的右子樹
		right = right.right;
		//把目前節點的左子樹，設定成我們新加的那個節點
		left = node;
	}
	
	/**
	 * 查找待删除的節點
	 * @param value	待删除節點的值
	 * @return
	 */
	public Node search(int value){
		if(value == this.value){
			return this;
		}else if(value < this.value){//應該向左子樹遞歸查找
			if(this.left != null){
				return this.left.search(value);
			}else{
				return null;
			}
		}else{
			if(this.right == null){
				return null;
			}else{
				return this.right.search(value);
			}
		}
	}
	/**
	 * 查找待删除節點的父節點
	 * @param value		待删除節點的值
	 * @return     傳回待删除節點的父節點
	 */
	public Node searchParent(int value){
		if((this.left !=null && this.left.value == value) || (this.right != null && this.right.value == value)){
			//目前節點就是待删除節點的父節點
			return this;
		}else{
			//如果查找的值，小于目前節點的值，且目前節點的左子節點不為空
			if(value < this.value && this.left != null){
				return this.left.searchParent(value);
			}else if(value >= this.value && this.right != null){
				return this.right.searchParent(value);
			}else{
				return null;//沒有找到父節點
			}
		}
	}
	
	
	//添加節點的方法
	//遞歸的形式添加節點，需要滿足二叉排序樹
	public void addNode(Node node){
		if(node == null){
			return;
		}
		//判斷傳入的節點值，跟目前子樹根節點值的關系
		if(node.value < this.value){
			//如果目前節點的左子節點為空
			if(this.left == null){
				this.left = node;
			}else
			{
				this.left.addNode(node);//遞歸添加
			}
		}else{
			if(this.right == null){
				this.right = node;
			}else{
				this.right.addNode(node);
			}
		}
		//當添加完一個節點後，如果右子樹的高度-左子樹的高度>1，左旋轉
		if(rightHeight() - leftHeight() > 1){
			leftRotate();//左旋轉
		}
	}
	//中序周遊
	public void infixOrder(){
		if(this.left != null){
			this.left.infixOrder();
		}
		System.out.println(this);
		if(this.right != null){
			this.right.infixOrder();
		}
	}
}
           

上面我們是把問題想成最簡單的情況，隻有右子樹左旋，

那如果有其他情況呢？

右旋轉

同理隻需要寫出對應的右旋轉方法即可，這個地方我就專貼方法代碼了

//右旋轉
	private void rightRotate(){
		Node newNode = new Node(value);
		newNode.right = right;
		newNode.left = left.right;
		value = left.value;
		left = left.left;
		right = newNode;
	}
           

問題

如果我們的數組換成10,11,7,6,8,9我們就會發現，即使我們進行了平衡處理，但是依然不是一個平很二叉樹

這是為什麼呢？

根據這個圖，我們不難看出，右旋轉就是把8,9旋轉過去，但是這個數正好很特别，導緻，即使旋轉過去還是不平衡的

1.當符合右旋轉的條件時

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

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

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

代碼修改

主要是在我們的添加節點的時候，加上一些邏輯判斷

//添加節點的方法
	//遞歸的形式添加節點，需要滿足二叉排序樹
	public void addNode(Node node){
		if(node == null){
			return;
		}
		//判斷傳入的節點值，跟目前子樹根節點值的關系
		if(node.value < this.value){
			//如果目前節點的左子節點為空
			if(this.left == null){
				this.left = node;
			}else
			{
				this.left.addNode(node);//遞歸添加
			}
		}else{
			if(this.right == null){
				this.right = node;
			}else{
				this.right.addNode(node);
			}
		}
		//當添加完一個節點後，如果右子樹的高度-左子樹的高度>1，左旋轉
		if(rightHeight() - leftHeight() > 1){
			//如果它的右子樹的左子樹高度大于它的右子樹的高度
			if(right != null && right.leftHeight() > right.rightHeight()){
				//先對右子樹進行右旋轉
				right.rightRotate();
				//然後對目前節點左旋轉
				leftRotate();//左旋轉
			}else{
				leftRotate();
			}
			return;
		}
		if(leftHeight() - rightHeight() > 1){
			//如果它的左子樹的右子樹高度大于它的左子樹的高度
			if(left != null && left.rightHeight() > left.leftHeight()){
				//先對目前節點的左節點(左子樹)進行左旋轉
				left.leftRotate();
				//在對目前節點進行右旋轉
				rightRotate();
			}else{
				rightRotate();
			}
		}
	}