說一下treemap的實現(xiàn)原理？紅黑樹的性質(zhì)？紅黑樹遍歷方式有哪些？如何實現(xiàn)樹映射？紅黑樹的本質(zhì)？紅黑樹的遍歷方法是什么因為有一個無序的樹映射，內(nèi)部實現(xiàn)是哈希表紅黑樹屬于平衡二叉樹。它不嚴格，因為它沒

說一下treemap的實現(xiàn)原理？紅黑樹的性質(zhì)？紅黑樹遍歷方式有哪些？

如何實現(xiàn)樹映射？紅黑樹的本質(zhì)？紅黑樹的遍歷方法是什么

因為有一個無序的樹映射，內(nèi)部實現(xiàn)是哈希表

紅黑樹屬于平衡二叉樹。

它不嚴格，因為它沒有嚴格控制左右子樹的高度或節(jié)點數(shù)之間的差小于或等于1。

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

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

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

紅黑樹是一種特殊的AVL樹，它遵循紅定理和黑定理紅定理：不可能有兩個連通的紅節(jié)點黑定理：根節(jié)點必須是一個黑節(jié)點，并且所有節(jié)點路徑上的黑節(jié)點數(shù)必須相等，從而導(dǎo)致空