摘要訊息 : 應用最多的樹.

0. 前言

在《【資料結構】樹》中, 我們對樹進行了介紹. 但是一般的樹其實應用得不是太多, 因為可以針對它們使用的演算法並不多. 而如果限制子節點的數量, 使得子節點最多不超過兩個, 根據《【資料結構】樹》定義 5, 這棵樹便是二元樹. 二元樹是應用得最多的樹.

更新紀錄 :

• 2022 年 6 月 13 日進行第一次更新和修正.

1. 定義

根據《【資料結構】樹》定義 5, 如果總有 $m = 2$, 那麼這棵樹就是二元樹. 但是這樣的定義和二元樹的嚴格定義存在出入.

定義 1. 若向量 $\boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}$ 的擴展 $\mathcal {T} = \left \{ \big ( \alpha_{1}, (p_{1}, l_{1}, r_{1}) \big ), \big ( \alpha_{2}, (p_{2}, l_{2}, r_{2}) \big ), ..., \big ( \alpha_{n}, (p_{n}, l_{n}, r_{n}) \big ) \right \}$ 滿足

• 必定存在且僅存在一個 $p_{k} = \infty$ ($k = 1, 2, ..., n$);
• 從任意 $\big ( \alpha_{i}, (p_{i}, r_{i}, l_{i}) \big )$ 出發都不存在回到 $\big ( \alpha_{i}, (p_{i}, r_{i}, l_{i}) \big )$ 的路徑,

那麼我們稱 $\mathcal {T}$ 為二元樹 (binary tree). 其中, $\big ( \alpha_{i}, (p_{i}, r_{i}, l_{i}) \big )$ 稱為樹的節點, $(p_{i}, r_{i}, l_{i})$ 是節點 $\big ( \alpha_{i}, (p_{i}, r_{i}, l_{i}) \big )$ 的指向型標記組 (指向型標記見《【資料結構】前向連結串列》第 1 節), , $p_{i}$ 指向父節點 (parent node), $l_{i}$ 指向左子節點 (left child node), $r_{i}$ 指向右子節點 (right child node), $i = 1, 2, ..., n$ 且 $j = 1, 2, ..., m_{i}$.

比較《【資料結構】樹》定義 5和二元樹的定義 1, 我們可以發現除了節點存在數量限制之外, 樹和二元樹還有一個區別, 就是樹不允許為空, 但是二元樹可以為空. 即對於樹來說, 不允許 $n = 0$, 但是二元樹的定義中沒有這個限制.

由定義 1 可知, 二元樹中的任意子樹也是一棵二元樹.

定義 2. 對於一棵高度為 $h$ 的二元樹, 若其恰好有 $2^{h} - 1$ 個節點, 則稱這棵樹為完美二元樹 (perfect binary tree), 也稱為滿二元樹 (full binary tree).

如果為 Figure 1 中的 $\alpha_{5}$ 補充左子節點和右子節點, 再為 $\alpha_{7}$ 補充左子節點, 那麼 Figure 1 中的樹將成為一棵完美二元樹.

2. 性質

性質 1. 若一棵二元樹中有 $n$ 個節點, 那麼它必定有 $n - 1$ 條邊. 其中, $n > 0$.

$證明$ :

一棵二元樹中, 除了根節點之外, 每一個子節點都有且唯有一個父節點. 因此, 除根節點之外的剩餘 $n - 1$ 個節點共有 $n - 1$ 條邊和其父節點相連結, 而根節點沒有父節點. 故若一棵二元樹有 $n$ 個元素, 那麼它必定有 $n - 1$ 條邊. 其中, $n > 0$.

$\blacksquare$

性質 2. 若一棵二元樹的高度為 $h$, 則它至少有 $h$ 個節點, 至多有 $2^{h} - 1$ 個節點. 其中, $h \geq 0$.

$證明$ :

首先, 對於一棵高度為 $h$ 的二元樹, 每一層都至少有一個節點, 因此至少有 $h$ 個元素.

$\square$

考慮到二元樹中一個父節點至多攜帶兩個子節點, 因此第 $i$ 層至多有 $2^{i - 1}$ 個節點, $i = 1, 2, ..., h$. 當 $h = 0$ 時, 節點的總數為 $0$, 即 $2^{0} - 1 = 0$; 當 $h > 0$ 時, 節點的總數為 $\displaystyle {\sum \limits_{i = 1}^{h}2^{i - 1} = 2^{h} - 1}$ 個.

$\square$

因此, 若一棵二元樹的高度為 $h$, 則它至少有 $h$ 個節點, 至多有 $2^{h} - 1$ 個節點. 其中, $h \geq 0$.

$\blacksquare$

定義 3. 對於二元樹 $\mathcal {T}$, 設其高度為 $h$, 若其滿足

1. 第 $1$ 層到第 $h - 1$ 層共有 $2^{h - 1} - 1$ 個節點;
2. 最後一層的節點是連續存在的, 即
   • 若第 $h - 1$ 層的任意一個節點存在左子節點, 那麼這一層該節點之前的所有節點都存在左右子節點;
   • 若第 $h - 1$ 層的任意一個節點存在右子節點, 那麼該節點必定存在左子節點, 並且這一層該節點之前的所有節點都存在左右子節點,

那麼我們稱 $\mathcal {T}$ 為完全二元樹 (complete binary tree).

根據定義 3, 如果移除掉一棵完全二元樹的最後一層節點, 那麼它就是一棵完美二元樹. 另外, 最後一層的節點可以不是滿的, 但是必須是連續存在的, 中間不能空缺.

Figure 1 中的二元樹就不是完全二元樹, 因為根據定義 3, 節點 $\alpha_{6}$ 存在左子節點, 那麼就要求第三層在 $\alpha_{6}$ 之前的節點 $\alpha_{4}$ 和 $\alpha_{5}$ 必須存在左右子節點. 另外, 即使節點 $\alpha_{5}$ 存在左右子節點, Figure 1 中的二元樹仍然不存在完全二元樹, 因為 $\alpha_{7}$ 不存在左子節點. 如果移除節點 $\alpha_{10}$, $\alpha_{11}$ 和 $\alpha_{12}$ 之後, 那麼 Figure 1 中的這棵二元樹就會成為一棵完全二元樹.

顯然, 一棵完美二元樹就能滿足定義 3, 所以任意完美二元樹也同時都是完全二元樹.

性質 3. 若一棵二元樹有 $n$ 個元素, 那麼其高度最大為 $n$, 最小為 $\left \lceil \log_{2} {(n + 1)} \right \rceil$.

$證明$ :

由性質 2 可以知道, 若每一層有且唯有一個元素, 那麼此時樹的高度即為 $n$, 且不會超過 $n$.

$\square$

再由性質 2 可知, 高度為 $h$ 的二元樹至多有 $2^{h} - 1$ 個元素. 由於 $n \leq 2^{h} - 1$, 因此有 $h \geq \log_{2} {(n + 1)}$. 由於 $h$ 是整數, 因此 $h \geq \left \lceil \log_{2} {(n + 1)} \right \rceil$.

$\square$

因此, 若一棵二元樹有 $n$ 個元素, 那麼其高度最大為 $n$, 最小為 $\left \lceil \log_{2} {(n + 1)} \right \rceil$.

$\blacksquare$

3. 線性儲存

一般來說, 樹都是採用類似於連結串列 (《【資料結構】連結串列》) 那樣的方式進行儲存, 但是由於二元樹的特殊性, 我們也可以使用向量 (《【資料結構】向量 (順序表)》) 進行儲存.

在一棵完全二元樹種, 如果我們按照從上至下為基礎, 然後從左至右進行編號, 那麼一個父節點和子節點的序號是有嚴格關係的 : 設二元樹 $T$ 中某個節點的編號為 $i$, 則有

• 如果 $i = 1$, 則這個節點是二元樹的根節點;
• 如果 $i > 1$, 則
  1. 這個節點的父節點編號為 $\left \lfloor \frac {i}{2} \right \rfloor$;
  2. 如果 $2i \leq n$, 則編號為 $2i$ 的節點是這個節點的左子節點;
  3. 如果 $2i + 1 \leq n$, 則編號為 $2i + 1$ 的節點是這個節點的右子節點.

但是有些時候, 如果二元樹中的元素不多, 那麼使用陣列來儲存就會浪費很多空間 :

