問題タブ [red-black-tree]

私は赤い黒い木に慣れていないので、この問題がどこから来ているのか困っています. 回転と挿入方法は正しいようです。しかし、数字を入力すると 100 45 34 55 74 50 130 120 125 160 165 150

プログラムから以下の出力が得られます。右端の数字はノード内の数字、次に色、そしてノードの親です。ルート ノードには親がリストされていません。ノード 45 と 74 は両方とも RED であり、両方のノードを両方とも赤にすることはできません。なぜなら、これは RED Black Tree プロパティに違反するからです: 赤の親には常に 2 つの黒の子があります。この問題に関する助けは素晴らしいでしょう。

34 [BLACK] (45)

45 [RED] (74)

50 [RED] (55)

55 [BLACK] (45)

74 [RED] (120)

100 [BLACK] (74)

120 [BLACK]

125 [BLACK] (130)

130 [RED] (120)

150 [RED] (160)

160 [BLACK] (130)

165 [RED] (160)

RedBlackTree.h /*

RedBlackTree.cpp BST::insert(rbnode) 関数は、他の関数が使用される前に関数の違いが行われるため、このクラスで正常に動作します。

Algorithms Third Edition の紹介では、赤黒木削除の疑似コード実装があります。ここにあります...

TREE-MINIMUM はツリー内の最小値を見つけるだけで、RB-TRANSPLANT は 2 番目のパラメーターの親を取得して 3 番目のパラメーターを指し、3 番目のパラメーターの親を 2 番目のパラメーターの親にします。

私のコメントによると、彼らは yp が z であるかどうかをテストし、そうであれば xp を y に設定します。しかし、x はすでに y.right なので、これは y.right.p = y と言っているようなものですが、y.right.p はすでに y です! なぜ彼らはこれをしているのですか？

これが彼らの説明です...

「しかし、y の元の親が z の場合、xp が y の元の親を指すことは望ましくありません。これは、そのノードをツリーから削除しているためです。ノード y は上に移動してツリー内の z の位置を取るため、13 行目で xp を y に設定すると、x == T.nil であっても、xp は y の親の元の位置を指すようになります。」</p>

したがって、彼らは x の親を y のままにしたいと考えています...それはすでに y です...

赤黒木については多くの質問がありますが、どのように機能するかについては誰も答えていません。なぜ赤黒と呼ばれるのですか？これにより、どのようにツリーのバランスが保たれますか (したがって、バランスの取れていない通常の二分探索ツリーよりもパフォーマンスが向上します)? それがどのように、そしてなぜ機能するかの概要を探しているだけです。

C＃の赤黒木に挿入することについて宿題の問題があります。以下のコードを書きましたが、プログラムは最初の3つの数字を追加しても問題なく動作します。4番目の数値を追加しようとすると、NullReferenceExceptionが発生します。2日間エラーを解決しようとしていますが、理解できません。

}

Cormen に基づいて赤黒木実装を作成しましたが、正常に機能しないため、何かを壊したに違いありません。私は Cormen を正しく書き直したと信じていますが、何が間違っているのかわかりません... どうすればそれを知ることができますか.. 10 個の値を取り、ツリーがどのように見えるかを確認しました/C321/html/RedBlack/redblack.html) と私のものは異なって見えます。コード全体はかなり長いですが、それなしではエラーを再現できません。申し訳ありません。有罪は挿入後のローテーションおよび/またはフィックスアップだと思います...

編集: 新しいコードですが、疑似コードを C++ に書き直したばかりだと断言できますが、それでも赤と黒の違反が発生します...

Red - Black ツリーについて読んだすべてのことから、データを格納するのに最適なデータ構造であるように思えます。

私はデータベースを構築しようとしていますが、赤と黒のツリーの実装の面で、どこにもっと注意を払う必要があり、何をすべきでないのか疑問に思っています。

赤と黒は本当に完璧ですか？

RBT (Cormen に基づく) の削除機能を実装しました。動作しているように見えますが、事前注文で削除 + ツリーの印刷をテストすると、間違った答えが返されます。何が問題なのかを数時間調べましたが、何も見つかりませんでした...

予約注文でツリーを印刷する機能は次のとおりです。

削除する重要な残りの部分は次のとおりです。

avl ツリーの検索が高速であるいくつかの場所でそれを読みましたが、理解できませんでした。私が理解しているように: 赤黒ツリーの最大高さ = 2*log(N+1) AVL ツリーの高さ = 1.44*logo(N+1)

AVLが短いからですか？

私はHaskellでRBツリーの実装をいじっていますが、バイナリリーフツリーのようにデータがリーフにのみ配置されるように少し変更するのに苦労しています。

内部ノードは、ノードの色に加えて、ツリーのサイズなどの他の情報を保持します（通常のRBツリーのように、データは葉に保持されます）。また、挿入されるデータを並べ替える必要もありません。データを挿入するときにバランスの取れたツリーを取得するためにのみRBを使用しますが、データが挿入される順序を維持したいと思います。

元のコードは（岡崎の本から）：

私はそれを次のように変更しました:(例外：関数insの非網羅的なパターンの原因）

元のバランス関数は次のとおりです。

上記のコードから明らかなように、これを少し変更しました。

助けてくれてありがとう:)

編集：私が探している種類の表現については、Chris Okasakiが、彼の本で説明されているように、バイナリランダムアクセスリストを使用することを提案しました。別の方法は、ウェイトバランスの取れたツリーとして実装されているData.Setのコードを単純に適応させることです。

私はまだこれに対する解決策を見つけるのに苦労していますが、質問、私はおそらくもっと簡単な別のものを持っています。以下は、岡崎赤黒木実装の挿入機能です。私がやりたいことは、ツリーに挿入するときにデータをソートしないようにすることです。したがって、挿入するたびに、データは常に左端/下端の葉に移動します。x < y、x > y、または x == y を比較する必要はありません。これらのガードを削除するだけで、最初は非常に簡単に見えます: ins s@(T color ayb) = balance color (ins a) y b. 挙動は木のバランスが保たれているように見えますが、着色は少し乱れます。そして最終的にそれは将来の挿入に影響を与えます..これをどのように達成できるか考えていますか? これは、以前の質問への最初のステップになる可能性があると思います。Haskell を使い始めたばかりなので、簡単には理解できません。どうもありがとう。