這篇文章主要介紹計(jì)算機(jī)網(wǎng)絡(luò)中紅黑樹插入的示例分析，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

岱山ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18980820575（備注：SSL證書合作）期待與您的合作！

紅黑樹的性質(zhì)

一棵滿足以下性質(zhì)的二叉搜索樹是一棵紅黑樹

1. 每個(gè)結(jié)點(diǎn)或是黑色或是紅色。

2. 根結(jié)點(diǎn)是黑色的。

3. 每個(gè)葉結(jié)點(diǎn)(NIL)是黑色的。

4. 如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)子結(jié)點(diǎn)都是黑色的。

5. 對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)。

性質(zhì)1和性質(zhì)2，不用做過多解釋。

性質(zhì)3，每個(gè)葉結(jié)點(diǎn)(NIL)是黑色的。這里的葉結(jié)點(diǎn)并不是指上圖中結(jié)點(diǎn)1,5,8,15，而是指下圖中值為null的結(jié)點(diǎn)，它們的顏色為黑色，且是它們父結(jié)點(diǎn)的子結(jié)點(diǎn)。

性質(zhì)4，如果一個(gè)結(jié)點(diǎn)是紅色的(圖中用白色代替紅色)，則它的兩個(gè)子結(jié)點(diǎn)都是黑色的，例如結(jié)點(diǎn)2,5,8,15。但是，如果某結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都是黑色的，該結(jié)點(diǎn)未必是紅色的，例如結(jié)點(diǎn)1。

性質(zhì)5，對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)。例如，從結(jié)點(diǎn)2到其所有后代葉結(jié)點(diǎn)的簡單路徑上，黑色結(jié)點(diǎn)的數(shù)量都為2；從根結(jié)點(diǎn)11到其所有后代葉結(jié)點(diǎn)的簡單路徑上，黑色結(jié)點(diǎn)的數(shù)量都為3。

這樣的一棵樹有什么特點(diǎn)呢？

通過對(duì)任何一條從根到葉結(jié)點(diǎn)的簡單路徑上各個(gè)結(jié)點(diǎn)的顏色進(jìn)行約束，紅黑樹確保沒有一條路徑會(huì)比其他路徑長出2倍，因?yàn)槭墙朴谄胶獾?。——《算法?dǎo)論》

由于性質(zhì)4，紅黑樹中不會(huì)出現(xiàn)兩個(gè)紅色結(jié)點(diǎn)相鄰的情形。樹中最短的可能出現(xiàn)的路徑是都是黑色結(jié)點(diǎn)的路徑，樹中最長的可能出現(xiàn)的路徑是紅色結(jié)點(diǎn)和黑色結(jié)點(diǎn)交替的路徑。再結(jié)合性質(zhì)5，每條路徑上均包含相同數(shù)目的黑色結(jié)點(diǎn)，所以紅黑樹確保沒有一條路徑會(huì)比其他路徑長出2倍。

紅黑樹的插入

首先以二叉搜索樹的方式插入結(jié)點(diǎn)，并將其著為紅色。如果著為黑色，則會(huì)違背性質(zhì)5，不便調(diào)整；如果著為紅色，可能會(huì)違背性質(zhì)2或性質(zhì)4，可以通過相對(duì)簡單的操作，使其恢復(fù)紅黑樹的性質(zhì)。

一個(gè)結(jié)點(diǎn)以二叉搜索樹的方式被插入后，可能出現(xiàn)以下幾種情況：

情形1

插入結(jié)點(diǎn)后，無父結(jié)點(diǎn)，結(jié)點(diǎn)插入成為根結(jié)點(diǎn)，違背性質(zhì)2，將結(jié)點(diǎn)調(diào)整為黑色，完成插入。

情形2

插入結(jié)點(diǎn)后，其父結(jié)點(diǎn)為黑色，沒有違背任何性質(zhì)，不用調(diào)整，完成插入。例如下圖中插入結(jié)點(diǎn)13。

情形3

插入結(jié)點(diǎn)后，其父結(jié)點(diǎn)為紅色，違背了性質(zhì)4，需要采取一系列的調(diào)整。例如下圖中插入結(jié)點(diǎn)4。

那么一系列的調(diào)整是什么呢？

如果插入結(jié)點(diǎn)node的父結(jié)點(diǎn)father為紅色，則結(jié)點(diǎn)father必然存在黑色的父結(jié)點(diǎn)grandfather，因?yàn)槿绻Y(jié)點(diǎn)father不存在父結(jié)點(diǎn)的話，就是根結(jié)點(diǎn)，而根結(jié)點(diǎn)是黑色的。那么結(jié)點(diǎn)grandfather的另一個(gè)子結(jié)點(diǎn)，我們可以稱之為結(jié)點(diǎn)uncle，即結(jié)點(diǎn)father的兄弟結(jié)點(diǎn)。結(jié)點(diǎn)uncle可能為黑色，也可能為紅色。

