本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

昨天我們介紹了Binary Search Tree(BST)，而今天要講的BST包含了兩點：Process BST和Balancing。

讀取BST的順序

我自己在實作BST的時候，我一定要把BST的每個Node數值印出來，我才能確定我所實作的Search, Insert和Delete是正確的，因此如何把BST的內容按照所期望的方式印出來就是我這邊要介紹的內容，大致上讀取BST時有三種過程：

1. Preorder:

Preorder是先讀取Root Node，才往左邊分支往下開始讀取，等左邊分支的Node都讀取完了，再前往右邊分支去讀取。

2. Inorder:

Inorder是先一路向下，下到左邊分支的最左下角開始讀取，然後再來是Root Node，再來才是右邊分支。這是唯一一個讀取後是『正序排列』的結果。

3. Postorder:

Postorder則是先讀取左邊分支，再來是右邊分支，最後才讀取Root Node。

How to Balance BST

昨天有提到BST有分為Balanced BST和Unbalanced BST，而有沒有BST有沒有被Balanced可以說是很關鍵的一個問題；試問，假設現在有一個陣列的長度是15，那如果一個BST沒有進行過Balance，那這個BST的Height就會是14（原因請看昨日的分享），這樣表示若是這種狀況下，在進行BST Search的時候，最壞的狀況下要找到最後一個Node才有結果；但是如果經過Balanced的BST，其Height僅為4，如此一來，進行BST Search最壞的情況下也只需要找四次就可以有結果了。那我們要怎麼去做到balance這件事呢？

Code在此，給大家參考，不敢說效能很好，但是經過我的測試看起來是可行的：

public class BSTProc {
	
	private BSTProc parentNode;
	private BSTProc leftNode;
	private BSTProc rightNode;
	
	public BSTProc(String procLabel, int vt) {
		this(procLabel, vt, null, null, null);
	}
	
	public BSTProc(String procLabel, int vt, BSTProc parentNode, BSTProc leftNode, BSTProc rightNode) {
		super.setProcLabel(procLabel);
		super.setVt(vt);
		this.setParentNode(parentNode);
		this.setLeftNode(leftNode);
		this.setRightNode(rightNode);
	}

	public BSTProc getParentNode() {
		return parentNode;
	}

	public void setParentNode(BSTProc parentNode) {
		this.parentNode = parentNode;
	}

	public BSTProc getLeftNode() {
		return leftNode;
	}

	public void setLeftNode(BSTProc leftNode) {
		this.leftNode = leftNode;
	}

	public BSTProc getRightNode() {
		return rightNode;
	}

	public void setRightNode(BSTProc rightNode) {
		this.rightNode = rightNode;
	} 

}

    // Rebuild an existed BST
    public void rebuild() {
		
        index = 0;
        
        // Transform a BST to an sorted array
		BSTProc[] array = getProcessAsc(new BSTProc[size], rootNode);
        
        // Get the index of middle value of the array
        int middleIndex = Integer.valueOf(array.length/2);
        // Set the value of the root node as the value of the middle of the array
		rootNode = array[middleIndex];
		rootNode.setParentNode(null);
        
        // Set left node, starting from root node recursively.
        rootNode.setLeftNode(treeBuilder(array, 0, middleIndex-1, rootNode));
        
        // Set right node, starting from root node recursively.
		rootNode.setRightNode(treeBuilder(array, middleIndex+1, array.length-1, rootNode));
		
    }
    
    private BSTProc[] getProcessAsc(BSTProc[] array, BSTProc currentNode) {
		
		if (currentNode.getLeftNode() != null) {
			array = getProcessAsc(array, currentNode.getLeftNode());
		}
		
		array[index] = currentNode;
		index++;
		
		if (currentNode.getRightNode() != null) {
			array = getProcessAsc(array, currentNode.getRightNode());
		}
		
		return array;
	}

	private BSTProc treeBuilder(BSTProc[] array, int startIndex, int endIndex, BSTProc parentNode) {
		
		if (endIndex < startIndex) {
			return null;
		}
		
		int middleIndex = (startIndex + endIndex)/2;
		BSTProc currentNode = array[middleIndex];
		if ( currentNode != null) {
			currentNode.setParentNode(parentNode);
			currentNode.setLeftNode(treeBuilder(array, startIndex, middleIndex-1, currentNode));
			currentNode.setRightNode(treeBuilder(array, middleIndex+1, endIndex, currentNode));
		}
		
		return currentNode;
	}

基本上這個方式是將原本已經存在的ＢＳＴ，轉換成正序排列的Array後，將Array一再拆分成兩邊，找出其對應的child node後，在連到對應的parent node上面；經過我的實測結果，其示意圖如下：

小結

1. BST的讀取順序分為Preorder, Inorder和Postorder。
2. BST的平衡會大幅影響執行效率。

預告

明天我們將會介紹新的演算法類別-Divide and Conquer。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin