6.Data Structures: Trees 學習筆記
學習資料來源: Master the Coding Interview: Data Structures + Algorithms
【Binary Trees】
特性
1.每個父節點有0、1或2個子節點。
2.每個子節點只有一個父節點。
3.Perfect Binary Trees有兩個特點:
(1)每個子層以2的n次方增加、(2)最底層數量是其餘層數量加總後+1。
【Binary Search Trees】
優點 (適合用來Search)
1.比O(n)佳
2.資料經過排序(sorted)
3.長度彈性
缺點
1.無O(1)操作,最佳O(log n)
特性
1.右邊的子節點會比目前節點大,左邊的子節點會比目前節點小。
2.Balanced BST: O(log n) vs Unbalanced BST: O(n)。
=> 處理Unbalanced BST方法: AVL Trees + Red Black Trees
【用JS實作 Binary Search Trees】
【Heaps】-【Binary Heaps】
lookup: O(n)、insert: O(log n)、delete: O(log n)
優點
1.呈現優先順序
2.快速新增
缺點
1.尋找特定項目較慢
特性
1.max heap: 每個父層比子層大,min heap: 每個父層比子層小,一般用於尋找最大/最小值
2.父層與子層間有比較規律,但左邊不一定都比右邊的分支小。(lookup較Binary Search Trees慢)
3.從左至右將Tree填滿,若子層比父層大則bubble-up。(insert較快,Best O(1); Worst O(log n))
4.沒有unbalanced binary heap的狀況
回到筆記列表,文章中的內容如果有誤,歡迎提醒告知,謝謝!