為什么工程中都用紅黑樹(shù)，而不是其他平衡二叉樹(shù)？紅黑樹(shù)屬于平衡二叉樹(shù)。它不嚴(yán)格，因?yàn)樗鼪](méi)有嚴(yán)格控制左右子樹(shù)的高度或節(jié)點(diǎn)數(shù)之間的差小于或等于1。但是紅黑樹(shù)的高度仍然是平均對(duì)數(shù)（n），最壞情況下的高度不會(huì)超

為什么工程中都用紅黑樹(shù)，而不是其他平衡二叉樹(shù)？

紅黑樹(shù)屬于平衡二叉樹(shù)。

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

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

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