因此, 針對元素比較多的二元樹, 我們可以使用向量來儲存. 在大多數程式設計語言中, 一般直接採用陣列儲存, 而陣列的存取會比連結串列這樣的方式要快得多. 但是, 如果二元樹的高度比較大, 但是元素比較少, 應該謹慎考慮是否應該使用向量來儲存二元樹.

4. 尋訪

在《【資料結構】樹》第 2 節, 我們介紹了三種對樹的尋訪方式, 這些方式對二元樹仍然適用, 所以此處我們不再累贅. 不過由於二元樹的特殊性, 二元樹還有一種獨有的尋訪方式, 就是中序尋訪. 二元樹的中序尋訪是從根節點開始的, 首先遞迴地尋訪左子樹, 當左子樹全部尋訪完畢之後才尋訪本節點中的元素, 然後遞迴地尋訪右子樹.

例題 1. 寫出二元樹 $\mathcal {T}$

從根節點開始的尋訪結果.

$解$ :

對於層級尋訪, 就是按照從上到下, 從左到右的順序進行尋訪即可, 因此結果為 $\alpha_{1}$, $\alpha_{2}$, $\alpha_{3}$, $\alpha_{4}$, $\alpha_{5}$, $\alpha_{6}$, $\alpha_{7}$.

$\square$

對於次序尋訪, 實際上是需要遞迴進行的, 因此我們採用堆疊的演示方式. 首先來看前序尋訪 :

• 開始尋訪. 目前位於根節點. 根據前序尋訪的順序, 我們首先存取元素, 此時結果為 $\alpha_{1}$. 然後前往節點 $\alpha_{1}$ 的左子節點 :
  • 現在來到了節點 $\alpha_{2}$. 根據尋訪順序, 首先存取元素, 此時的結果為 $\alpha_{1}$, $\alpha_{2}$. 然後前往節點 $\alpha_{2}$ 的左子節點 :
    • 根據尋訪順序, 首先存取元素, 此時的結果為 $\alpha_{1}$, $\alpha_{2}$, $\alpha_{4}$. 然後嘗試前往節點 $\alpha_{4}$ 的左子節點的時候, 發現為空; 然後嘗試前往節點 $\alpha_{4}$ 的右子節點的時候, 發現仍然為空. 因此回溯到節點 $\alpha_{2}$.
  • 現在回到了節點 $\alpha_{2}$. 跟根據尋訪順序, 接下來要前往節點 $\alpha_{2}$ 的右子節點 :
    • 根據尋訪順序, 首先存取元素, 此時的結果為 $\alpha_{1}$, $\alpha_{2}$, $\alpha_{4}$, $\alpha_{5}$. 然後嘗試前往節點 $\alpha_{5}$ 的左子節點的時候, 發現為空; 然後嘗試前往節點 $\alpha_{5}$ 的右子節點的時候, 發現仍然為空. 因此回溯到節點 $\alpha_{2}$.
  • 現在又回到了節點 $\alpha_{2}$, 由於節點 $\alpha_{2}$ 的左右子樹都已經尋訪, 因此回溯到節點 $\alpha_{1}$.
• 現在回到了節點 $\alpha_{1}$. 根據前序尋訪的順序, 現在前往節點 $\alpha_{1}$ 的右子節點 :
  • 現在來到了節點 $\alpha_{3}$ 根據尋訪換序, 首先存取元素, 此時的結果為 $\alpha_{1}$, $\alpha_{2}$, $\alpha_{4}$, $\alpha_{5}$, $\alpha_{3}$. 然後嘗試前往節點 $\alpha_{3}$ 的左子樹 :
    • 根據尋訪順序, 首先存取元素, 此時的結果為 $\alpha_{1}$, $\alpha_{2}$, $\alpha_{4}$, $\alpha_{5}$, $\alpha_{3}$, $\alpha_{6}$. 然後嘗試前往節點 $\alpha_{6}$ 的左子節點的時候, 發現為空; 然後嘗試前往節點 $\alpha_{6}$ 的右子節點的時候, 發現仍然為空. 因此回溯到節點 $\alpha_{3}$.
  • 現在回到了節點 $\alpha_{3}$. 根據尋訪順序, 接下來要前往節點 $\alpha_{3}$ 的右子節點 :
    • 根據尋訪順序, 首先存取元素, 此時的結果為 $\alpha_{1}$, $\alpha_{2}$, $\alpha_{4}$, $\alpha_{5}$, $\alpha_{3}$, $\alpha_{6}$, $\alpha_{7}$. 然後嘗試前往節點 $\alpha_{7}$ 的左子節點的時候, 發現為空; 然後嘗試前往節點 $\alpha_{7}$ 的右子節點的時候, 發現仍然為空. 因此回溯到節點 $\alpha_{3}$.
  • 現在又回到了節點 $\alpha_{3}$. 由於節點 $\alpha_{3}$ 的左右子樹都已經尋訪, 因此回溯到節點 $\alpha_{1}$.
