高效率的二元搜尋樹 1 – AVL Tree

AVL tree 的不平衡狀況

一節點的 左子樹 與 右子樹 高度差絕對值 > 1

調整方式

其實也不必特意去記什麼 LL, LR, RL 或 RR 型的歪斜,記得 BST 是 inorder (先看左子在看右子),所以只要把 AVL 歪斜的那棵子樹在 inorder 中是中子的 node 拉上來變 parent 就好了

加入子樹

  1. BST 都是先從 root 開始比較,比 root 大往右,比 root 小往左,依此類推
  2. 加入完畢後,再依序往回調整平衡

高效率二元搜尋樹

觀念

  • AVL tree
  • Red-black tree
  • Splay tree

都是為了解決『二元搜尋樹過度歪斜導致搜尋時間太久』的問題,所以 Horowitzh 的 Foundamentals of Data Structures in C 才會有將這三種樹專章放在『Efficient Binary Search Trees

所以重點:

  1. 這三種樹都是 Binary Search Tree
  2. 目的是要解決 BST 過度歪斜導致搜尋時間太久的問題

Application

  • AVL tree
    網路上查不太到什麼直接的用途,但是他的變種 2-3 tree 有
  • Red-black tree
    紅黑樹相對於AVL樹來說,犧牲了部分平衡性以換取插入/刪除操作時少量的旋轉操作,整體來說效能要優於AVL樹 The process scheduler in Linux uses Red Black Trees (Completely Fair Scheduler in Linux Kernel).
  • Splay Tree
    為了使整個查找時間更小,被查頻率高的那些條目就應當經常處於靠近樹根的位置,於是想到設計一個簡單方法, 在每次查找之後對樹進行重構,把被查找的條目搬移到離樹根近一些的地方 這個性質與 cache 和 garbage collection 的設計邏輯很相近,因此被用來設計這些應用的演算法

小筆記

計算機科學很多時候是把人類生活的現象抽象化成運算邏輯,因此很多時候再思考怎麼應用時都需要聯想力

More Heap

今天在看意春木的 軟韌體工程師面試- C語言與OS作業系統 常見題目(筆試考題),讀到有關描述 heap 概念的一段話:

heap:
台灣正體中文稱為堆積,大陸叫做堆。
不可預測的因素造成上述的stack區塊不適合運用。
所以當資訊為動態配置產生,系統會存放在另外一塊空間,稱之為『Heap』
(注意這裡的Heap跟資料結構中的Heap不相關,可別會錯意!)。

其中令我疑惑的是最後這句括號中的補充,因此做了些研究,先是複習了一下資料結構中的 heap,最常見也基本的三個重點:

  1. 是一種樹狀結構
    => 不懂為什麼,因為堆疊錐形金字塔像是一顆樹狀結構?
  2. 最常以 array 實作
    => 我覺得這個原因是,當不同 level 的元素(child and parent)要做比較和交換時,會比 linked list 要方便及快速
  3. 最常被拿來實作 priority queue
    => 因為當一個物件要進入這個 priority queue 時,一定是從 queue 的最尾端 (堆積樹的最右下一個位置) 插入,然後才進行優先權檢查看應該調整到哪個位置 (不可能一來就排在最先或最後,那就沒有 priority 了),而 head 的調整原理很符合這個規則需求

然後我搜尋了一下關鍵字heap in memory data structure,找到的第一個結果是 stackoverflow 的提問,就是在討論『C 執行時期記憶體配置中的 heap 與資料結構中討論的 heap 有什麼不同』,原文連結:http://stackoverflow.com/questions/1699057/why-are-two-different-concepts-both-called-heap

票選最高的一個解答為:

Donald Knuth says (The Art of Computer Programming, Third Ed., Vol. 1, p. 435):

==Several authors began about 1975 to call the pool of available memory a “heap."==

He doesn’t say which authors and doesn’t give references to any specific papers, but does say that the use of the term “heap" in relation to priority queues is the traditional sense of the word.

下面的留言和解答也有一些支持用 pool 來稱呼 memory pool 的概念