C STL中的map用紅黑樹實(shí)現(xiàn)，搜索效率是O(lgN),為什么不像python一樣用散列表從而獲得常數(shù)級搜索效率呢？因?yàn)橛幸粋€無序的映射，內(nèi)部實(shí)現(xiàn)是哈希表為什么TreeSet使用紅黑樹，而一些數(shù)

C STL中的map用紅黑樹實(shí)現(xiàn)，搜索效率是O(lgN),為什么不像python一樣用散列表從而獲得常數(shù)級搜索效率呢？

因?yàn)橛幸粋€無序的映射，內(nèi)部實(shí)現(xiàn)是哈希表

為什么TreeSet使用紅黑樹，而一些數(shù)據(jù)庫索引使用B-tree和B-tree？在cstl中，許多部分（包括set、multiset、map和Multimap）都使用了紅黑樹變體（SGI-STL中的紅黑樹有一些變化，這些變化為set操作提供了更好的性能和支持）。紅黑樹是一個二叉搜索樹，每個節(jié)點(diǎn)都有顏色屬性。顏色是紅色或黑色。

紅黑樹，b 樹分別用于什么場景，為什么？

假設(shè)您的計(jì)算機(jī)中有十億個身份證信息。如果你想用你的電腦來添加，刪除和搜索這些身份證信息，你應(yīng)該如何設(shè)計(jì)一個程序來實(shí)現(xiàn)這些功能？

當(dāng)然，最簡單的方法是逐個比較，但此操作平均需要5億次。

如果應(yīng)用紅黑樹的話，只要比正確的次數(shù)最多，也就是最多30次。

30倍于5億倍，程序性能提高了1600多萬倍。

紅黑樹有什么用途？

紅黑樹的操作時間與二叉搜索樹相同，搜索、插入和刪除的時間復(fù)雜度為O（logn）。紅黑樹是一種特殊的AVL樹。它遵循了red定理和black定理red定理：不可能有兩個連通的red節(jié)點(diǎn)black定理：根節(jié)點(diǎn)必須是一個black節(jié)點(diǎn)，并且所有節(jié)點(diǎn)路徑上的black節(jié)點(diǎn)數(shù)必須相等，從而導(dǎo)致空

紅黑樹屬于平衡二叉樹。

它不嚴(yán)格，因?yàn)樗鼪]有嚴(yán)格控制左右子樹的高度或節(jié)點(diǎn)數(shù)之間的差小于或等于1。

但是紅黑樹的高度仍然是平均對數(shù)（n），最壞情況下的高度不會超過2log（n），這是通過數(shù)學(xué)證明的。所以這是一棵平衡樹，但并不嚴(yán)格。然而，嚴(yán)格性并不影響數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性。

紅黑樹主要用于系統(tǒng)底層，不用于OI競賽。