章節連結
重念一次早該補起來的「資料結構與演算法」。這篇筆記下自我平衡樹。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/146354
本篇範圍：Chapter 14
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. 當樹不平衡的話，那時間複雜度就會由 O ( logN ) -> O( n ) 靠近
2. 解決方法有 3 種：B-Tree & B+ Tree, AVL Tree 和 Red-Black Tree
M-Way Search Tree
1. 每一個 node 有 M 個 children ( 也就是有 m 條連結 )，同時有 m-1 個 key
2. 每個 node 內，一樣需符合較小的值在左，較大的值在右
B-Tree
1. 它是一種特規的 M-Way Tree
2. 每一個節點，最多有 m 個 children
3. root 一定至少要有兩個 children
4. 除了 root 節點外，至少要有 [ m/2 ] 無條件進位到最近整數個 children
5. 所有的 leave 都會是同一層
某一個塞爆，就會往上抬一層
