1. 首頁 > 生活經驗 > >

紅黑樹和平衡二叉樹的區別

生活百科平衡

紅黑樹放棄了追求完全平衡，追求大致平衡 ， 在與平衡二叉樹的時間復雜度相差不大的情況下，保證每次插入最多只需要三次旋轉就能達到平衡，實現起來也更為簡單 。
平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩 ， 每次插入新節點之后需要旋轉的次數不能預知 。
【紅黑樹和平衡二叉樹的區別】紅黑樹：是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構 ， 典型的用途是實現關聯數組 。紅黑樹是在１９７２年被發明，當時被稱為平衡二叉Ｂ樹 。紅黑樹是一種特化的ＡＶＬ樹（平衡二叉樹），都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能 。它雖然是復雜的，但它的最壞情況運行時間也是非常良好的 ， 并且在實踐中是高效的： 它可以在Ｏ時間內做查找，插入和刪除，這里的ｎ 是樹中元素的數目 。