紅黑樹简珠，平衡二叉查找樹燕差，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是 Red 或 Black咬腕。
通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍葬荷，因而是接近平衡的涨共。
紅黑樹，作為一棵二叉查找樹宠漩，滿足二叉查找樹的一般性質(zhì)举反。
二叉查找樹
也稱有序二叉樹（ordered binary tree），或已排序二叉樹（sorted binary tree）扒吁，是指一棵空樹或者具有下列性質(zhì)的二叉樹：
- 若任意節(jié)點的左子樹不空火鼻，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
- 若任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值魁索；
- 任意節(jié)點的左融撞、右子樹也分別為二叉查找樹。
- 沒有鍵值相等的節(jié)點（no duplicate nodes）粗蔚。
因為一棵由 n 個結(jié)點隨機構(gòu)造的二叉查找樹的高度為 log(n)尝偎，所以順理成章，二叉查找樹的一般操作的執(zhí)行時間為O(log(n))鹏控。但二叉查找樹若退化成了一棵具有 n 個結(jié)點的線性鏈后冬念，則這些操作最壞情況運行時間為O(n)。
紅黑樹雖然本質(zhì)上是一棵二叉查找樹牧挣，但它在二叉查找樹的基礎(chǔ)上增加了著色和相關(guān)的性質(zhì)使得紅黑樹相對平衡，從而保證了紅黑樹的查找醒陆、插入瀑构、刪除的時間復雜度最壞為O(log(n))。
平衡二叉查找樹
它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過 1刨摩，并且左右兩個子樹都是一棵平衡二叉查找樹寺晌。平衡二叉搜索樹的常用實現(xiàn)方法有紅黑樹、AVL澡刹、替罪羊樹呻征、Treap、伸展樹等罢浇。
紅黑樹的 5 個性質(zhì)
性質(zhì)1：節(jié)點是紅色或黑色陆赋。
性質(zhì)2：根節(jié)點是黑色。
性質(zhì)3：每個葉節(jié)點（NIL 節(jié)點嚷闭，空節(jié)點）是黑色的攒岛。
性質(zhì)4：每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
性質(zhì)5：從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點胞锰。
