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

AVL tree 的不平衡狀況

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

調整方式

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

加入子樹

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

發表迴響

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

WordPress.com 標誌

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

Google photo

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

Twitter picture

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

Facebook照片

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

連結到 %s