[筆記] Master The Coding Interview – 15

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Tree」關於樹的第三部分簡介。

---

課程相關資訊

[連結]：https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/

課程對應章節：130~134

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

---

範例程式碼

https://repl.it/@andy922200/Data-Structures-Trees-exercise

AVL Trees

AVL Trees是屬於Binary Search Trees的一種，所以會具有 BST 的特性外，額外有個「每一 node 的左子樹高度-右子樹高度只能是-1、0、1」的特徵。由於整個樹不會長歪(也就是太偏某一邊)，在搜尋時的速度會更快。

Red Black Trees

紅黑樹，利用節點顏色來檢視二元樹每條延展的路徑高度是否差不多。具有「最長路徑不會超過最短路徑的兩倍」的性質。

---

參考資料

1. [資料結構] CH8. AVL Trees
2. Red-Black Tree / 紅黑樹

相關文章

按讚加入粉絲團

延伸閱讀

• [筆記] TypeScript 之 enum 生成其所有 value 的集合
• [筆記] 程式必修課！離散數學與演算法 – 142
• [筆記] 程式必修課！離散數學與演算法 – 141
• [筆記] 程式必修課！離散數學與演算法 – 140
• [筆記] 程式必修課！離散數學與演算法 – 138