資料結構與算法分析第四章

第四章講的是樹這種結構，這種結構的大部分操作的運作時間平均為logN，其中重點是二叉搜尋樹（代碼實作）。本章的主要内容：

• 了解樹是如何實作檔案系統的
• 樹如何來計算表達式的值
• 如何利用樹支援一O（logN）平均時間進行的各種搜尋操作，以及如何細化到最壞情況下時間界O（logN）的。

簡單介紹一下樹這種資料結構，樹這種結構可以聯想到家譜，一層一層的向下傳遞，樹的一些屬性：

• 一棵樹的最上層的一個節點為根（root）
• 一個節點與下一層節點相連，則這個節點稱作下一層相連節點的父節點（parent）
• 除去根節點外，每個節點都有一個父節點
• 具有同一個父節點的一組節點互稱兄弟節點（brother）
• 沒有兒子的節點稱為樹葉（leaf）
• 一個節點的深度（depth）為從根節點到該節點的唯一路徑長，是以根的深度為0
• 一個節點的高（height）為該節點到一個樹葉最長路徑，是以樹葉的高為0
• 一棵樹的深度為最深的樹葉的深度

一些特殊的樹：

• 二叉查找樹√
• AVL樹√
• 伸展樹？
• B-樹（非二叉的查找樹）

我們使用二叉樹的原因是希望它的大部分操作消耗平均能在logN，但是有些情況（這些情況很常見），比如删除操作，會使得二叉樹左子樹比右子樹深度深得多，原因在于上述的删除算法有助于左子樹比右子樹深，那樣的話二叉樹的深度就不能保持在logN左右，這樣的樹是不平衡的，是以我們用AVL樹來填補這種不平衡；

AVL樹是帶有平衡條件的樹，也就是說，在檢測到左右子樹深度相差大于1時，會自動平衡各個節點來使得樹保持平衡，這樣我們可以保持大部分操作的平均消耗在logN