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

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

評論: 0　查看評論　發表評論

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

網站導航：博客園首頁  我的園子  新聞  閃存  小組  博問  知識庫