先從最簡單的情形分析，因?yàn)閺?fù)雜的情形可以轉(zhuǎn)化為簡單的情形，簡單的情形就是結(jié)點(diǎn)uncle為黑色的情形。

情形3.1

如上圖(a)中，情形是這樣的，node 為紅，father 為紅，grandfather 和 uncle 為黑，α，β，θ，ω，η 都是結(jié)點(diǎn)對(duì)應(yīng)的子樹。假設(shè)整棵二叉搜索樹中，只有node和father因違背性質(zhì)4而無法成為正常的紅黑樹，此時(shí)將圖(a)調(diào)整成圖(b)，則可以恢復(fù)成正常的紅黑樹。整個(gè)調(diào)整過程中實(shí)際分為兩步，旋轉(zhuǎn)和變色。

什么是旋轉(zhuǎn)？

如上圖(c)是一棵二叉搜索樹的一部分，其中 x, y 是結(jié)點(diǎn)，α，β，θ 是對(duì)應(yīng)結(jié)點(diǎn)的子樹。由圖可知，α < x < β < y < θ ，即 α子樹中的所有結(jié)點(diǎn)都小于x，結(jié)點(diǎn) x都小于 β子樹中的所有結(jié)點(diǎn)，β子樹中的所有結(jié)點(diǎn)的值都小于結(jié)點(diǎn) y 的值，結(jié)點(diǎn) y 的值都小于 θ子樹中的所有結(jié)點(diǎn)。在二叉搜索樹中，如果結(jié)點(diǎn)y的值比結(jié)點(diǎn)x的值大，那么結(jié)點(diǎn)x在結(jié)點(diǎn)y的左子樹中，如圖(c)；或者結(jié)點(diǎn)y在結(jié)點(diǎn)x的右子樹中，如圖(d)。故 α < x < β < y < θ ，也可以用圖(d)的結(jié)構(gòu)來表現(xiàn)。這就是旋轉(zhuǎn)，它不會(huì)破壞二叉搜索樹的性質(zhì)。

node 為紅，father 為紅，grandfather 和 uncle 為黑的具體情形一

圖(a)中，node 為 father 的左子結(jié)點(diǎn)， father 為 grand 的左子結(jié)點(diǎn)，node < father < θ < grand < uncle。這種情形中 father < grand，即可以表現(xiàn)為 father 是 grand 的左子樹，也可以表現(xiàn)為 grand 是 father 的右子樹，故將圖(a)中 father 和 grand 旋轉(zhuǎn)，旋轉(zhuǎn)雖然不會(huì)破壞二叉搜索樹的性質(zhì)，但是旋轉(zhuǎn)之后，會(huì)破壞紅黑樹的性質(zhì)，所以還需要調(diào)整結(jié)點(diǎn)的顏色。

變色

所以圖(a)旋轉(zhuǎn)過后，還要將 grand 變?yōu)榧t色，father 變?yōu)楹谏?，變成圖(b)，完成插入。

node 為紅，father 為紅，grandfather 和 uncle 為黑的具體情形二

node 為 father 的右子結(jié)點(diǎn)， father 為 grand 的右子結(jié)點(diǎn)，如下圖(e)，就是具體情形一的翻轉(zhuǎn)。

即，uncle < grand < θ < father < node ，將圖(e)中 father 和 grand 旋轉(zhuǎn)，變色后，變成圖(f)，完成插入。

node 為紅，father 為紅，grandfather 和 uncle 為黑的具體情形三

node 為 father 的右子結(jié)點(diǎn)， father 為 grand 的左子結(jié)點(diǎn)，如下圖(m)。

將圖(m)中 node 和 father 旋轉(zhuǎn)后，變成圖(n)，將father看作新的node，就成為了具體情形一，再次旋轉(zhuǎn)，變色后，完成插入。

node 為紅，father 為紅，grandfather 和 uncle 為黑的具體情形四

node 為 father 的右子結(jié)點(diǎn)， father 為 grand 的左子結(jié)點(diǎn)，如下圖(i)，就是具體情形三的翻轉(zhuǎn)。

將圖(i)中 node 和 father 旋轉(zhuǎn)后，變成圖(j)，將father看作新的node，就成為了具體情形二，再次旋轉(zhuǎn)，變色后，完成插入。

情形3.2

node ，father 和 uncle 為紅，grandfather 為黑。

