1. 概要

このチュートリアルでは、AVLと赤黒木という2つの自己平衡二分データ構造について説明します。 プロパティと操作を例とともに示します。

最後に、それらの間のいくつかのコアの違いを探ります。

2. AVLツリーの概要

AVLツリーを理解するために、最初にバイナリツリーデータ構造について説明しましょう。 これは、AVLツリーデータ構造が必要な理由を理解するのに役立ちます。

二分木データ構造では、最大2つの子ノードを許可できます。 二分木を使用して、データを整理できます。 ただし、データは検索またはトラバース操作用に最適化されていません。

したがって、この問題を解決するために、二分探索木(BST)データ構造が導入されています。 これは、バイナリツリーの更新バージョンです。 追加されたプロパティは、親ノードよりも小さいデータが左側のサブツリーに追加されることです。 同様に、情報が親ノードよりも大きい場合は、それらを右側のサブツリーに追加します。

すべてのツリー操作はバイナリ検索ツリーで最適化されており、実行時間はバイナリツリーよりも高速です。 しかし、それでも、いくつかの問題があります。 二分探索木は、左に歪んだツリーまたは右に歪んだツリーになる可能性があります。左に歪んだツリーと右に歪んだツリーを見てみましょう。

BSTデータ構造の最大の利点は、すべてのツリー操作の時間計算量がであるということです。ここで、はノードの総数です。 BSTが左スキューまたは右スキューのツリーである場合でも、時間計算量はになります。 この問題の解決策は、AVLツリーのデータ構造です。

これは、自己平衡二分探索木の一種です。 ノードごとにバランス係数があり、またはである必要があります。 バランス係数は、左側のサブツリーの高さから右側のサブツリーの高さを差し引くことによって計算されます。 バランス係数がまたはよりも大きい場合は、回転を適用してツリーのバランスを取り直す必要があります。 AVLツリーを見てみましょう。

AVLツリーには、ツリー操作の時間計算量が 平均的にも最悪の場合にも。

3. AVLツリーのプロパティ

次に、AVLツリーデータ構造のプロパティについて説明します。

AVLツリーは高さバランスツリーとも呼ばれます。 高さのAVLツリー内のノードの最大数はにすることができます。 さらに、高さのAVLツリー内のノードの最小数は、漸化式:、ここで、、およびを使用して計算できます。

左または右の回転を適用することにより、AVLツリーのバランスをとることができます。 AVLツリーのツリー操作はBSTと同じように機能します。 ただし、ツリー操作を実行した後、各ノードのバランス係数を確認する必要があります。したがって、ツリーが不均衡な場合は、バランスをとるためにローテーションを実行します。

右側のサブツリーの要素が増える可能性があり、いくつかのツリー操作を適用した後、AVLツリーのバランスが崩れる可能性があります。 不平衡ノードを左側に回転させてこれを克服し、AVLツリーを再び平衡にします。

左側のサブツリーの要素が増える可能性があり、いくつかのツリー操作を適用した後、AVLツリーが不均衡になる可能性があります。 これを克服するために、不平衡ノードを右側に回転させて、AVLツリーを再び平衡にします。

もう1つの可能性は、AVLツリーでいくつかのツリー操作を実行し、右側のサブツリーがないと不均衡になりますが、左側のサブツリーには、値が親ノードよりも大きいすべてのノードが含まれている場合です。 これを克服するには、右回転と左回転の2回転を実行する必要があります。

同様に、AVLツリーは、左側のサブツリーがないと不均衡になる可能性がありますが、右側のサブツリーには、値が親ノードよりも小さいノードのみが含まれます。 AVLツリーのバランスをとるために2つの回転を実行する必要があります。1つは左回転、もう1つは右回転です。

4. AVL木の操作

4.1. 検索

すべてのAVLツリーはBSTであるため、AVLツリーでの検索操作はBSTに似ています。検索する要素をルートノードと比較することから検索プロセスを開始します。 さらに、必要な要素のキー値に基づいて、ルートノードから左または右のサブツリーに移動し、プロセスを繰り返します。 必要な要素を見つけるか、ツリーを完全に探索するときに、検索プロセスを終了します。

AVL内の要素を検索するための時間計算量はです。ここで、AVLツリー内のノードの総数はです。

4.2. 挿入

AVLツリーでの挿入操作は、BST挿入と同様です。 ただし、AVLツリーには追加のステップがあります。 ツリーが常にバランスを保つように、挿入操作後に各ノードのバランス係数を計算する必要があります。挿入操作の手順について説明します。

ツリーが空の場合は、ルートに要素を挿入します。 ツリーが空でない場合は、最初に、挿入するノードの値を親ノードまたはルートノードと比較します。 比較に基づいて、右または左のサブツリーに移動し、新しいノードを挿入するための適切な場所を取得します。

挿入プロセスの後、各ノードのバランス係数を計算します。 いずれかのノードが不均衡な場合、ツリーが再び均衡するまで、要件に従っていくつかのローテーションを実行します。 AVLツリーへの挿入プロセスの時間計算量はです。

例を見てみましょう。 指定されたキー値を持つノードのセットをAVLツリーに挿入します。 最初、ツリーは空です。 ノードを1つずつ挿入します。

まず、キーが。のノードを挿入します。 これは、AVLツリーのルートノードになります。 次に、キーのあるノードを挿入し、続いてキーのあるノードを挿入します。 ノードを挿入した後、各ノードのバランス係数も計算します。

次に、キー値と:を含むノードを挿入しましょう。

今まで、バランスの取れたAVLツリーがあります。 したがって、ローテーションを実行する必要はありません。 キー値を持つ次のノードを挿入しましょう:

