Coursera アルゴリズム コースの 1 つでこの質問に出くわしましたが、その方法がわからないことに気付きました。しかし、それでも、私はそれについていくつかの考えを持っています。最初に頭に浮かんだのは、最適化されたビット セット (Java の などBitSet) を使用してマッピング ノードの を取得することでしkey -> colorた。したがって、ツリー全体に 1 ビット セットを割り当て、それを色情報源として使用するだけで済みます。ツリーに重複する要素がない場合は、機能するはずです。
このタスクについて他の人のアイデアを見てうれしいです。
ノード内のいずれかのポインターの最下位ビットを使用して、色情報を格納します。ノード ポインタには、ほとんどのプラットフォームで偶数のアドレスが含まれている必要があります。詳細はこちらをご覧ください。
1 つのオプションは、スプレイ ツリーなど、簿記をあまり必要としないツリーを使用することです。ただし、特にスプレイ ツリーは反復にはあまり適していないため (ランダム ルックアップでははるかに優れています)、作業しているドメインには適していない可能性があります。
ノードの位置に基づいて、赤黒ツリー全体に 1 つの BitSet を使用することもできます。たとえば、ルートは 0 番目のビット、ルートの左の枝は 1 番目のビット、右の枝は 2 番目のビット、左の枝の左の枝は3番目のビットなど; このようにして、要素が重複していても問題になりません。ツリーをトラバースしながら、現在のビット位置をメモします。
各ノードにブール値を割り当てる代わりに、ツリーに 1 つのビットセットを使用する方が、スペースの点ではるかに効率的です。各ブール値は少なくとも 1 バイトを使用し、アラインメントに応じて 1 ワードを使用する場合がありますが、ビットセットはノードごとに 1 ビットしか使用しません (さらに 2x ビットを使用して、最短の分岐が最長の枝）。
子にブール値プロパティを使用する代わりに、間違った場所に子を持つノードとして赤いノードを定義できます。
このようにすると、すべてのリーフ ノードが黒であることが保証され、新しいノードを挿入するときに、親を兄弟と交換する (赤にする) 必要があります。