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的狀況

回到筆記列表，文章中的內容如果有誤，歡迎提醒告知，謝謝!