1樓：answer
去看algorithms, 4th edition, 肯定比我們這些人講的都清楚。不過我想了想紅黑樹為什麼能實現平衡的原因：
普通的二叉搜尋樹的高度受node插入順序的影響，在最壞的情況下，即所有的node按key值由大到小或由小到大依次插入，n個node組成的二叉搜尋樹的高度會是n。
紅黑樹想了一種辦法，通過a.允許3節點的存在; b.旋轉操作，使得key值處在中間的節點會被調整到中間來，比如，key值分別為a, f, k，為f的那個節點會通過紅黑樹被調整為a和f的父節點或更靠近root，在a和f的中間，不論插入順序如何，這樣樹就更平衡。
2樓：「已登出」
到這裡找
3樓：
這個問題很不錯。
紅黑樹就是一種以二叉樹形式實現了2-3-4樹的想法。
因此紅黑樹的各種操作其實是對應到2-3-4樹的相應操作的。
而2-3-4樹是平衡樹，所以紅黑樹的樣子也就差不多算平衡樹了。
ps：具體來說，紅黑樹其實就3類節點，分別是一黑，一黑一紅，一黑二紅。就是用來對應二，三，四節點的。其他細節的話還是看wiki吧。
pps：如果要問2-3-4樹怎麼來的amp;*
4樓：理查德帕克
授人以魚，不如授之以漁，何況自己都忘了，建議去看sedgewick的《演算法》第四版平衡搜尋樹和紅黑樹部分，講得非常清晰。
為什麼說「滿二叉樹也是完全二叉樹」？
一名 1 先明確完全二叉樹的概念。先上圖！完全二叉樹分為樓主所說的 圖1就是了 還有一種完全二叉樹是圖2。圖2也是完全二叉樹！圖2也是完全二叉樹！圖2也是完全二叉樹！概念 完全二叉樹分為兩種，1 最後一層沒有滿，那麼最後一層的節點都得在左邊。2 最後一層滿了，那就得全滿才行，圖2。完全二叉樹就這麼個...
2021 04 11 判斷二叉樹是否是完全二叉樹？
一鯨 const completeSize node node const sl completeSize left if sl 0 return 1 const sr completeSize right if sr 0 return 1 const fl sl 1 sl const fr sr ...
二叉樹可以是monad嗎？
dreday 其實list也可以不是concat，也可以concat後reverse，這樣做就出現另乙個monad了。head就比較奇怪了，如果bind返回是空的話就報錯了。我的理解是，不是二叉樹是不是monad，而是二叉樹實現了bind，fmap這兩個方法後二叉樹就是monad了。monad其實是...