紅黑樹的插入及Javascript實作方法詳解
- 小云云原創
- 2018-03-28 09:16:131489瀏覽
本文主要和大家分享紅黑樹的插入及Javascript實現方法詳解，文中透過範例程式碼介紹的非常詳細，對大家的學習或工作具有一定的參考學習價值，希望能幫助大家。
紅黑樹的性質
一棵滿足以下性質的二元搜尋樹是一棵紅黑樹
每個結點或是黑色或是紅色。
根結點是黑色的。
每個葉結點(NIL)是黑色的。
如果一個結點是紅色的，則它的兩個子結點都是黑色的。
對每個結點，從該結點到其所有後代葉結點的簡單路徑上，均包含相同數目的黑色結點。
性質1和性質2，不用做太多解釋。
性質3，每個葉結點(NIL)是黑色的。這裡的葉結點並不是指上圖結點1,5,8,15，而是指下圖中值為null的結點，它們的顏色為黑色，且是它們父結點的子結點。
性質4，如果一個結點是紅色的(圖中用白色代替紅色)，則它的兩個子結點都是黑色的，例如結點2 ,5,8,15。但是，如果某結點的兩個子結點都是黑色的，則該結點未必是紅色的，例如結點1。
性質5，對每個結點，從該結點到其所有後代葉結點的簡單路徑上，均包含相同數目的黑色結點。例如，從結點2到其所有後代葉結點的簡單路徑上，黑色結點的數量都為2；從根結點11到其所有後代葉結點的簡單路徑上，黑色結點的數量都為3。
這樣的一棵樹有什麼特色呢？
透過對任何一條從根到葉結點的簡單路徑上各個結點的顏色進行約束，紅黑樹確保沒有一條路徑會比其他路徑長出2倍，因為是近似於平衡的。 ——《演算法導論》
由於性質4，紅黑樹中不會出現兩個紅色結點相鄰的情形。樹中最短的可能出現的路徑是都是黑色結點的路徑，樹中最長的可能出現的路徑是紅色結點和黑色結點交替的路徑。再結合性質5，每條路徑上均包含相同數目的黑色結點，所以紅黑樹確保沒有一條路徑會比其他路徑長出2倍。
紅黑樹的插入
首先以二元搜尋樹的方式插入結點，並將其著為紅色。如果著為黑色，則會違反性質5，不便調整；如果著為紅色，可能會違背性質2或性質4，可以透過相對簡單的操作，使其恢復紅黑樹的性質。
一個結點以二元搜尋樹的方式被插入後，可能出現以下幾種情況：
情形1
插入結點後，無父結點，結點插入成為根結點，違反性質2，將結點調整為黑色，完成插入。
情形2
插入結點後，其父結點為黑色，沒有違反任何性質，不用調整，完成插入。例如下圖中插入結點13。
情形3
插入結點後，其父結點為紅色，違背了性質4，需要採取一系列的調整。例如下圖中插入結點4。
那麼一系列的調整是什麼呢？
如果插入結點node的父結點father為紅色，則結點father必然存在黑色的父結點grandfather，因為如果結點father不存在父結點的話，就是根結點，而根結點是黑色的。那麼結點grandfather的另一個子結點，我們可以稱為結點uncle，即結點father的兄弟結點。結點uncle可能為黑色，也可能為紅色。
先從最簡單的情形分析，因為複雜的情形可以轉換成簡單的情形，簡單的情形就是結點uncle為黑色的情形。
情形3.1
如上圖(a)中，情形是這樣的，node 為紅，father 為紅，grandfather 和uncle 為黑，α ，β，θ，ω，η 都是結點對應的子樹。假設整棵二元搜尋樹中，只有node和father因違反性質4而無法成為正常的紅黑樹，此時將圖(a)調整成圖(b)，則可以恢復成正常的紅黑樹。整個調整過程中實際分為兩步，旋轉和變色。
什麼是旋轉？
如上圖(c)是一棵二元搜尋樹的一部分，其中 x, y 是結點，α，β，θ 是對應結點的子樹。由圖可知，α < x < β < y < θ ，即α子樹中的所有結點都小於x，結點x都小於β子樹中的所有結點，β子樹中的所有結點的值都小於結點y 的值，結點y 的值都小於θ子樹中的所有結點。在二元搜尋樹中，如果結點y的值比結點x的值大，那麼結點x在結點y的左子樹中，如圖(c)；或結點y在結點x的右子樹中，如圖(d)。故 α < x < β < y < θ ，也可以用圖(d)的結構來表現。這就是旋轉，它不會破壞二元搜尋樹的性質。
node 為紅，father 為紅，grandfather 和uncle 為黑的具體情形一
圖(a)中，node 為father 的左子結點， father 為grand 的左子結點，node < father < θ < grand < uncle。這種情形中father < grand，即可以表現為father 是grand 的左子樹，也可以表現為grand 是father 的右子樹，故將圖(a)中father 和grand 旋轉，旋轉雖然不會破壞二元搜尋樹的性質，但是旋轉之後，會破壞紅黑樹的性質，所以還需要調整結點的顏色。
變色
所以圖(a)旋轉過後，還要將 grand 變成紅色，father 變成黑色，變成圖(b)，完成插入。
node 為紅，father 為紅，grandfather 和uncle 為黑的具體情形二
node 為father 的右子結點， father 為grand 的右子結點，如下圖( e)，就是具體情形一的翻轉。
即，uncle < grand < θ < father < node ，將圖(e)father 和grand 旋轉，變色後，變成圖(f )，完成插入。
node 為紅，father 為紅，grandfather 和uncle 為黑的具體情形三
node 為father 的右子結點， father 為grand 的左子結點，如下圖( m)。
將圖(m)中node 和father 旋轉後，變成圖(n)，將father看作新的node，就成為了具體情形一，再次旋轉，變色後，完成插入。
node 為紅，father 為紅，grandfather 和uncle 為黑的具體情形四
node 為father 的右子結點， father 為grand 的左子結點，如下圖( i)，就是具體情形三的翻轉。
將圖(i)中node 和father 旋轉後，變成圖(j)，將father看作新的node，就成為了具體情形二，再次旋轉，變色後，完成插入。
情形3.2
node ，father 和 uncle 為紅，grandfather 為黑。
如上圖(k)，不旋轉，而是將grand著紅，father和uncle著黑，同時將grand當作新的node，進行情形的判斷。如果grand作為新的node後，變成了情形2，則插入完成；如果變成了情形3.1，則調整後，插入完成；如果仍是情形3.2，則繼續將grand，father和uncle變色，和node結點上移，如果新的node結點沒有父節點了，則變成了情形1，將根結點著為黑色，那麼插入完成。
綜上
| #node的情形 | ##動作||
|---|---|---|
| node為紅色,無father | 將node重新著色 | |
| node為紅,father為黑 | ||
| node,father為紅,grand ,uncle為黑 | 旋轉一次或兩次,並重新著色 | |
| node,father,uncle為紅,grand為黑 | 將father, uncle,grand重新著色, grand作為新的node |
#
// 结点
function Node(value) {
this.value = value
this.color = 'red' // 结点的颜色默认为红色
this.parent = null
this.left = null
this.right = null
}
function RedBlackTree() {
this.root = null
}
RedBlackTree.prototype.insert = function (node) {
// 以二叉搜索树的方式插入结点
// 如果根结点不存在，则结点作为根结点
// 如果结点的值小于node，且结点的右子结点不存在，跳出循环
// 如果结点的值大于等于node，且结点的左子结点不存在，跳出循环
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) {
// 当node.parent不存在时，即为情形1，跳出循环
// 当node.parent.color === 'black'时，即为情形2，跳出循环
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') {
// 叶结点也是黑色的
// 情形3.1
let directionFromFatherToNode = father.left === node ? 'left' : 'right'
let directionFromGrandToFather = grand.left === father ? 'left' : 'right'
if (directionFromFatherToNode === directionFromGrandToFather) {
// 具体情形一或二
// 旋转
this._rotate(father)
// 变色
father.color = 'black'
grand.color = 'red'
} else {
// 具体情形三或四
// 旋转
this._rotate(node)
this._rotate(node)
// 变色
node.color = 'black'
grand.color = 'red'
}
break // 完成插入，跳出循环
} else {
// 情形3.2
// 变色
grand.color = 'red'
father.color = 'black'
uncle.color = 'black'
// 将grand设为新的node
node = grand
}
}
if (!node.parent) {
// 如果是情形1
node.color = 'black'
this.root = node
}
}
RedBlackTree.prototype._rotate = function (node) {
// 旋转 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相關推薦：nginx學習九高階資料結構之紅黑樹ngx_rbtree_t#
以上是紅黑樹的插入及Javascript實作方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！