如上圖(k)，不旋轉(zhuǎn)，而是將grand著紅，father和uncle著黑，同時(shí)將grand作為新的node，進(jìn)行情形的判斷。如果grand作為新的node后，變成了情形2，則插入完成；如果變成了情形3.1，則調(diào)整后，插入完成；如果仍是情形3.2，則繼續(xù)將grand，father和uncle變色，和node結(jié)點(diǎn)上移，如果新的node結(jié)點(diǎn)沒有父節(jié)點(diǎn)了，則變成了情形1，將根結(jié)點(diǎn)著為黑色，那么插入完成。

綜上

	node的情形	操作
情形1	node為紅,無father	將node重新著色
情形2	node為紅,father為黑
情形3.1	node,father為紅,grand,uncle為黑	旋轉(zhuǎn)一次或兩次,并重新著色
情形3.2	node,father,uncle為紅,grand為黑	將father, uncle,grand重新著色, grand作為新的node

代碼

// 結(jié)點(diǎn)
function Node(value) {
 this.value = value
 this.color = 'red' // 結(jié)點(diǎn)的顏色默認(rèn)為紅色
 this.parent = null
 this.left = null
 this.right = null
}

function RedBlackTree() {
 this.root = null
}

RedBlackTree.prototype.insert = function (node) {
 // 以二叉搜索樹的方式插入結(jié)點(diǎn)
 // 如果根結(jié)點(diǎn)不存在，則結(jié)點(diǎn)作為根結(jié)點(diǎn)
 // 如果結(jié)點(diǎn)的值小于node，且結(jié)點(diǎn)的右子結(jié)點(diǎn)不存在，跳出循環(huán)
 // 如果結(jié)點(diǎn)的值大于等于node，且結(jié)點(diǎn)的左子結(jié)點(diǎn)不存在，跳出循環(huán)
 if (!this.root) {
 this.root = node
 } else {
 let current = this.root
 while (current[node.value <= current.value ? 'left' : 'right']) {
  current = current[node.value <= current.value ? 'left' : 'right']
 }
 current[node.value <= current.value ? 'left' : 'right'] = node
 node.parent = current
 }
 // 判斷情形
 this._fixTree(node)
 return this
}

RedBlackTree.prototype._fixTree = function (node) {
 // 當(dāng)node.parent不存在時(shí)，即為情形1，跳出循環(huán)
 // 當(dāng)node.parent.color === 'black'時(shí)，即為情形2，跳出循環(huán)
 while (node.parent && node.parent.color !== 'black') {
 // 情形3
 let father = node.parent
 let grand = father.parent
 let uncle = grand[grand.left === father ? 'right' : 'left']
 if (!uncle || uncle.color === 'black') {
  // 葉結(jié)點(diǎn)也是黑色的
  // 情形3.1
  let directionFromFatherToNode = father.left === node ? 'left' : 'right'
  let directionFromGrandToFather = grand.left === father ? 'left' : 'right'
  if (directionFromFatherToNode === directionFromGrandToFather) {
  // 具體情形一或二
  // 旋轉(zhuǎn)
  this._rotate(father)
  // 變色
  father.color = 'black'
  grand.color = 'red'
  } else {
  // 具體情形三或四
  // 旋轉(zhuǎn)
  this._rotate(node)
  this._rotate(node)
  // 變色
  node.color = 'black'
  grand.color = 'red'
  }
  break // 完成插入，跳出循環(huán)
 } else {
  // 情形3.2
  // 變色
  grand.color = 'red'
  father.color = 'black'
  uncle.color = 'black'
  // 將grand設(shè)為新的node
  node = grand
 }
 }

 if (!node.parent) {
 // 如果是情形1
 node.color = 'black'
 this.root = node
 }
}

RedBlackTree.prototype._rotate = function (node) {
 // 旋轉(zhuǎn) node 和 node.parent
 let y = node.parent
 if (y.right === node) {
 if (y.parent) {
  y.parent[y.parent.left === y ? 'left' : 'right'] = node
 }
 node.parent = y.parent
 if (node.left) {
  node.left.parent = y
 }
 y.right = node.left
 node.left = y
 y.parent = node
 } else {
 if (y.parent) {
  y.parent[y.parent.left === y ? 'left' : 'right'] = node
 }
 node.parent = y.parent
 if (node.right) {
  node.right.parent = y
 }
 y.left = node.right
 node.right = y
 y.parent = node
 }
}

let arr = [11, 2, 14, 1, 7, 15, 5, 8, 4, 16]
let tree = new RedBlackTree()
arr.forEach(i => tree.insert(new Node(i)))
debugger

以上是“計(jì)算機(jī)網(wǎng)絡(luò)中紅黑樹插入的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司行業(yè)資訊頻道！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站欄目：計(jì)算機(jī)網(wǎng)絡(luò)中紅黑樹插入的示例分析-創(chuàng)新互聯(lián)
文章鏈接：http://weahome.cn/article/dophes.html