紅黑樹比平衡二叉樹的優(yōu)點(diǎn) 為什么工程中都用紅黑樹,而不是其他平衡二叉樹?
為什么工程中都用紅黑樹,而不是其他平衡二叉樹?紅黑樹屬于平衡二叉樹。它不嚴(yán)格,因?yàn)樗鼪]有嚴(yán)格控制左右子樹的高度或節(jié)點(diǎn)數(shù)之間的差小于或等于1。但是紅黑樹的高度仍然是平均對數(shù)(n),最壞情況下的高度不會超
為什么工程中都用紅黑樹,而不是其他平衡二叉樹?
紅黑樹屬于平衡二叉樹。
它不嚴(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競賽。
紅黑樹與普通的平衡二叉樹除了顏色到底有什么區(qū)別?
首先,平衡二叉樹是一種特殊的二叉排序樹,其節(jié)點(diǎn)元素是偏序的。二是相對一般