一、紅黑樹（Red-Black Tree）是二叉搜索樹（Binary Search Tree）的一種。二叉搜索樹在最壞的情況下可能會(huì)變成一個(gè)鏈表（當(dāng)所有節(jié)點(diǎn)按從小到大的順序依次插入后）。這種低效產(chǎn)生的原因是樹沒有維持一定的平衡性，要提高搜索效率，就要想辦法來維持樹左邊的平衡，也就是要盡時(shí)降低樹的高度，可行的做法就是用一些策略在每次修改樹的內(nèi)容之后都調(diào)整樹的結(jié)構(gòu)，使之滿足一定的平衡條件。其中一種滿足一定平衡條件而且目前應(yīng)用廣泛的是紅黑樹。它可以在每一次插入或刪除節(jié)點(diǎn)之后都會(huì)花O（log N）的時(shí)間來對(duì)樹的結(jié)構(gòu)作修改，以保持樹的平衡。而紅黑樹的查找方法與二叉搜索樹完全一樣，也能夠在O(log N)

作者: Rollen Holt 發(fā)表于 2010-12-16 00:34 原文鏈接

評(píng)論: 0　查看評(píng)論　發(fā)表評(píng)論

最新新聞：
· 在線比價(jià)搜索引擎Shop.com出售 蓋茨曾投資(2010-12-16 08:54)
· 鄧元鋆離職背后：諾基亞中國(guó)腹背受敵(2010-12-16 08:53)
· 央行：超級(jí)網(wǎng)銀收費(fèi)將降低(2010-12-16 08:52)
· Android和iPhone平臺(tái)2010年度最佳軟件和游戲榜單出爐(2010-12-16 08:50)
· 京東遭遇出版社集體逼宮 今日恢復(fù)原價(jià)改返券(2010-12-16 08:48)

網(wǎng)站導(dǎo)航：博客園首頁(yè)  我的園子  新聞  閃存  小組  博問  知識(shí)庫(kù)