二元搜尋樹(Binary Search Tree)

摘要

參考資料：維基百科、資料結構大便當 — binary search tree

優點：程式碼簡潔、執行效率高，適合資料庫使用，搜尋、新增、刪除、插入都很方便

缺點：必須事先排序、有左右指標，需要記憶體較大的記憶體

比current小的為previous

比current小的為next

//-------------------- 200(current) ------------------
//------- 180(previous) ----------- 300(next) --------
//- 140 ------- 190 -------- 250 --------- 325 -------

---

資料搜尋

搜尋成功

//----------------- 200(Root當前) --------------
//------- 180 -------------------- 300 --------
//- NULL ------- 190 -------- 250 ------- 325 -

• 假設要搜尋325，首先找到Root
• 因為325比Root大，所以搜尋Root的Next

//----------------- 200(Root) -----------------------
//------- 180 -------------------- 300(當前) --------
//- NULL ------- 190 -------- 250 --------- 325 ----

• 此時當前變為300
• 因為325比300大，所以找300的Next

//----------------- 200(Root) -----------------------
//------- 180 -------------------- 300 --------------
//- NULL ------- 190 -------- 250 ------ 325(當前) ---

• 此時當前變為325，就搜尋到指定的資料囉

搜尋失敗

//----------------- 200(Root當前) --------------
//------- 180 -------------------- 300 --------
//- NULL ------- 190 -------- 250 ------- 325 -

• 假設要搜尋170，首先找到Root
• 因為170比Root小，所以搜尋Root的Previous

//-------------------- 200(Root) -------------------
//------- 180(當前) -------------------- 300 --------
//- NULL ------- 190 -------- 250 --------- 325 ----

• 此時當前變為180
• 因為170比180小，所以找180的Previous

//----------------- 200(Root) -----------------------
//--------- 180 -------------------- 300 ------------
//- NULL(當前) ------- 190 --- 250 ------ 325 --------

• 此時當前變為NULL，搜尋失敗

新增資料

在NULL位置，新增資料

//-------------------------- 200(Root當前) ---------------------------
//----------- 180 -------------------------------- 300 ---------------
//----- NULL ------ 190 ---------------- 250 ------------ 325 --------

• 假設要新增30
• 首先以Root開始，檢查Root Previous是否為NULL，如果是則新增

//------------------------- 200(Root) ------------------------------
//---------- 180(當前) ------------------------- 300 ----------------
//- NULL ------------ 190 ------------ 250 ------------- 325 -------

• 此時當前變為180
• 因為30比180小，所以找180的Previous

//------------------------- 200(Root) ------------------------------
//---------- 180 ------------------------------- 300 ---------------
//- NULL(當前) ------- 190 ------------ 250 ------------- 325 -------

• 當前為NULL，因此在此新增資料

已存在則不新增

//------------------------- 200(Root當前) ---------------------------
//---------- 180 ------------------------------- 300 ---------------
//- NULL ------------ 190 ------------ 250 -------------- 325 ------

• 假設要新增180
• 首先以Root開始，檢查Root Previous是否為NULL，如果是則新增

//------------------------- 200(Root) ------------------------------
//---------- 180(當前) -------------------------- 300 ---------------
//- NULL ------------ 190 ------------ 250 -------------- 325 ------

• 此時當前變為180
• 因為180已存在，所以不新增

刪除資料

//---------------------------- 200(Root當前) -----------------------------
//---------- 180 --------------------------------- 300 ------------------
//--- 60 ------------ 190 -------------- 250 -------------- 325 ---------
//-30---- 90 --- 185 ----- 195 ---- 210 ----- 260------ 310 ---- 350 ----

• 假設要刪除310
• 首先以Root開始，檢查Root Next是否為NULL，NULL則刪除失敗

//---------------------------- 200(Root) --------------------------------
//---------- 180 --------------------------------- 300(當前) -------------
//--- 60 ------------ 190 -------------- 250 -------------- 325 ---------
//-30---- 90 --- 185 ----- 195 ---- 210 ----- 260------ 310 ---- 350 ----

• 此時當前變為300
• 因為310比300大，檢查Next是否為NULL，如果是則刪除失敗

//---------------------------- 200(Root) --------------------------------
//---------- 180 --------------------------------- 300 ------------------
//--- 60 ------------ 190 -------------- 250 -------------- 325(當前) ----
//-30---- 90 --- 185 ----- 195 ---- 210 ----- 260------ 310 ---- 350 ----

• 此時當前變為325
• 因為310比325小，檢查Previous是否為NULL，如果是則刪除失敗

//---------------------------- 200(Root) ----------------------------------
//---------- 180 --------------------------------- 300 --------------------
//--- 60 ------------ 190 -------------- 250 ---------------- 325 ---------
//-30---- 90 --- 185 ----- 195 ---- 210 ----- 260------ 310(當前) --- 350 --

• 此時當前變為310
• 將310刪除，此時會有幾種狀況，如下

1. 要刪除的310，Next為NULL，刪除310後，Parent的Next設定為X

//----- Parent --------------
//------------ 310(當前) -----
//--------- X ----- NULL ----

2. 要刪除的310，Next為NULL，刪除310後，Parent的Previous設定為X

//------------- Parent ------------
//----- 310(當前) -------------------
//-- X ----- NULL ------------------

3. 要刪除的310，Next為NULL，刪除310後，Parent設定為X

//-------- Parent(310當前) ----------------
//---- X ------------- NULL --------------

4. 要刪除的310，Previous為NULL，刪除310後，Parent的Next設定為X

//------------ Parent ----------------
//----------------------- 310 -------
//----------------- NULL ------- X --

5. 要刪除的310，Previous為NULL，刪除310後，Parent的Previous設定為X

//------------ Parent ----------------
//---- 310 --------------------------
//NULL ---- X -----------------------

6. 要刪除的310，Previous為NULL，刪除310後，Parent設定為X

//------- Parent(310當前) --------------
//--- NULL ------------ X -------------

7. 要刪除的310，Previous與Next皆不是NULL，狀況如下

//狀況一
//------------- 310 ----------------------
//----- 308 ---------------- 312 ---------
//------------------- 311 -------- 315 ---
//假如刪310，312直接替補上去
//會發生兩個左邊，308、311
//所以這時候，應該是311替補310的位置
//------------- 311 ----------------------
//---- 308 ---------------- 312 ----------
//------------------------------- 315 ----
//此狀況只會發生在刪除時，有左有右的情況

//狀況二
//------------- 310 ---------------------
//----- 308 -------------- 312 ----------
//------------------------------- 315 ---
//假如刪310，可以312直接替補上去
//因為只有一個左邊，308
//------------- 312 ----------------------
//----- 308 -------------- 315 ---------

遍歷資料

由Root找到最左邊->在找右邊，如下

public void traverse(ListItem root) {
    if(root != null) {
        traverse(root.previous());
        System.out.println("A " + root.getValue());
        traverse(root.next());
    }
}