Table of Contents
前言
昨天我們介紹了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上面；經過我的實測結果，其示意圖如下：
小結
- BST的讀取順序分為Preorder, Inorder和Postorder。
- BST的平衡會大幅影響執行效率。
預告
明天我們將會介紹新的演算法類別-Divide and Conquer。