建站
咨詢
售后
建站咨詢
新聞中心
紅黑樹算是很難的一種數(shù)據(jù)結(jié)構(gòu)吧，一般很少考察插入、刪除等具體操作步驟，如果遇到要你手寫紅黑樹的面試官，就直接告辭吧。所以，更多是會考察你對紅黑樹的理解程度，考察的最多的估計(jì)就是為什么有了二查找查找樹/平衡樹還需要紅黑樹這個(gè)問題了，今天，你只需要花一分鐘的時(shí)間，就知道怎么回答這個(gè)問題了。
創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：做網(wǎng)站、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的井岡山網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
1、二叉查找樹的缺點(diǎn)
二叉查找樹，相信大家都接觸過，二叉查找樹的特點(diǎn)就是左子樹的節(jié)點(diǎn)值比父親節(jié)點(diǎn)小，而右子樹的節(jié)點(diǎn)值比父親節(jié)點(diǎn)大，如圖
基于二叉查找樹的這種特點(diǎn)，我們在查找某個(gè)節(jié)點(diǎn)的時(shí)候，可以采取類似于二分查找的思想，快速找到某個(gè)節(jié)點(diǎn)。n 個(gè)節(jié)點(diǎn)的二叉查找樹，正常的情況下，查找的時(shí)間復(fù)雜度為 O(logn)。
之所以說是正常情況下，是因?yàn)槎娌檎覙溆锌赡艹霈F(xiàn)一種極端的情況，例如
這種情況也是滿足二叉查找樹的條件，然而，此時(shí)的二叉查找樹已經(jīng)近似退化為一條鏈表，這樣的二叉查找樹的查找時(shí)間復(fù)雜度頓時(shí)變成了 O(n)，可想而知，我們必須不能讓這種情況發(fā)生，為了解決這個(gè)問題，于是我們引申出了平衡二叉樹。
2、平衡二叉樹
平衡二叉樹就是為了解決二叉查找樹退化成一顆鏈表而誕生了，平衡樹具有如下特點(diǎn)
- 具有二叉查找樹的全部特性。
- 每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1。
例如：圖一就是一顆平衡樹了，而圖二則不是(節(jié)點(diǎn)右邊標(biāo)的是這個(gè)節(jié)點(diǎn)的高度)
對于圖二，因?yàn)楣?jié)點(diǎn)9的左孩子高度為2，而右孩子高度為0。他們之間的差值超過1了。
平衡樹基于這種特點(diǎn)就可以保證不會出現(xiàn)大量節(jié)點(diǎn)偏向于一邊的情況了。關(guān)于平衡樹如何構(gòu)建、插入、刪除、左旋、右旋等操作這里不在說明.
于是，通過平衡樹，我們解決了二叉查找樹的缺點(diǎn)。對于有 n 個(gè)節(jié)點(diǎn)的平衡樹，最壞的查找時(shí)間復(fù)雜度也為 O(logn)。
3、為什么有了平衡樹還需要紅黑樹?
雖然平衡樹解決了二叉查找樹退化為近似鏈表的缺點(diǎn)，能夠把查找時(shí)間控制在 O(logn)，不過卻不是最佳的，因?yàn)槠胶鈽湟竺總€(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1，這個(gè)要求實(shí)在是太嚴(yán)了，導(dǎo)致每次進(jìn)行插入/刪除節(jié)點(diǎn)的時(shí)候，幾乎都會破壞平衡樹的第二個(gè)規(guī)則，進(jìn)而我們都需要通過左旋和右旋來進(jìn)行調(diào)整，使之再次成為一顆符合要求的平衡樹。
顯然，如果在那種插入、刪除很頻繁的場景中，平衡樹需要頻繁著進(jìn)行調(diào)整，這會使平衡樹的性能大打折扣，為了解決這個(gè)問題，于是有了紅黑樹，紅黑樹具有如下特點(diǎn)：
- 具有二叉查找樹的特點(diǎn)。
- 根節(jié)點(diǎn)是黑色的;
- 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)(NIL)，也就是說，葉子節(jié)點(diǎn)不存數(shù)據(jù)。
- 任何相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色，也就是說，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開的。
- 每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)的葉子節(jié)點(diǎn)是所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)。
例如下面的圖片(注意，圖片中黑色的、空的葉子節(jié)點(diǎn)沒有畫出)(圖片來自極客時(shí)間)
正是由于紅黑樹的這種特點(diǎn)，使得它能夠在最壞情況下，也能在 O(logn) 的時(shí)間復(fù)雜度查找到某個(gè)節(jié)點(diǎn)。至于為什么就能夠保證時(shí)間復(fù)雜度為 O(logn)，我這里就不細(xì)講了，后面的文章可能會講。
不過，與平衡樹不同的是，紅黑樹在插入、刪除等操作，不會像平衡樹那樣，頻繁著破壞紅黑樹的規(guī)則，所以不需要頻繁著調(diào)整，這也是我們?yōu)槭裁创蠖鄶?shù)情況下使用紅黑樹的原因。
不過，如果你要說，單單在查找方面的效率的話，平衡樹比紅黑樹快。
所以，我們也可以說，紅黑樹是一種不大嚴(yán)格的平衡樹。也可以說是一個(gè)折中發(fā)方案。
如果我上面講的，你都懂，都能夠在面試中說出來，應(yīng)該是足夠的了。我當(dāng)時(shí)就是這么回答的。
4、總結(jié)
所以，最后的答案是，平衡樹是為了解決二叉查找樹退化為鏈表的情況，而紅黑樹是為了解決平衡樹在插入、刪除等操作需要頻繁調(diào)整的情況。
不過，紅黑樹還有挺多其他的知識點(diǎn)可以考，例如紅黑樹有哪些應(yīng)用場景?向集合容器中 HashMap，TreeMap 等，內(nèi)部結(jié)構(gòu)就用到了紅黑樹了。還有構(gòu)建一棵節(jié)點(diǎn)個(gè)數(shù)為 n 的紅黑樹，時(shí)間復(fù)雜度是多少?紅黑樹與哈希表在不同應(yīng)該場景的選擇?紅黑樹有哪些性質(zhì)?紅黑樹各種操作的時(shí)間復(fù)雜度是多少?
如果你把這些都弄懂了，應(yīng)該就差不多可以的了，后面有時(shí)間的話，我給大家詳細(xì)講一下這些題，這里最好是要求理解，而不是死記硬背。
標(biāo)題名稱：有了二叉查找樹、平衡樹為啥還需要紅黑樹？
標(biāo)題URL：http://m.5511xx.com/article/dpdedih.html