• 現在又回到了節點 $\alpha_{1}$. 由於節點 $\alpha_{1}$ 的左右子樹都已經尋訪, 因此嘗試回到節點 $\alpha_{1}$ 的父節點. 由於節點 $\alpha_{1}$ 沒有父節點, 代表著節點 $\alpha_{1}$ 就是這棵樹的根節點, 故尋訪完畢.

最終前序尋訪的結果為 $\alpha_{1}$, $\alpha_{2}$, $\alpha_{4}$, $\alpha_{5}$, $\alpha_{3}$, $\alpha_{6}$, $\alpha_{7}$.

$\square$

對於中序尋訪 :

• 開始尋訪. 目前位於根節點. 根據中序尋訪的順序, 我們首先前往節點 $\alpha_{1}$ 的左子節點 :
  • 現在來到了節點 $\alpha_{2}$. 根據尋訪順序, 我們前往節點 $\alpha_{2}$ 的左子節點 :
    • 現在來到節點 $\alpha_{4}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{4}$ 的左子節點, 但是節點 $\alpha_{4}$ 的左子節點為空; 然後, 我們存取元素, 此時的尋訪結果為 $\alpha_{4}$; 最後嘗試前往節點 $\alpha_{}$ 的右子節點, 發現右子節點也為空. 此時, 節點 $\alpha_{4}$ 尋訪完畢, 回到節點 $\alpha_{2}$.
  • 現在回到了節點 $\alpha_{2}$. 我們要存取節點中的元素, 此時的尋訪結果為 $\alpha_{4}$, $\alpha_{2}$. 然後嘗試前往節點 $\alpha_{2}$ 的右子節點 :
    • 現在來到了節點 $\alpha_{4}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{5}$ 的左子節點, 但是節點 $\alpha_{5}$ 的左子節點為空; 然後, 我們存取元素, 此時的結果為 $\alpha_{4}$, $\alpha_{2}$, $\alpha_{5}$; 最後嘗試前往節點 $\alpha_{5}$ 的右子節點, 發現右子節點也為空. 此時, 節點 $\alpha_{5}$ 尋訪完畢, 回到節點 $\alpha_{2}$.
  • 現在又回到了節點 $\alpha_{2}$, 由於節點 $\alpha_{2}$ 的左右子樹都已經尋訪, 因此回溯到節點 $\alpha_{1}$.
