5分鐘了解二叉樹之二叉查找樹

• 2022 年 4 月 16 日
• 筆記
• 圖解演算法與數據結構, 演算法與數據結構

轉載請註明出處：//www.cnblogs.com/morningli/p/16033726.html

二叉樹主要用於兩種用途，一是用來建立索引，通過索引的建立快速檢索海量數據；二是用來保存資訊，比如生物的遺傳樹等。我們程式設計師主要還是關注前一種用途，本文講到的二叉查找樹正是利用二叉樹的特性快速查找數據的一種數據結構。

首先我們來了解一下二叉查找樹的定義：

它或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值； 它的左、右子樹也分別為二叉排序樹。

二叉查找樹又叫二叉搜索樹、二叉排序樹。二叉查找樹作為一種經典的數據結構，它既有鏈表的快速插入與刪除操作的特點，又有數組快速查找的優勢；應用十分廣泛，可用於實現動態集和查找表，例如在文件系統和資料庫系統一般會採用這種數據結構進行高效率的排序與檢索操作。

時間複雜度

搜索

遞歸搜索

 Tree-Search(x, key)
   if x = NIL or key = x.key then
     return x
   if key < x.key then
     return Tree-Search(x.left, key)
   else
     return Tree-Search(x.right, key)
   end if

迭代搜索

Iterative-Tree-Search(x, key)
   while x ≠ NIL and key ≠ x.key then
     if key < x.key then
       x := x.left
     else
       x := x.right
     end if
   repeat
   return x

插入

1    Tree-Insert(T, z)
2      y := NIL
3      x := T.root
4      while x ≠ NIL do
5        y := x
6        if z.key < x.key then
7          x := x.left
8        else
9          x := x.right
10       end if
11     repeat
12     z.parent := y
13     if y = NIL then
14       T.root := z
15     else if z.key < y.key then
16       y.left := z
17     else
18       y.right := z
19     end if

刪除

刪除一個節點，比如說z, 從二叉搜索樹T應遵守三種情況：

1. z是葉子節點：直接刪除，不影響原樹。
2. z僅僅有左或右子樹的節點：節點刪除後，將它的左子樹或右子樹整個移動到刪除節點z的位置就可以，子承父業。見下圖(a)和(b)

z既有左又有右子樹的節點：找到須要刪除的節點z的後繼y（右子樹最小節點），用y的數據來替待z的數據，然後再刪除節點y。

1. y是z的直接右子節點，y提升到z的位置，左指針指向原來z的左子樹，見下圖(c)
2. y不是z的直接右子節點，y的右子節點（y不可能有左子節點）取代y的位置，y取代z的位置，見下圖(d)

本文主要講二叉查找樹的一些主要操作，二叉查找樹的主要問題是樹的形狀完全跟插入刪除數據的順序有關，在一些場景下很容易就退化成了普通的鏈表，這也是二叉查找樹的時間複雜度最差的時候會是O(n)的原因，下一篇會繼續深入講解二叉樹查找樹會如何退化以及如何應對，敬請期待。 

引用：

//baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855?fr=aladdin

//en.wikipedia.org/wiki/Binary_search_tree