赤黒ツリーの挿入とJavaScriptの実装方法を詳しく解説

この記事では、主に赤黒ツリーの挿入と Javascript の実装方法について詳しく説明し、皆さんの学習や仕事に役立つことを願っています。

赤黒木の性質

以下の性質を満たす二分探索木は赤黒木です

1. 各ノードは黒か赤のいずれかです。

2. ルートノードは黒です。

3. 各リーフノード (NIL) は黒です。

4. ノードが赤の場合、その子ノードは両方とも黒です。

5. 各ノードについて、そのノードからそのすべての子孫リーフ ノードへの単純なパスには、同じ数の黒いノードが含まれます。

プロパティ 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 ? &#39;left&#39; : &#39;right&#39;]) {
  current = current[node.value <= current.value ? &#39;left&#39; : &#39;right&#39;]
 }
 current[node.value <= current.value ? &#39;left&#39; : &#39;right&#39;] = node
 node.parent = current
 }
 // 判断情形
 this._fixTree(node)
 return this
}

RedBlackTree.prototype._fixTree = function (node) {
 // 当node.parent不存在时，即为情形1，跳出循环
 // 当node.parent.color === &#39;black&#39;时，即为情形2，跳出循环
 while (node.parent && node.parent.color !== &#39;black&#39;) {
 // 情形3
 let father = node.parent
 let grand = father.parent
 let uncle = grand[grand.left === father ? &#39;right&#39; : &#39;left&#39;]
 if (!uncle || uncle.color === &#39;black&#39;) {
  // 叶结点也是黑色的
  // 情形3.1
  let directionFromFatherToNode = father.left === node ? &#39;left&#39; : &#39;right&#39;
  let directionFromGrandToFather = grand.left === father ? &#39;left&#39; : &#39;right&#39;
  if (directionFromFatherToNode === directionFromGrandToFather) {
  // 具体情形一或二
  // 旋转
  this._rotate(father)
  // 变色
  father.color = &#39;black&#39;
  grand.color = &#39;red&#39;
  } else {
  // 具体情形三或四
  // 旋转
  this._rotate(node)
  this._rotate(node)
  // 变色
  node.color = &#39;black&#39;
  grand.color = &#39;red&#39;
  }
  break // 完成插入，跳出循环
 } else {
  // 情形3.2
  // 变色
  grand.color = &#39;red&#39;
  father.color = &#39;black&#39;
  uncle.color = &#39;black&#39;
  // 将grand设为新的node
  node = grand
 }
 }

 if (!node.parent) {
 // 如果是情形1
 node.color = &#39;black&#39;
 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 ? &#39;left&#39; : &#39;right&#39;] = 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 ? &#39;left&#39; : &#39;right&#39;] = 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

関連推奨事項:

PHP バイナリ ツリー (3): 赤黒ツリー

Nginx の赤黒ツリー

nginx は 9 つの高度なデータ構造を学習します: 赤黒ツリー ngx_rbtree_t

以上が赤黒ツリーの挿入とJavaScriptの実装方法を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。