摘要訊息 : 一種搜尋友好的二元樹.

0. 前言

在《【資料結構】樹——二元樹》中, 我們介紹了二元樹, 也提到了二元樹是應用最多的樹. 像堆積 (《【資料結構與演算法】堆積, 堆積排序和優先佇列》), 左偏樹 (《【資料結構】樹——左偏樹》) 和一般的贏者樹 (《【資料結構】樹——贏者樹》) 都是二元樹. 但是這些二元樹的元素有序性不夠強, 或者只能在一定程度上維持元素的有序性. 這些資料結構中, 雖然堆積的元素有序性算是最高, 但是如果要得到一個有序的序列, 它需要付出 \Theta(n\log {n}) 的時間代價. 除此之外, 在堆積中搜尋元素是很困難的, 基本上類似於線性搜尋. 因此, 我們需要引入一種搜尋友好的有序二元樹.

Tip : 第 5 節和第 6 節將在之後的更新中補全.

1. 定義

定義 1. 設二元樹 \mathcal {T} 滿足

• 任意節點的左子節點 (若存在), 其元素小於等於父節點元素;
• 任意節點的右子節點 (若存在), 其元素大於等於父節點元素,

則稱 \mathcal {T} 為二元搜尋樹 (binary search tree).

根據定義 1, 二元搜尋樹 \mathcal {T} 中以任意節點為子樹的二元樹都是一棵二元搜尋樹.

如果定義嚴格一些, 把等於這個可滿足條件從定義 1 中去掉, 那麼這棵二元搜尋樹中的元素是不可重複的.

性質 1. 二元搜尋樹的中序尋訪結果是升序序列.

證明 :

我們使用歸謬法進行證明. 不妨設存在二元搜尋樹, 它的中序尋訪無法產生升序序列. 若假設成立, 那麼必定存在一個規模最小的二元搜尋樹不滿足斷言, 不妨記這棵二元搜尋樹為 \mathcal {T}. 顯然, \mathcal {T} 不能僅有一個節點, 因為對單個節點的二元樹的中序尋訪結果必定是有序的. 於是, \mathcal {T} 中存在多個節點.

記 \mathcal {T} 的根節點中的元素為 r, 其左子節點為 l, 右子節點為 r. 設 l 的中序尋訪結果為 x_{l}, r 的中序尋訪結果為 x_{r}. 由於我們要求 \mathcal {T} 的規模最小, 於是以 l 為根節點的子樹和以 r 為根節點的子樹必定滿足定義 1, 所以任意來自 l 中的元素都不會大於來自 r 中的元素. 因此, 樹 \mathcal {T} 的尋訪結果可以表示為 x_{l}rx_{r}. 然而這個序列必定是升序的, 和假設衝突.

因此, 二元搜尋樹的中序尋訪結果是升序序列.

\blacksquare

2. 搜尋

二元搜尋樹的名稱帶有搜尋, 是因為它是搜尋友好的. 在一棵非空的二元搜尋樹中尋找一個元素 e, 首先將其和根節點中的元素比較, 如果 e 比根節點元素要大, 那麼就進入右子樹中進行搜尋; 如果 e 比根節點元素要小, 那麼就進入左子樹中進行搜尋. 在這樣的情況下, 若樹的高度為 h, 那麼搜尋的時間複雜度為 O(h). 若一棵二元搜尋樹中有 n 個元素, 根據《【資料結構】樹——二元樹》性質 3 那麼樹高至多為 n, 至少為 \left \lceil \log_{2} {(n + 1)} \right \rceil. 因此在最好的情況下, 在二元搜尋樹中搜尋的時間複雜度為 \Omega(\log {n}). 值得一提的是, 不論在什麼情況下, 二元搜尋樹中搜尋元素需要的輔助空間和節點數量無關, 因此空間複雜度為 \Theta(1).

例題 1. 在 Figure 1 中的二元搜尋樹 \mathcal {T} 中搜尋元素 37.

解 :

首先比較根節點元素 30, 由於 30 < 37, 因此進入右子樹中進行搜尋. 比較 36 和 37, 由於 36 < 37, 因此進入 36 的右子樹中進行搜尋. 最後, 由於 37 < 40, 因此可以判定在 \mathcal {T} 中不存在元素 37.

\blacksquare

3. 插入

向二元搜尋樹中插入一個元素必須維持二元搜尋樹的定義. 根據在二元搜尋樹中搜尋的結果, 我們只要將要插入的元素插入到一個空的子節點中即可. 記 E(\cdot) 表示節點 \cdot 中的元素, 設 p 是二元樹中某個節點, 要插入的元素為 e. 如果 e < E(p), 說明 e 必定要成為 p 左子樹中的一個節點. 此時, 若 p 的左子節點為空, 那麼我們可以直接將 e 插入到 p 的左子節點中; 否則, 繼續在 p 的左子樹中搜尋一個合適的位置. 如果 e \geq E(p), 那麼就看 p 的右子節點是否為空, 如果是的話就插入到 p 的右子節點上, 否則就繼續在 p 的右子樹中搜尋合適的位置.