• 現在回到了節點 $\alpha_{1}$. 根據中序尋訪的順序, 存取元素, 此時的結果為 $\alpha_{4}$, $\alpha_{2}$, $\alpha_{5}$, $\alpha_{1}$. 最後根據尋訪順序, 我們前往節點 $\alpha_{1}$ 的右子節點 :
  • 現在來到了節點 $\alpha_{3}$. 根據尋訪換序, 我們前往節點 $\alpha_{3}$ 的左子節點 :
    • 現在來到節點 $\alpha_{6}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{6}$ 的左子節點, 但是節點 $\alpha_{6}$ 的左子節點為空; 然後, 我們存取元素, 此時的結果為 $\alpha_{4}$, $\alpha_{2}$, $\alpha_{5}$, $\alpha_{1}$, $\alpha_{6}$; 最後嘗試前往節點 $\alpha_{6}$ 的右子節點, 發現右子節點也為空. 此時, 節點 $\alpha_{6}$ 尋訪完畢, 回到節點 $\alpha_{3}$.
  • 現在回到了節點 $\alpha_{3}$. 存取節點 $\alpha_{3}$ 中的元素, 此時的結果為 $\alpha_{4}$, $\alpha_{2}$, $\alpha_{5}$, $\alpha_{1}$, $\alpha_{6}$, $\alpha_{3}$. 最後根據尋訪順序, 我們前往節點 $\alpha_{3}$ 的右子節點 :
    • 現在來到了節點 $\alpha_{7}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{7}$ 的左子節點, 但是節點 $\alpha_{7}$ 的左子節點為空; 然後, 我們存取元素, 此時的結果為 $\alpha_{3}$ 中的元素, 此時的結果為 $\alpha_{4}$, $\alpha_{2}$, $\alpha_{5}$, $\alpha_{1}$, $\alpha_{6}$, $\alpha_{3}$, $\alpha_{7}$; 最後嘗試前往節點 $\alpha_{7}$ 的右子節點, 發現右子節點也為空. 此時, 節點 $\alpha_{7}$ 尋訪完畢, 回到節點 $\alpha_{3}$.
  • 現在又回到了節點 $\alpha_{3}$. 由於節點 $\alpha_{3}$ 的左右子樹都已經尋訪, 因此回溯到節點 $\alpha_{1}$.
• 現在又回到了節點 $\alpha_{1}$. 由於節點 $\alpha_{1}$ 的左右子樹都已經尋訪, 因此嘗試回到節點 $\alpha_{1}$ 的父節點. 由於節點 $\alpha_{1}$ 沒有父節點, 代表著節點 $\alpha_{1}$ 就是這棵樹的根節點, 故尋訪完畢.

最終中序尋訪的結果為 $\alpha_{4}$, $\alpha_{2}$, $\alpha_{5}$, $\alpha_{1}$, $\alpha_{6}$, $\alpha_{3}$, $\alpha_{7}$.

$\square$

最後來看看後序尋訪 :

• 開始尋訪. 目前位於根節點. 根據後序尋訪的順序, 我們首先前往節點 $\alpha_{1}$ 的左子節點 :
  • 現在來到了節點 $\alpha_{2}$. 根據尋訪順序, 我們前往節點 $\alpha_{2}$ 的左子節點 :
    • 現在來到節點 $\alpha_{4}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{4}$ 的左子節點, 但是節點 $\alpha_{4}$ 的左子節點為空; 然後, 嘗試前往節點的右子節點 $\alpha_{4}$, 發現右子節點也為空; 最後我們存取節點 $\alpha_{4}$ 中的元素, 此時的尋訪結果為 $\alpha_{4}$. 此時, 節點 $\alpha_{4}$ 尋訪完畢, 回到節點 $\alpha_{2}$.
  • 現在回到了節點 $\alpha_{2}$. 根據尋訪的順序, 我們前往節點 $\alpha_{2}$ 的右子節點
    • 現在來到節點 $\alpha_{5}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{5}$ 的左子節點, 但是節點 $\alpha_{5}$ 的左子節點為空; 然後, 嘗試前往節點 $\alpha_{5}$ 的右子節點, 發現右子節點也為空; 最後我們存取元素, 此時的結果為 $\alpha_{4}$, $\alpha_{5}$. 此時, 節點 $\alpha_{5}$ 尋訪完畢, 回到節點 $\alpha_{2}$.
  • 現在又回到了節點 $\alpha_{2}$, 最後我們存取節點 $\alpha_{2}$ 的元素, 此時的結果為 $\alpha_{4}$, $\alpha_{5}$, $\alpha_{2}$. 節點 $\alpha_{2}$ 為根的子樹已經尋訪完畢了, 現在回到節點 $\alpha_{1}$.
