ホームページ >ウェブフロントエンド >jsチュートリアル >赤黒ツリーの挿入とJavaScriptの実装方法を詳しく解説
赤黒ツリーの挿入とJavaScriptの実装方法を詳しく解説
- 小云云オリジナル
- 2018-03-28 09:16:131580ブラウズ
この記事では、主に赤黒ツリーの挿入と Javascript の実装方法について詳しく説明し、皆さんの学習や仕事に役立つことを願っています。
赤黒木の性質
以下の性質を満たす二分探索木は赤黒木です
各ノードは黒か赤のいずれかです。
ルートノードは黒です。
各リーフノード (NIL) は黒です。
ノードが赤の場合、その子ノードは両方とも黒です。
各ノードについて、そのノードからそのすべての子孫リーフ ノードへの単純なパスには、同じ数の黒いノードが含まれます。
プロパティ 1 とプロパティ 2 については、あまり説明する必要はありません。
プロパティ 3、各リーフ ノード (NIL) は黒です。ここでのリーフ ノードは、上図のノード 1、5、8、15 を指しますが、下図の null 値を持つノードを指します。その色は黒であり、親ノードの子ノードです。 。
プロパティ 4、ノードが赤の場合 (図では赤の代わりに白が使用されています)、その 2 つの子ノード (ノード 2、5、8、15 など) は黒になります。ただし、ノードの両方の子ノードが黒である場合、ノード 1 のように、そのノードは赤ではない可能性があります。
プロパティ 5、各ノードについて、ノードからそのすべての子孫リーフ ノードへの単純なパスには、同じ数の黒いノードが含まれます。たとえば、ノード 2 からそのすべての子孫リーフ ノードへの単純なパスでは、黒いノードの数は 2 です。ルート ノード 11 からそのすべての子孫のリーフ ノードへの単純なパスでは、黒いノードの数は 2 です。 。
そのような木の特徴は何ですか？
ルートからリーフ ノードまでの単純なパス上の各ノードの色を制限することにより、赤黒ツリーは、ほぼバランスが取れているため、どのパスも他のパスの 2 倍の長さになることがなくなります。 ——「アルゴリズム入門」
性質 4 により、赤黒ツリーでは 2 つの赤いノードは隣接しません。ツリー内で可能な最短のパスはすべて黒色のノードを持つパスであり、ツリー内で可能な最長のパスは赤色のノードと黒色のノードが交互にあるパスです。プロパティ 5 と組み合わせると、各パスには同じ数の黒いノードが含まれるため、赤黒ツリーによって、どのパスも他のパスの 2 倍の長さになることがなくなります。
赤黒ツリーの挿入
まず二分探索木にノードを挿入し、赤色に着色します。黒の場合は特性 5 に違反するため調整が不便ですが、赤の場合は特性 2 または特性 4 に違反する可能性があります。比較的簡単な操作で赤黒の木の特性に戻すことができます。
二分探索木にノードが挿入された後、次の状況が発生する可能性があります:
ケース 1
ノードを挿入した後、親ノードが存在せず、ノードがルート ノードになるように挿入されるため、違反します。プロパティ 2. ノードを黒に調整し、挿入を完了します。
ケース 2
ノードを挿入した後、その親ノードは黒になり、どのプロパティにも違反しません。調整は必要なく、挿入が完了します。たとえば、次の図にノード 13 を挿入します。
ケース 3
ノードを挿入した後、その親ノードは赤になります。これはプロパティ 4 に違反しており、一連の調整が必要です。たとえば、次の図にノード 4 を挿入します。
では、一連の調整とは何でしょうか?
挿入されたノードノードの親ノードの父が赤である場合、ノードの父には黒の親ノードの祖父が必要です。なぜなら、ノードの父に親ノードがない場合、それがルートノードであり、ルートノードは黒。この場合、ノード祖父のもう一方の子ノードはノードおじさんと呼ぶことができ、これはノード父の兄弟ノードです。ノードおじさんは黒でも赤でも構いません。
最初に最も単純な状況を分析しましょう。複雑な状況は単純な状況に変換できるためです。単純な状況とは、ノードのおじさんが黒人の状況です。
シナリオ3.1
上記(a)に示すように、状況は次のようになり、ノードが赤、お父さんが赤、おじいさんとおじさんが黒、α、β、θ、ω、ηはすべてノードのサブツリー。二分探索木全体のうち、性質 4 に違反して、ノードと父親だけが正常な赤黒木になれなかったとします。このとき、画像 (a) を画像 (b) に調整すると、正常な赤黒木に戻すことができます。黒い木。調整プロセス全体は、実際には回転と色の変更の 2 つのステップに分かれています。
ローテーションとは何ですか?
上の図 (c) は二分探索木の一部です。x、y はノード、α、β、θ は対応するノードのサブツリーです。図から、α
ノードは赤、父は赤、祖父と叔父は黒です。具体的な状況 1
図 (a) では、ノードは父の左の子ノード、父はグランドの左の子ノード、ノード ; θ
色の変更
ということで、写真(a)を回転させた後、グランドを赤に、ファーザーを黒に変更して、写真(b)になり挿入完了です。
ノードが赤、父が赤、祖父と叔父が黒
ノードが父の右子ノード、父がグランドの右子ノードです。 、具体的なケースのフリップです。
つまり、叔父<グランド<父親<ノードを図(e)で回転させ、色を変更して図(f)に変更します。図 (m) に示すように、
ノードが赤、父が赤、祖父と叔父が黒の具体的なケース 3 は、
ノードが父の右の子ノード、父がグランドの左の子ノードです。下に。
図(m)のノードと父親を回転させると、図(n)になり、父親を新しいノードとして扱い、特定の状況1になります。再度回転し、色を変更して、挿入を完了します。
ノードは赤、父は赤、祖父と叔父は黒、具体的なケース4。以下の図(i)に示すように、
ノードは父の右の子ノード、父はグランドの左の子ノードです。は特殊なケースです。 3. 反転します。
図(i)のノードと父親を回転させると、図(j)になり、父親を新しいノードとして扱い、特定の状況になります。 2. 再度回転し、色を変更して、挿入が完了します。
ケース 3.2
ノード、父と叔父は赤、祖父は黒です。
上の写真(k)のように、回転するのではなく、グランドを赤、父と叔父を黒に着色し、グランドを新たなノードとして状況を判断します。グランドが新しいノードになるとケース 2 になり、調整後ケース 3.1 になると挿入が完了します。引き続きケース 3.2 になると、グランド、父親、叔父の色を変更し続けます。 , and ノード 新しいノードに親ノードがない場合は、ケース 1 になります。ルート ノードが黒く表示され、挿入が完了します。
要約すると
| ノードの操作 | 操作 | |
|---|---|---|
| 状況1 | ノードは赤で、父親なし | ノードの色を変更します |
| シナリオ 2 | ノードは赤、父は黒 | |
| ケース3.1 | ノード、父は赤、グランド、叔父は黒 | 1回か2回回転して色を変更 |
| ケース3.2 | ノード、父、叔父は赤、グランドは黒です | 父、叔父、グランド、グランドは新しいノードを再着色します |
コード
// 结点
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 は 9 つの高度なデータ構造を学習します: 赤黒ツリー ngx_rbtree_t
以上が赤黒ツリーの挿入とJavaScriptの実装方法を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。