紅黑樹是一種自平衡二叉查找樹梁呈。它的統(tǒng)計(jì)性能要好于平衡二叉樹（AVL樹），因此忍燥，紅黑樹在很多地方都有應(yīng)用墓卦。在C++ STL中掷贾，很多部分(目前包括set, multiset, map, multimap)應(yīng)用了紅黑樹的變體睛榄，java8里面的hashmap也用到紅黑樹。
紅黑樹五個(gè)性質(zhì)
紅黑樹想帅，顧名思義场靴，通過紅黑兩種顏色域保證樹的高度近似平衡。它的每個(gè)節(jié)點(diǎn)是一個(gè)五元組：color（顏色）博脑，key（數(shù)據(jù)）憎乙，left（左孩子），right（右孩子）和p（父節(jié)點(diǎn)）叉趣。
性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色
性質(zhì)2. 根是黑色
性質(zhì)3. 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）
性質(zhì)4. 如果一個(gè)節(jié)點(diǎn)是紅的泞边，則它的兩個(gè)兒子都是黑的
性質(zhì)5. 從任一節(jié)點(diǎn)到其葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
image.png