例題 2. 向 Figure 1 中的二元搜尋樹 \mathcal {T} 中插入元素 32.

解 :

從 \mathcal {T} 的根節點開始比較. 由於 30 < 32, 因此 32 應該被插入到 30 的右子樹中. 接下來, 36 > 32, 因此 32 應該被插入到 36 左子樹中. 因為 33 > 32, 所以 32 應該插入到 33 的左子樹中. 最後, 31 < 32, 又因 31 不存在右子節點, 因此把 32 安排到 31 的右子節點上.

\blacksquare

容易地, 我們可以得到向二元搜尋樹中插入元素的時間複雜度為 \Theta(h), 空間複雜度為 \Theta(1). 其中, h 是樹的高度.

4. 移除

從二元搜尋樹中移除元素要比搜尋和插入操作都要複雜, 我們將總體情況分成三種 :

1. 要移除的節點是葉子節點;
2. 要移除的節點有一棵非空子樹;
3. 要移除的節點有兩棵非空子樹.

第一種情況非常簡單, 只需要移除這個節點即可. 在第二種情況下, 設要移除的節點為 p, 其非空子節點為 c. 如果要移除的節點是根節點, 那麼只要讓 c 作為新的根節點即可; 否則, 將以 c 為根節點的子樹掛到原來 p 節點所在的位置即可. 第三種情況有兩種解決方案, 我們並不會將兩棵子樹進行拆分或者合併, 而是選擇左子樹中最大的節點或者右子樹中最小的節點作為新的子樹根節點, 然後這個新的根節點會替代被移除的 p. 左子樹中的最大元素對應的節點只需要沿著右子節點走到葉子節點即可找到, 右子樹中最小元素對應的節點只需要沿著左子節點走到葉子節點即可找到.

例題 3. 從 Figure 1 中的二元搜尋樹 \mathcal {T} 中移除元素 36.

解 :

在 \mathcal {T} 中找到了元素 36 之後, 我們發現元素 36 對應的節點有兩棵子樹, 我們可以從左子樹中選擇最大的元素 35 作為新的根節點元素; 也可以從右子樹中選擇最小的元素 40 作為新的根節點元素.

\blacksquare

5. 和二元搜尋樹有關的演算法

二元搜尋樹在二元樹中非常重要, 所以有很多演算法都和二元搜尋樹有關.

5.1 二元搜尋樹排列

給定一個整數範圍 [m, n], 要求生成所有不同的二元搜尋樹, 這些二元搜尋樹包含此範圍內所有整數.

5.2 二元搜尋樹復原

設二元搜尋樹 \mathcal {T} 中的兩個節點 n_{1} 和 n_{2} 被意外地交換了, 找到這兩個節點並且復原.

5.3 平衡的二元搜尋樹

給定一個升序的序列 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 要求生成一棵二元搜尋樹, 其滿足任意節點的兩棵子樹的高度之差不超過 1. 其中, \alpha_{1} \leq \alpha_{2} \leq ... \leq \alpha_{n}.

現在將 \boldsymbol {\alpha} 更換為一個前向連結串列 \left \{ (\alpha_{1}, p_{2}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}, 要求從這個前向連結串列生成高度平衡的二元搜尋樹.

5.4 最近公共祖先

設節點 m 和 n 位於根節點為 p 的子樹中, 若子樹中不存在節點 p' 滿足

• p = p';
• p' 是 m 的祖先;
• p' 是 n 的祖先,

那麼稱 p 是節點 m 和 n 的最近公共祖先 (lowest common ancestor).

現任意給定二元搜尋樹 \mathcal {T} 中的兩個節點 m 和 n, 要求尋找 m 和 n 的最近公共祖先.

5.5 尋訪結果

任意給定一個序列 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 要求判斷這個序列是否為二元搜尋樹的尋訪結果.

5.6 最接近 n 的 k 個值

給定二元搜尋樹 \mathcal {T} 和一個值 n (n 可能是小數), 要求在 \mathcal {T} 中找到 k 個最接近 n 的值. 其中, 1 \leq k \leq \mathop {\mathrm {card}}{\mathcal {T}}.

5.7 節點最多的子樹

給定二元搜尋樹 \mathcal {T}, 要求在 \mathcal {T} 中找到節點最多的子樹.

5.8 出現頻率最高的元素

給定二元搜尋樹 \mathcal {T}, 要求在 \mathcal {T} 中找到出現次數最多的元素.

6. 實作

我自己用 C++ 實作了二元搜尋樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/binary_search_tree.hpp, 大家可以參考後自行實作.