• 現在回到了節點 $\alpha_{1}$. 根據後序尋訪的順序, 我們前往節點 $\alpha_{1}$ 的右子節點 :
  • 現在來到了節點 $\alpha_{3}$. 根據尋訪換序, 我們前往節點 $\alpha_{3}$ 的左子節點 :
    • 現在來到節點 $\alpha_{6}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{6}$ 的左子節點, 但是節點 $\alpha_{5}$ 的左子節點為空; 然後, 嘗試前往節點 $\alpha_{6}$ 的右子節點, 發現右子節點也為空; 最後我們存取元素, 此時的結果為 $\alpha_{4}$, $\alpha_{5}$, $\alpha_{2}$, $\alpha_{6}$. 此時, 節點 $\alpha_{6}$ 尋訪完畢, 回到節點 $\alpha_{3}$.
  • 現在回到了節點 $\alpha_{3}$. 根據尋訪的順序, 我們要前往節點 $\alpha_{3}$ 的右子節點 :
    • 現在來到節點 $\alpha_{7}$. 根據尋訪順序, 我們首先前往節點 $\alpha_{7}$ 的左子節點, 但是節點 $\alpha_{7}$ 的左子節點為空; 然後, 嘗試前往節點 $\alpha_{7}$ 的右子節點, 發現右子節點也為空; 最後我們存取元素, 此時的結果為 $\alpha_{4}$, $\alpha_{5}$, $\alpha_{2}$, $\alpha_{6}$, $\alpha_{7}$. 此時, 節點 $\alpha_{7}$ 尋訪完畢, 回到節點 $\alpha_{3}$.
  • 現在又回到了節點 $\alpha_{3}$. 最後我們存取節點 $\alpha_{3}$ 的元素, 此時的結果為 $\alpha_{4}$, $\alpha_{5}$, $\alpha_{2}$, $\alpha_{6}$, $\alpha_{7}$, $\alpha_{2}$. 節點 $\alpha_{3}$ 為根的子樹已經尋訪完畢了, 現在回到節點 $\alpha_{1}$.
• 現在又回到了節點 $\alpha_{1}$. 根據尋訪順序, 我們還要存取節點 $\alpha_{1}$ 中的元素. 此時的結果為 $\alpha_{4}$, $\alpha_{5}$, $\alpha_{2}$, $\alpha_{6}$, $\alpha_{7}$, $\alpha_{2}$, $\alpha_{1}$. 由於節點 $\alpha_{1}$ 的左右子樹都已經尋訪, 因此嘗試回到節點 $\alpha_{1}$ 的父節點. 由於節點 $\alpha_{1}$ 沒有父節點, 代表著節點 $\alpha_{1}$ 就是這棵樹的根節點, 故尋訪完畢.

最終後序尋訪的結果為 $\alpha_{4}$, $\alpha_{5}$, $\alpha_{2}$, $\alpha_{6}$, $\alpha_{7}$, $\alpha_{2}$, $\alpha_{1}$.

$\square$

綜上所述, 樹 $\mathcal {T}$ 的層次尋訪結果為 $\displaystyle {\alpha_{1}, \alpha_{2}, \alpha_{3}, \alpha_{4}, \alpha_{5}, \alpha_{6}, \alpha_{7}};$ 前序尋訪結果為 $\displaystyle {\alpha_{1}, \alpha_{2}, \alpha_{4}, \alpha_{5}, \alpha_{3}, \alpha_{6}, \alpha_{7}};$ 中序尋訪的結果為 $\displaystyle {\alpha_{4}, \alpha_{2}, \alpha_{5}, \alpha_{1}, \alpha_{6}, \alpha_{3}, \alpha_{7}};$ 後序尋訪的結果為 $\displaystyle {\alpha_{4}, \alpha_{5}, \alpha_{2}, \alpha_{6}, \alpha_{7}, \alpha_{2}, \alpha_{1}}.$

$\blacksquare$

5. 旋轉

二元樹可以以某個節點為基準, 進行左旋轉和右旋轉. 這是普通的樹無法做到的.

設 $n$ 是樹 $\mathcal {T}$ 的某個節點, $l$ 是 $n$ 的左子節點 (可以為空), $p$ 是 $n$ 的父節點. 以節點 $n$ 為基礎的左旋轉, 就是使用節點 $p$ 去替換原來 $l$, 然後將被擠出來的 $l$ 掛到 $p$ 的右子樹當中. 如果 $p$ 存在父節點 $\hat {p}$, 原來 $p$ 位於 $\hat {p}$ 哪一個子節點, 那麼就把旋轉之後以 $n$ 為根節點的子樹掛到 $\hat {p}$ 對應的子節點中; 如果 $p$ 本來是根節點, 那麼經過旋轉之後, $n$ 就變成了根節點.

從 Figure 5 中, 我們可以發現左旋轉看起來像以節點 $n$ 為中心, 節點 $p$ 隨著它自己和 $n$ 的連接線, 向左自然滑落一樣. 這便是左旋的名稱由來. 被擠掉的 $l$ 節點被重新安排至 $p$ 的右子節點, 因為 $p$ 的右子節點本來是 $n$, 滑落之後 $p$ 的右子節點總為空.

設 $n$ 是樹 $\mathcal {T}$ 的某個節點, $r$ 是 $n$ 的右子節點 (可以為空), $p$ 是 $n$ 的父節點. 以節點 $n$ 為基礎的右旋轉, 就是使用節點 $p$ 去替換原來 $r$, 然後將被擠出來的 $r$ 掛到 $p$ 的左子樹當中. 如果 $p$ 存在父節點 $\hat {p}$, 原來 $p$ 位於 $\hat {p}$ 哪一個子節點, 那麼就把旋轉之後以 $n$ 為根節點的子樹掛到 $\hat {p}$ 對應的子節點中; 如果 $p$ 本來是根節點, 那麼經過旋轉之後, $n$ 就變成了根節點.

從 Figure 6 中, 我們可以發現右旋轉看起來像以節點 $n$ 為中心, 節點 $p$ 隨著它自己和 $n$ 的連接線, 向右自然滑落一樣. 這便是右旋的名稱由來. 被擠掉的 $r$ 節點被重新安排至 $p$ 的左子節點, 因為 $p$ 的左子節點本來是 $n$, 滑落之後 $p$ 的左子節點總為空.

值得注意的是, 上面這兩種旋轉的角度都是不大於 $180^{\circ}$ 的. 而旋轉角度如果大於 $180^{\circ}$, 這樣的旋轉是不存在也是無效的, 也就是說

這兩種旋轉是錯誤的.

定理 1. 在對二元樹進行旋轉之後, 二元樹的中序尋訪結果不改變.

$證明$ :

首先證明二元樹在進行左旋轉之後, 中序尋訪結果不發生改變.

設 $p$ 是二元樹 $T$ 的某個非空節點, $c$ 為 $p$ 的非空右子節點, $l$ 為 $c$ 的左子節點. 記 $x$ 為存取 $p$ 節點元素之前產生的尋訪結果, $c_{l}$ 為節點 $c$ 的左子樹的尋訪結果, $y$ 為存取節點 $c$ 元素之後的尋訪結果, 旋轉過後的二元樹為 $T'$. 我們直接使用 $p$ 和 $c$ 來表示節點 $p$ 和 $c$ 中的元素. 那麼在進行左旋轉之前, 二元樹 $T$ 的中序尋訪結果為 $xpc_{l}cy$.

要證明二元樹在左旋轉之後中序尋訪順序不變, 只需要證明二元樹 $T$ 在左旋轉之後的中序尋訪結果仍然為 $xpc_{l}cy$.

若 $p$ 為二元樹 $T$ 的根節點, 在二元樹 $T$ 以節點 $c$ 為中心進行左旋轉之後, $c$ 將成為 $T'$ 的根節點. 根據中序尋訪的規則, 我們並不是直接存取 $c$ 中的元素, 而是首先前往 $c$ 的左子樹 $p$. 而左旋並沒有改變 $p$ 的左子樹, 因此在旋轉之後, $x$ 不改變. 根據中序尋訪的規則, 在存取 $p$ 中的元素之後, 目前的尋訪結果為 $xp$. 接下來要尋訪 $p$ 的右子樹. 在旋轉之後, $p$ 的右子樹發生了改變, 變成了以 $l$ 為根節點的子樹. 而 $c_{l}$ 是以 $l$ 為根節點的子樹的尋訪結果, 因此可以確定尋訪完 $l$ 之後, 現在的尋訪結果為 $xpc_{l}$. 現在 $c$ 的左子樹已經尋訪完畢, 要存取 $c$ 中的元素, 於是尋訪結果為 $xpc_{l}c$. 旋轉並不改變原本位於 $c$ 節點的右子樹, 於是 $y$ 便是以 $c$ 的右子節點為根節點的子樹的尋訪結果. 因此, 總體的尋訪結果為 $xpc_{l}cy$.

若 $p$ 不是二元樹 $T$ 的根節點, 我們已經證明了以 $p$ 為根節點的子樹經過旋轉, 變為 $c$ 為根節點之後, 子樹的尋訪順序不改變. 因此, 我們只需要考慮 $x$ 和 $y$ 是否改變即可. 對於 $c$ 的左子樹位於 $x$ 的部分和 $p$ 的右子樹位於 $y$ 的部分, 我們可以由上面的分析可知這兩個部分的尋訪結果不改變. 而左旋只改變了原本以 $p$ 為根節點的子樹, 其餘部分的節點順序並未改變, 因此尋訪結果也不改變. 因此, 尋訪完畢之後的結果仍然為 $xpc_{l}cy$.

所以在二元樹進行左旋轉之後, 中序尋訪的結果不發生改變.

$\square$

接下來證明二元樹進行右旋轉之後, 中序尋訪的結果仍然不發生改變.

設 $p$ 是二元樹 $T$ 的某個非空節點, $c$ 為 $p$ 的非空左子節點, $l$ 為 $c$ 的右子節點. 記 $x$ 為存取 $c$ 節點元素之前產生的尋訪結果, $y$ 為存取 $c$ 節點元素之後產生的尋訪結果, $c_{r}$ 為節點 $c$ 的右子樹的尋訪結果, 旋轉過後的二元樹為 $T'$. 我們直接使用 $p$ 和 $c$ 來表示節點 $p$ 和 $c$ 中的元素. 那麼在進行左旋轉之前, 二元樹 $T$ 的中序尋訪結果為 $xcc_{r}py$.

要證明二元樹在左旋轉之後中序尋訪順序不變, 只需要證明二元樹 $T$ 在右旋轉之後的中序尋訪結果仍然為 $xcc_{r}py$.

若 $p$ 為二元樹 $T$ 的根節點, 在二元樹 $T$ 以節點 $c$ 為中心進行右旋轉之後, $c$ 將成為 $T'$ 的根節點. 根據中序尋訪的規則, 我們並不是直接存取 $c$ 中的元素, 而是首先前往 $c$ 的左子樹 $p$. 而左子樹 $p$ 的尋訪結果即是旋轉之前 $c$ 的左子樹的尋訪結果. 旋轉並沒有改變本來位於 $c$ 左子樹中的節點順序, 因此 $x$ 不變, 於是現在的尋訪結果為 $x$. 根據中序尋訪的順序, 接下來要存取 $c$ 節點中的元素, 於是尋訪結果為 $xc$. 然後要尋訪 $c$ 的右子樹. 由於旋轉之後, $p$ 成為了 $c$ 的右子樹, 因此需要首先尋訪 $p$ 的左子樹. 而 $r$ 被放置在了 $p$ 的左子節點中, 旋轉並沒有改變以 $r$ 為根節點的子樹的順序, 因此 $c_{r}$ 不發生改變. 於是, 現在的尋訪結果為 $xcc_{r}$. 接下來要存取 $p$ 節點中的元素, 尋訪結果會變為 $xcc_{r}p$. 之後就會尋訪 $p$ 的右子節點, 而旋轉也沒有改變其右子樹的順序, 因此尋訪完畢之後結果為 $xcc_{r}py$.

若 $p$ 不是二元樹 $T$ 的根節點. 我們已經證明了以 $p$ 為根節點的子樹經過旋轉, 變為 $c$ 為根節點之後, 子樹的尋訪順序不改變. 因此, 我們只需要考慮 $x$ 和 $y$ 是否改變即可. 對於 $c$ 的左子樹位於 $x$ 的部分和 $p$ 的右子樹位於 $y$ 的部分, 我們可以由上面的分析可知這兩個部分的尋訪結果不改變. 而右旋只改變了原本以 $p$ 為根節點的子樹, 其餘部分的節點順序並未改變, 因此尋訪結果也不改變. 因此, 尋訪完畢之後的結果仍然為 $xcc_{r}py$.

所以在二元樹進行右旋轉之後, 中序尋訪的結果不發生改變.

$\square$

綜上所述, 在對二元樹進行旋轉之後, 二元樹的中序尋訪結果不改變.

$\blacksquare$

6. 實作

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