為什么需要紅黑樹？
由于AVL樹是以增加、刪除節(jié)點(diǎn)來(lái)保證樹的基本平衡，從而保證查詢效率在O(logN)左右。
紅黑樹就是在不犧牲太大的增加、刪除操作的代價(jià)，而且也能保證穩(wěn)定高效的查找效率。
紅黑樹的特性
紅黑樹
- 每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色
- 根節(jié)點(diǎn)是黑色
- 每個(gè)葉子節(jié)點(diǎn)（null）是黑色
- 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
- 沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)兩倍(雖然不是AVL中高度差不能超過(guò)為2的嚴(yán)格平衡)
紅黑樹查找性能
- 查找性能：基本維持在O(logN)，但是最差的情況是最短路徑的兩倍減一，所以要比AVL樹差一點(diǎn)。
- 插入性能：需要至多兩次旋轉(zhuǎn)和變色，也為O(logN)
- 刪除性能：刪除性能要比AVL樹好很多，至多進(jìn)行三次旋轉(zhuǎn)操作。而不用像AVL樹檢查每一層的平衡因子可能涉及到多次旋轉(zhuǎn)，所以刪除性能要比AVL樹好很多。
