高效率二元搜尋樹

觀念

  • 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 的設計邏輯很相近,因此被用來設計這些應用的演算法

小筆記

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

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s