3

すべての AVL ツリーが赤黒ツリーのように着色できるという証明を探しています。誰か証明してくれませんか？

4

4 に答える 4

1

定義により、R/B ツリーは |maxPath - minPath| のように、AVL よりもわずかにバランスが悪い場合があります。AVL の場合は <= 1、R/B の maxPath <= 2 * minPath である必要があるため、すべての R/B が AVL であるとは限りませんが、AVL-s が空のサブツリーを持つ必要はありません。

     4
    / \
   3   6
  /\   /\
 1  E 5  8

は完全に正当な AVL であり、R/B ではありません。なぜなら、R/B は葉を含むことができず、常に黒く着色された空のツリーで終了する必要があるためです。そのため、上のツリーに色を付けることができません。R/B にするには、すべての葉 x をノード E x E に変換し、次の規則に従うことができます。ノードには黒色の子がある すべての空のツリーは黒色 ノードが与えられると、空のツリーへのすべてのパスは同じ数のブラック ノードを持つ必要があります 任意のリーフは、左と右のサブツリーが空のノードで置き換えることができます 最大パス T ≤ 2 * 最小パス T

ところで、ノードと葉が赤で着色されていることに気付きました-これは意図したものではありませんでした。カロル

于 2011-03-24T13:05:39.647 に答える
0

赤黒木は枝の高さを赤いノードで調整するので、高さの差が制限されている場合は、最も短い黒い枝から始めて、いつでもすべての枝を調整できます。しかし、すべての枝の高さを数えなければならないため、非常に大きなコストがかかります。

赤黒木の最大局所高差境界は 2 です。

于 2021-10-23T22:49:38.557 に答える
-2

答えはノーだと思います。

AVLツリーはRBツリーよりもバランスが良く、バランスが異なることを意味します。つまり、すべてのAVLツリーを有効なRBツリーとして色付けすることはできません。

于 2009-03-24T21:19:29.790 に答える
-2

答えは「はい」です。すべてのAVLツリーは赤黒に着色でき、その逆は成り立ちません。

私はそれをどのように行うかを正確に理解しておらず、その証拠も求めています。

于 2009-04-15T18:19:58.620 に答える