平衡二叉樹: 維持左右子樹平衡
平衡因子(左右子樹高度差)絕對值小于1,若超過就會進行左/右旋來保持平衡,比較耗時,因此在頻繁插入刪除的場景不適用,適用于查詢多的場景
紅黑樹: 維持左右子樹大致平衡
- 根節(jié)點是黑的;
- 每個節(jié)點非紅即黑
- 每個葉節(jié)點(葉節(jié)點即樹尾端NULL指針或NULL節(jié)點)都是黑的;
- 如圖所示脱羡,如果一個節(jié)點是紅的,那么它的兩兒子都是黑的;
- 對于任意節(jié)點而言,其到葉子點樹NULL指針的每條路徑都包含相同數(shù)目的黑節(jié)點;
文獻:
https://blog.csdn.net/u010899985/article/details/80981053