高效率的二元搜尋樹 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 的概念

Elevator Scheduling (1)

下午去吃飯回來搭電梯時,因為電梯剛好在二樓,我就直接按鈕進去了

當我到了六樓,一出來就發現有人在等電梯,我突發奇想,思考一個可能性,就是會不會他們其實剛好正要按電梯按鈕,但是就只是差那麼個幾秒鐘,導致我先搶到電梯了?

那麼假如今天剛好相反過來,我慢了一點,電梯明明在二樓,我就只能眼睜睜看著它先到六樓再下來載我嗎?

我開始思考延遲電梯反應時間的可能性

讓可能只是誤差非常小的時間範圍內,可以讓慢了一點的我還是可以先搭到電梯,然後到了六樓以後再換六樓的人搭下來,結果光是在Word上邊寫邊想就花了我兩個小時左右的時間,以下是我的思考結果,之前在圖書館搭電梯就曾經對三部電梯的調度提過問題,可惜當時沒有那麼無聊好好思考和紀錄,現在就可以當參考了

有聽過電梯演算法 (Elevator Algorithm),還有個有名的人物 Theresa Christy,會不會其實這個問題早就克服了呢?

情境:目前電梯正位於1F,當一位使用者正準備按下電梯向上按鈕進入電梯,由於6F亦有乘客愈搭乘電梯下樓,假設兩造於相差半秒內的時間按下電梯按鈕,事實是6F乘客較晚按下按鈕,則電梯可能因為反應時間快速,使得收到6F訊號以後立即向上,1F乘客需等待6F使用者下樓以後方可上樓

相關數據假設:
按鈕時間差 0.5 sec
電梯反應時間 0.1 sec (電梯接收到按鈕訊號並判斷該打開門讓1F乘客進入或是上樓的處理時間)
電梯自 1F  6F運行時間 15 sec
電梯門開門或關門時間 2 sec
乘客進或出電梯時間(在此假設兩樓層各只有一位乘客,且在進入電梯後立刻按下樓層按鈕) 2 sec
1F乘客 P1
6F 乘客 P6
電梯完成運送兩位乘客抵達愈前往樓層總耗時
= 第一位乘客按下按鈕 至 送最後一位乘客抵達樓層並開啟門使其離開
= 電梯反應時間 + 電梯總運行時間 + 電梯開關門總時間 + 乘客進出電梯時間
= 0.1 + 15 x 3 (上樓2次,下樓1次) +  2 x 5 (*1) + 2 x 4 (兩位乘客各進與出1次) 
= 63.1 sec
乘客等待時間(從乘客按下按鈕開始至乘客抵達愈前往樓層*2):
P1 等待時間
= 電梯運行至6F + 電梯於6F開關門總時間 + P6進出總時間 + 電梯運行至1F + P1進出總時間 + 電梯於1F開關門總時間 + 電梯運行至6F + 電梯於6F 開門時間 (*3)
= (15 – 0.4 (*4))+ 2 x 2 (開關各一次) + 2 x 2 (6F進,1F出) + 15 + 2 x 2 (1F進,6F出) + 2 x 2 (開關各一次) + 15 + 2
= 62.6 sec
P6等待時間
= 電梯反應時間 + 電梯運行至6F時間 + 電梯於6F開關門總時間 + P6進出總時間 + 電梯運行至1F + 電梯於1F開門時間
= 0.1 + 15 + 2 x 2 + 2 x 2+ 15 + 2
= 40.1 sec
平均等待時間 = (63 + 40.1) ÷ 2 = 51.55 sec
改善想法:由以上討論可發現,電梯反應時間對於一位乘客的等待時間影響並不是很大,所以假如增加電梯反應時間至1 sec,企圖使電梯可在較慢的乘客也按下電梯按鈕以後,再做出判斷(因為較慢的乘客會是在0.5sec時按下按鈕,電梯則是在1sec時完成判斷),如此一來,便可以於第一次由1F運行至6F時服務1F乘客抵達6F
改善後電梯完成運送兩位乘客抵達愈前往樓層總耗時
= 第一位乘客按下按鈕 至 送最後一位乘客抵達樓層並開啟門使其離開
= 電梯反應時間 + 電梯總運行時間 + 電梯開關門總時間 + 乘客進出電梯時間
= 1 + 15 x 2 (上下樓各1次) +  2 x 5 (*5) + 2 x 4 (兩位乘客各進與出1次) 
= 49 sec
乘客等待時間(從乘客按下按鈕開始至乘客抵達愈前往樓層):
P1 等待時間
= 電梯反應時間(*6) + 電梯於1F開關門總時間 + P1進出總時間 + 電梯運行至 6F時間 + 電梯於 6F 開門時間
= 0.5 + 2 x 2 + 2 x 2 + 15 + 2
= 25.5 sec
P6等待時間
= 電梯反應時間 + 電梯於1F開關門總時間 + P1進出總時間 + 電梯運行至 6F 時間 + 電梯於6F 開關門時間 + P6 進出總時間 + 電梯運行至1F 時間 + 電梯於 1F 開門時間
= 1 + 2 x 2 + 2 x 2 + 15 + 2 x 2 + 2 x 2 + 15 + 2
= 49 sec
改善後平均等待時間 = (25.5 + 49) ÷ 2 = 37.25 sec
 ———————————————————————————————————— 
*1  第一次抵達6F,開與關各一次,接著抵達1F,開與關各一次,第二次抵達6F,僅計算開門時間,故計一次,所以總共是5次
*2 與作業系統討論的不同,這裡的討論包含了運送乘客時間(CPU Turnaround Time)      
*3 P1因為較慢按下按鈕,此時電梯已經完成反應,因此P1無須等待電梯反應時間       
*4 電梯開始移動是第一個乘客按下之後的0.1秒,從這0.1秒到第二位乘客按下按鈕間的0.4秒,電梯已經移動了一段時間,所以要從電梯運行至6F的15秒鐘扣掉這0.4秒
*5 因為電梯會判斷成應該先在1F開門載客,所以於1F開與關各一次,抵達6F開與關各一次,第二次回到1F時開門一次
*6 對於P1而言,他按下按鈕的時間是電梯反應時間開始之後過了0.5秒,因此實際上他的等待時間只有0.5秒