ご覧のとおり、Key-Valueを使用してノードを挿入すると、ツリーのバランスが崩れます。 したがって、ツリーのバランスを取り直すために、左回転を実行しました。 key-valueで次のノードを挿入しましょう:

AVLツリーはバランスが取れています。 最後に、key-valueで最後のノードを挿入しましょう:

値が。のノードを挿入した後、AVLツリーは不均衡になります。 したがって、最初に左回転を実行し、次に右回転を実行してAVLツリーのバランスを取りました。

4.3. 消す

AVLツリーでの削除操作は、BST削除と同様です。 ただし、ここでも、削除操作を実行した後、各ノードのバランス係数を計算する必要があります。 ノードを削除する場合は、最初にツリーを走査してノードの場所を見つけます。このプロセスは、AVLツリーまたはBSTでノードまたは要素を検索するのと同じです。

指定されたツリーで必要なノードを見つけたら、ノードを削除するだけです。 ノードの削除後、各ノードのバランス係数を計算します。 AVLツリーのバランスが崩れている場合は、要件に従ってローテーションを実行します。 AVLから要素を削除するための時間計算量はです。

削除の例を示すためにAVLツリーを使用しています。

ここで、たとえば、AVLツリーから次のノードを削除します。 最初にノードを削除し、次にノードを削除しましょう:

ノードとを削除した後、各ノードのバランス係数を計算しました。 さらに、すべてのノードのバランスが取れていることがわかります。 したがって、ここでローテーションを実行する必要はありません。 次のノードを削除しましょう:

値が。のノードを削除すると、AVLのバランスが崩れていることがわかります。 したがって、AVLツリーのバランスをとるために、ここで右回転を実行する必要があります。

5. 赤黒木(RBT)の紹介

また、自己平衡二分探索木でもあります。 したがって、二分探索木のすべての前提条件に従います。 赤黒木は、ほぼ高さのバランスが取れた木としても知られています。

赤黒木データ構造には、赤と黒の2種類のノードがあります。 さらに、ツリー操作を実行した後、赤黒木のバランスをとるために、いくつかの回転を適用し、ノードの色を変更する必要がある場合があります。 赤黒木データ構造におけるツリー操作の複雑さは、AVLツリーと同じです。

赤黒木は、AVL木と同じ複雑さの平衡二分探索木です。 したがって、なぜ追加のツリーデータ構造が必要なのですか?説明しましょう。

前に説明したように、AVLツリーのツリーのバランスをとるために回転を適用する必要があります。 何度か回転させなければならない状況に直面することがよくあります。 回転が多いほど、処理も多くなります。 したがって、処理は必要な回転数に基づいて異なります。 ただし、赤黒木では、ツリーのバランスを取るために最大2回転が必要になる場合があります。したがって、実装と実行を容易にするために赤黒木が導入されています。

6. 赤黒木の特性

赤黒木では、各ノードは黒または赤で色分けされています。 ルートノードとリーフノードは通常、黒で表示されます。 さらに、ノードが赤の場合、その子ノードは黒に着色する必要があります。 RBTツリーを見てみましょう。

RBTにノードがある場合、RBTの高さは最大でになります。RBTの高さは、このツリーデータ構造が異なるため、重要なプロパティです。 AVLツリーから。 すべての操作の後、いくつかの回転を実行し、現在のツリーに従ってノードの色を設定する必要があります。 RBTはBSTと同じ構造ですが、ノードのカラーコードを格納するために追加のビットを使用します。

RBT内のすべてのノードには、ノードの値、左側のサブツリーポインター、右側のサブツリーポインター、およびノードのカラーコードを格納する変数の4つのデータがあります。

7. 赤黒木の操作

RBTでの検索は、BSTでの任意の要素の検索と同じです。 任意の要素を検索するには、ルートノードから開始し、指定された要素のキー値を比較してツリーに移動します。 任意の要素を検索する時間計算量はです。

RBTでの挿入操作は、BSTでの挿入のいくつかのルールに従います。 ツリーが空の場合、ルートノードになるため、要素を挿入して黒にする必要があります。 ツリーが空でない場合は、新しいノードを作成して赤に色付けします。

さらに、ツリーに要素を挿入する場合は常に、新しいノードのデフォルトの色は常に赤になります。これは、子ノードと親ノードの色が赤であってはならないことを意味します。 隣接する赤いノードがないことを確認するだけです。

要素を挿入した後、挿入された要素の親ノードが黒の場合、追加のプロセスを実行する必要はありません。 バランスの取れたRBTになります。 ただし、挿入された要素の親が赤の場合は、親の兄弟ノードの色を確認する必要があります。 したがって、親ノードと同じレベルにあるノードの色を確認する必要があります。

RBTでの削除操作は、BSTでの削除と同じです。 まず、目的のノードが見つかるまでツリーを走査する必要があります。 ノードを見つけるとすぐに、RBTからノードを削除します。

赤いノードを削除しても、RBTの条件に違反することはありません。したがって、BSTのようにノードを削除するだけで済みます。 ただし、黒のノードを削除すると、RBTの条件に違反する可能性があります。したがって、黒のノードを削除した後、RBTのバランスを取り戻すために、回転や色の変更などのアクションを実行する必要があります。 。

赤黒木とその操作の詳細については、赤黒木入門の例を参照してください。

8. 違い

次に、AVLと赤黒木データ構造の主な違いを見てみましょう。

9. 結論

このチュートリアルでは、AVLと赤黒木のデータ構造について説明しました。 プロパティと操作を例とともに示しました。

最後に、それらの間のコアの違いを調査しました。