二元搜尋樹(Binary Search Tree)

1. 摘要
2. 搜尋資料
3. 新增資料
4. 刪除資料
5. 遍歷資料

摘要

參考資料:維基百科資料結構大便當 — 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 ----
  1. 要刪除的310,Next為NULL,刪除310後,Parent的Previous設定為X
//------------- Parent ------------
//----- 310(當前) -------------------
//-- X ----- NULL ------------------
  1. 要刪除的310,Next為NULL,刪除310後,Parent設定為X
//-------- Parent(310當前) ----------------
//---- X ------------- NULL --------------
  1. 要刪除的310,Previous為NULL,刪除310後,Parent的Next設定為X
//------------ Parent ----------------
//----------------------- 310 -------
//----------------- NULL ------- X --
  1. 要刪除的310,Previous為NULL,刪除310後,Parent的Previous設定為X
//------------ Parent ----------------
//---- 310 --------------------------
//NULL ---- X -----------------------
  1. 要刪除的310,Previous為NULL,刪除310後,Parent設定為X
//------- Parent(310當前) --------------
//--- NULL ------------ X -------------
  1. 要刪除的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());
    }
}

訂閱Codeilin的旅程,若有最新消息會通知。

廣告

對「二元搜尋樹(Binary Search Tree)」的一則回應

Add yours

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

WordPress.com.

向上 ↑

%d 位部落客按了讚: