小結

重點回顧

• 二元樹是一種非線性資料結構，體現“一分為二”的分治邏輯。每個二元樹節點包含一個值以及兩個指標，分別指向其左子節點和右子節點。
• 對於二元樹中的某個節點，其左（右）子節點及其以下形成的樹被稱為該節點的左（右）子樹。
• 二元樹的相關術語包括根節點、葉節點、層、度、邊、高度和深度等。
• 二元樹的初始化、節點插入和節點刪除操作與鏈結串列操作方法類似。
• 常見的二元樹型別有完美二元樹、完全二元樹、完滿二元樹和平衡二元樹。完美二元樹是最理想的狀態，而鏈結串列是退化後的最差狀態。
• 二元樹可以用陣列表示，方法是將節點值和空位按層序走訪順序排列，並根據父節點與子節點之間的索引對映關係來實現指標。
• 二元樹的層序走訪是一種廣度優先搜尋方法，它體現了“一圈一圈向外擴展”的逐層走訪方式，通常透過佇列來實現。
• 前序、中序、後序走訪皆屬於深度優先搜尋，它們體現了“先走到盡頭，再回溯繼續”的走訪方式，通常使用遞迴來實現。
• 二元搜尋樹是一種高效的元素查詢資料結構，其查詢、插入和刪除操作的時間複雜度均為 \(O(\log n)\) 。當二元搜尋樹退化為鏈結串列時，各項時間複雜度會劣化至 \(O(n)\) 。
• AVL 樹，也稱平衡二元搜尋樹，它透過旋轉操作確保在不斷插入和刪除節點後樹仍然保持平衡。
• AVL 樹的旋轉操作包括右旋、左旋、先右旋再左旋、先左旋再右旋。在插入或刪除節點後，AVL 樹會從底向頂執行旋轉操作，使樹重新恢復平衡。

Q & A

Q：對於只有一個節點的二元樹，樹的高度和根節點的深度都是 \(0\) 嗎？

是的，因為高度和深度通常定義為“經過的邊的數量”。

Q：二元樹中的插入與刪除一般由一套操作配合完成，這裡的“一套操作”指什麼呢？可以理解為資源的子節點的資源釋放嗎？

拿二元搜尋樹來舉例，刪除節點操作要分三種情況處理，其中每種情況都需要進行多個步驟的節點操作。

Q：為什麼 DFS 走訪二元樹有前、中、後三種順序，分別有什麼用呢？

與順序和逆序走訪陣列類似，前序、中序、後序走訪是三種二元樹走訪方法，我們可以使用它們得到一個特定順序的走訪結果。例如在二元搜尋樹中，由於節點大小滿足 左子節點值 < 根節點值 < 右子節點值 ，因此我們只要按照“左 \(\rightarrow\) 根 \(\rightarrow\) 右”的優先順序走訪樹，就可以獲得有序的節點序列。

Q：右旋操作是處理失衡節點 node、child、grand_child 之間的關係，那 node 的父節點和 node 原來的連線不需要維護嗎？右旋操作後豈不是斷掉了？

我們需要從遞迴的視角來看這個問題。右旋操作 right_rotate(root) 傳入的是子樹的根節點，最終 return child 返回旋轉之後的子樹的根節點。子樹的根節點和其父節點的連線是在該函式返回後完成的，不屬於右旋操作的維護範圍。

Q：在 C++ 中，函式被劃分到 private 和 public 中，這方面有什麼考量嗎？為什麼要將 height() 函式和 updateHeight() 函式分別放在 public 和 private 中呢？

主要看方法的使用範圍，如果方法只在類別內部使用，那麼就設計為 private 。例如，使用者單獨呼叫 updateHeight() 是沒有意義的，它只是插入、刪除操作中的一步。而 height() 是訪問節點高度，類似於 vector.size() ，因此設定成 public 以便使用。

Q：如何從一組輸入資料構建一棵二元搜尋樹？根節點的選擇是不是很重要？

是的，構建樹的方法已在二元搜尋樹程式碼中的 build_tree() 方法中給出。至於根節點的選擇，我們通常會將輸入資料排序，然後將中點元素作為根節點，再遞迴地構建左右子樹。這樣做可以最大程度保證樹的平衡性。

Q：在 Java 中，字串對比是否一定要用 equals() 方法？

在 Java 中，對於基本資料型別，== 用於對比兩個變數的值是否相等。對於引用型別，兩種符號的工作原理是不同的。

• == ：用來比較兩個變數是否指向同一個物件，即它們在記憶體中的位置是否相同。
• equals()：用來對比兩個物件的值是否相等。

因此，如果要對比值，我們應該使用 equals() 。然而，透過 String a = "hi"; String b = "hi"; 初始化的字串都儲存在字串常數池中，它們指向同一個物件，因此也可以用 a == b 來比較兩個字串的內容。

Q：廣度優先走訪到最底層之前，佇列中的節點數量是 \(2^h\) 嗎？

是的，例如高度 \(h = 2\) 的滿二元樹，其節點總數 \(n = 7\) ，則底層節點數量 \(4 = 2^h = (n + 1) / 2\) 。