理解する前に、 赤黒ツリーとAVLツリー 違いがあるため、Red-Black ツリーと AVL ツリーについては別々に知る必要があります。

赤黒木とは何ですか?

赤黒の木は自己バランスを保っています 二分探索木 各ノードには、ノードの色を示す追加の情報が 1 ビット含まれています。ノードの色は、ノードに格納されているビット情報に応じて、赤または黒になります。

プロパティ

以下は、赤黒ツリーに関連付けられたプロパティです。

• ツリーのルート ノードは黒である必要があります。
• 赤いノードは黒い子のみを持つことができます。あるいは、隣接する 2 つのノードの色を赤にすることはできないと言えます。
• ノードに左または右の子がない場合、そのノードはリーフ ノードと言われます。そこで、左と右の子を葉ノードの下に置きます。 なし

リーフ ノードの黒の深さまたは黒の高さは、リーフ ノードからルート ノードに移動するときに遭遇する黒の数として定義できます。赤黒ツリーの重要な特性の 1 つは、すべてのリーフ ノードが同じ黒深度を持つ必要があることです。

文字から文字列へ

例を通してこの特性を理解しましょう。

上のツリーには 5 つのノードがあり、そのうち 1 つは赤、他の 4 つのノードは黒です。上のツリーには 3 つのリーフ ノードがあります。次に、各リーフ ノードの黒の深さを計算します。 3 つのリーフ ノードすべての黒の深度が 2 であることがわかります。したがって、それは赤黒の木です。

木が上記の 3 つの特性のいずれにも従わない場合、その木は赤黒木ではありません。

赤黒木の高さ

h を n 個のノードを持つツリーの高さとみなします。 n の最小値は何でしょうか?すべてのノードが黒の場合、n の値は最小になります。ツリーにすべての黒いノードが含まれている場合、そのツリーは完全な二分木になります。完全な二分木の高さが h の場合、ツリー内のノードの数は次のようになります。

n = 2h -1

n の最大値は何でしょうか?

n の値は、すべての黒ノードに 2 つの赤の子がある場合に最大になりますが、赤のノードは赤の子を持つことができないため、黒の子を持つことになります。このようにして、黒と赤の子の層が交互に存在します。したがって、黒のレイヤーの数が h であれば、赤のレイヤーの数も h になります。したがって、木の全高は 2h になります。ノードの合計数は次のとおりです。

n = 2*2h-1

AVLツリーとは何ですか?

アン AVLツリー 以下の場合 (二分探索木と平衡木) を観察すると、 は自己平衡二分探索木になります。

上記のツリーでは、要素を検索するための最悪の場合の時間計算量は O(h)、つまりツリーの高さです。上記の場合、17 個の要素を検索するために行われる比較数は 4 であり、ツリーの高さも 4 です。

以下に示すように、歪んだ二分木を考慮すると、次のようになります。

上の右側の歪んだ木では、17 個の要素を検索するために行われる比較の数は 5 であり、木に存在する要素の数も 5 です。したがって、木が歪んだ 2 分木であれば、時間計算量は次のようになります。 O(n)になります。

ここで、時間計算量が O(h) になるように、これらの歪んだツリーのバランスをとらなければなりません。という用語があります。 バランス係数 、二分探索ツリーの自己バランスをとるために使用されます。バランス係数は次のように計算できます。

バランス係数の値は、1、0、または -1 のいずれかになります。バイナリ ツリー内の各ノードの値が 1、0、または -1 の場合、そのツリーはバランスが取れていると言われます。 二分木 またはAVLツリー。

各ノードのバランス係数が 0 の場合、ツリーは完全にバランスのとれたツリーとして知られます。ツリー内の各ノードのバランス係数の値が 1、0、または -1 であるため、AVL ツリーはほぼバランスのとれたツリーです。

赤黒ツリーと AVL ツリーの違い。

赤黒ツリーと AVL ツリーの違いは次のとおりです。

選択ソートJava

二分探索木

Red-Black ツリーは二分探索木であり、AVL ツリーも二分探索木です。

ルール

赤黒ツリーには次のルールが適用されます。

1. 赤黒ツリーのノードの色は赤または黒です。
2. ルート ノードの色は黒である必要があります。
3. 隣接するノードは赤であってはなりません。言い換えれば、赤いノードは赤い子を持つことはできませんが、黒いノードは黒い子を持つことができると言えます。
4. すべてのパスに同じ数の黒いノードが存在する必要があります。その場合、木だけが赤黒木とみなされます。
5. 外部ノードは nil ノードであり、色は常に黒色です。

AVL ツリーのルール:

すべてのノードのバランス係数は、-1、0、または 1 のいずれかである必要があります。

例

上の図では、木が赤黒木かどうかを確認する必要があります。これを確認するには、まず、木が二分探索木であるかどうかを確認する必要があります。上の図からわかるように、二分探索木のすべてのプロパティを満たしています。したがって、これは二分探索木です。次に、上記のルールを満たしているかどうかを検証する必要があります。上記のツリーは、上記の 5 つのルールをすべて満たしています。したがって、上記の木は赤黒木であると結論付けられます。

上の図では、ツリーが AVL ツリーかどうかを確認する必要があります。各ノードには -1、0、または 1 のいずれかのバランス係数の値があるため、AVL ツリーになります。

その木がバランスのとれた木であるかどうかは、どのようにして判断できるのでしょうか?

赤黒ツリーの場合、ツリーが二分探索ツリーであれば、上記の規則がすべて満たされる場合、そのツリーは赤黒ツリーであると言われます。

AVL ツリーの場合、バランス係数が -1、0、または 1 の場合、上記のツリーは AVL ツリーであると言われます。

バランス調整に使用する道具

ツリーのバランスが取れていない場合は、赤黒ツリーでツリーのバランスをとるために 2 つのツールが使用されます。

jtextfield

色直し 回転

ツリーのバランスが取れていない場合は、AVL ツリー内のツリーのバランスをとるために 1 つのツールが使用されます。

回転

どの作業に対して効率的か

赤黒ツリーの場合、挿入と削除の操作が効率的です。再カラー化によってツリーのバランスが取れた場合、赤黒ツリーでの挿入および削除操作が効率的になります。

AVL ツリーの場合、ツリーのバランスを取るために必要なツールは 1 つだけであるため、検索操作は効率的です。

時間計算量

赤黒ツリーの場合、すべての操作、つまり挿入、削除、検索の時間計算量は O(logn) です。

AVL ツリーの場合、挿入、削除、検索のすべての操作の時間計算量は O(logn) です。

表形式の違いを理解しましょう。