[低端筆記] MIT算法導論 6. AVL Trees, AVL Sort

MIT的算法導論公開課有兩種版本, 我選較新版的
MIT 6.006 Introduction to Algorithms, Fall 2011

官方筆記

Typed notes (PDF - 1.4MB)

複習: Binary Search Trees (BSTs)

• rooted binary tree
• each node has
• key
• left pointer
• right pointer
• parent pointer
• BST property
• 左子樹 ≤ 根
• 右子樹 ≥ 根
• BSTs support insert, delete, min, max in O(h) time
• h 為樹高(height of a tree) = 從根到葉的最長路徑
• h 在平衡時為 lg n

*height of a node
 = 該點到葉的最長路徑
 = Max{height(left child), height(right child)} + 1

Heights of nodes in a BST

AVL Trees

任意節點的左右子樹高度差最多為 |1|
( | Hl - Hr | ≤ 1 )

• nil 設為 -1
• 每個節點都會儲存其樹高資訊

AVL Tree

AVL Trees are Balanced

Worst case: 任意節點的 Hl 都比 Hr 少 1
Nh = (min.)  # nodes in height-h AVL tree
Nh = Nh-1 + Nh-2 + 1  //右子+左子+自己
Nh > Fh = φh/√5          //Fh = Fh-1 + Fh-2
φ = 1.618~
h < logφ n = 1.440 lg n

AVL Insert

#Fix

1. suppose x is the lowest node violating AVL
2. assume x is right-heavy (left case symmetric)
• if x's right child is right-heavy or balanced

• else:

#旋轉

#Example