注意事項
- 本節(jié)要“不求甚解”龟劲，掌握結果梢薪，不糾細節(jié)
- 你將體會計算機科學的精妙與偉大
性能，性能宇姚，還是性能
- 數(shù)組：查找快O(1)匈庭，增刪慢O(n)
- 鏈表：查找慢O(n)，增刪快O(1)
- 二叉搜索樹BST：查找快浑劳，增刪快 - “木桶效應”
二叉搜索樹BST可以通過二分查找快速搜索結果
平衡二叉樹
- BST如果不平衡阱持，那就又成了鏈表了
- 所以要盡量平衡：平衡二叉搜索樹BBST
- BBST增刪查，時間復雜度都是 O(logn)魔熏，即樹的高度
二叉查找樹其性能在某些特殊情況可能降級到 O(n)衷咽。比如樹不平衡鸽扁，一側有非常多節(jié)點，而另一側幾乎沒有镶骗，則其性能會退化桶现，導致后續(xù)操作都非常低效。所以卖词，構建一個平衡的二叉樹是高效處理數(shù)據(jù)的前提巩那。平衡的二叉查找樹，它能自動保持平衡狀態(tài)此蜈。這種平衡的二叉查找樹稱為AVL 樹即横，名字來源于其發(fā)明人：G.M. Adelson-Velskii 和E.M.Land。
紅黑樹
- 一種自平衡二叉樹
- 分為 紅/黑 兩種顏色裆赵，通過顏色轉換來維持樹的平衡
- 相對于普通平衡二叉樹东囚，它的維持平衡的效率更高
紅黑樹是一種特化的AVL樹（平衡二叉樹），都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡战授，從而獲得較高的查找性能页藻。它雖然是復雜的，但它的最壞情況運行時間也是非常良好的植兰，并且在實踐中是高效的： 它可以在O(log n)時間內做查找份帐，插入和刪除，這里的n 是樹中元素的數(shù)目楣导。
B樹
- 物理上是多叉樹废境，但邏輯上是二叉樹
- 一般用于高效I/O，關系型數(shù)據(jù)庫常用B樹來組織數(shù)據(jù)
B樹和平衡二叉樹稍有不同的是B樹屬于多叉樹又名平衡多路查找樹（查找路徑不只兩個）筒繁，數(shù)據(jù)庫索引技術里大量使用者B樹和B+樹的數(shù)據(jù)結構噩凹。
小結
- 數(shù)組、鏈表毡咏，各有各的缺點
- 特定的二叉樹（BBST）可以讓整體效果最優(yōu)
- 各種高級二叉樹驮宴，繼續(xù)優(yōu)化，滿足不同場景
