首先了解下二叉樹(shù)特性:
? ? 1.左子樹(shù)上所有的節(jié)點(diǎn)的值均小于或等于它的根節(jié)點(diǎn)的值
? ? 2.右子樹(shù)上所有節(jié)點(diǎn)的值均大于或等于它的根節(jié)點(diǎn)的值
? ? 3.左右子樹(shù)也分別為二叉樹(shù)排序
二叉樹(shù)優(yōu)缺點(diǎn):查找所需要的最大次數(shù)等同于二叉查找樹(shù)丶高度.在插入結(jié)點(diǎn)的時(shí)候也是利用類(lèi)似的方法,通過(guò)一層一層比較大小,找到新節(jié)點(diǎn)適合插入位置.缺點(diǎn)就是后來(lái)插入的很容易變成線性結(jié)構(gòu),查找性能大打折扣.
紅黑樹(shù)特性:
? ? 1.紅黑樹(shù)是一種自平衡的二叉查找樹(shù).
????2.節(jié)點(diǎn)是紅色或者黑色
? ? 3.根節(jié)點(diǎn)是黑色
? ? 4.每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)(NIL節(jié)點(diǎn))
? ? 5.每個(gè)紅色節(jié)點(diǎn)的兩字子節(jié)點(diǎn)都是黑色(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
? ? 6.從任一節(jié)點(diǎn)到其每個(gè)葉子所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)
紅黑樹(shù)從根到葉子的最長(zhǎng)路徑不會(huì)超過(guò)最短路徑的2倍,當(dāng)插入或刪除節(jié)點(diǎn)的時(shí)候,紅黑樹(shù)的規(guī)則很有可能被破壞,我們需要調(diào)整,來(lái)維持規(guī)則.
調(diào)整的兩種方法:
????變色:為了重新符合紅黑樹(shù)的規(guī)則,嘗試把紅色節(jié)點(diǎn)變?yōu)楹谏?或者把黑色節(jié)點(diǎn)變?yōu)榧t色
? ? 旋轉(zhuǎn)有兩種情況:
? ? 左旋轉(zhuǎn):逆時(shí)針旋轉(zhuǎn)紅黑樹(shù)的兩個(gè)節(jié)點(diǎn),使得父節(jié)點(diǎn)被自己的右孩子取代,而自己的成為自己的做孩子.如下圖
? ? 右旋轉(zhuǎn):順時(shí)針旋轉(zhuǎn)紅黑樹(shù)的兩個(gè)節(jié)點(diǎn),使得父節(jié)點(diǎn)被自己的左孩子取代,而自己成為自己的右孩子.
