#binary-search-tree

Stanford CS161 Lecture 7：二元搜尋樹、紅黑樹與最壞 O(log n) 的來源

一般 BST 的操作成本是 O(h)，偏斜時會退化成 O(n)；紅黑樹用五條顏色不變量把高度限制在 2 log₂(n+1)，因此搜尋、插入與刪除都有最壞 O(log n) 保證。