バランスの取れた木
1. 序章
このチュートリアルでは、バランスの取れた二分木について学びます。
特に、このようなツリーがなぜ役立つのかを見て、3つのタイプを調べます。 AVL木、赤黒木、および重量バランスのとれた木について説明します。 それぞれのタイプには、バランスの定義があります。
2. 二分探索木と二分探索木
ノード内の各ノードに最大で2つの子がある場合、ツリーバイナリと呼びます。子孫を持つノードの左の子は、ノードの左のサブツリーを形成します。 右のサブツリーの定義も同様です。
階層データの格納には適していますが、この一般的な形式の二分木は高速ルックアップを保証しません。 例として、次のツリーで番号9を検索してみましょう。
どちらのノードにアクセスしても、次に左または右のサブツリーをトラバースする必要があるかどうかはわかりません。 これは、ツリー階層が関係に従わないためです。
したがって、最悪の場合、検索には時間がかかります。ここで、はツリー内のノードの数です。
2.1. 二分探索木
この問題を解決するには、バイナリ検索ツリー（BST）と呼ばれる特殊なタイプのバイナリツリーを使用します。
ツリーが維持する順序により、ルックアップ中にツリーを整理できます。 を検索しているときにノードにアクセスするとします。 の左側のサブツリーを無視して、右側にのみ焦点を合わせることができます。これにより、検索が高速化されます。 上記の検索ツリーで9を見つける方法は次のとおりです。
ただし、検索の最悪の場合の複雑さは依然としてです。 ソートされた配列からツリーを構築する場合に発生します。この場合、ツリーには高さがあり、リンクリストに縮退します。 挿入と削除には検索が含まれるため、 BSTで一般的に実行されるすべての操作が最悪の場合です。したがって、複雑さを決定するのはツリーの高さです。 そこで、バランスの取れた木が登場します。 それらは特別なタイプの二分探索木です。
3. バランスの取れた木
バランスの取れたツリーは、ノード間の順序を維持するだけではない検索ツリーです。 また、高さを制御し、挿入または削除後も維持されるようにします。
これを行うには、ノードを追加または削除した後、バランスの取れたツリーがそれ自体を再バランスする必要があります。これにより、計算のオーバーヘッドが発生し、挿入と削除のアルゴリズムが複雑になります。 ただし、これは、高速な検索、挿入、および削除操作を備えた対数高さの検索ツリーに支払う準備ができている価格です。 この記事では、リバランスアルゴリズムについては説明しません。
そのような木にはいくつかの種類があります。 すべてのノードのバランスをとる必要がありますが、バランスの概念はタイプごとに異なります。
4. AVL木
AVLツリーでは、左右のサブツリーの高さが最大で1だけ異なる場合、ノードを平衡と呼びます。したがって、ルートを持つ検索ツリーは、すべてのノードが平衡である場合、AVLツリーになります。 AVLの意味で（高さ0の空の探索木は、簡単にバランスが取れています）：
(1)
例えば：
このバランスの定義の結果は、AVL木の高さが最悪の場合になるということです。
4.1. 高さが対数であることの証明
すべての兄弟サブツリーの高さが1つ異なる場合、AVLツリーのバランスは最小になります。例：
これがAVLツリーの最悪の場合の構造です。 バランスの最も悪いAVLツリーにノードを追加すると、非AVLツリーを取得するか、そのノードの1つにバランスを取ります。 ノードの削除についても同じことが言えます。 したがって、このようなAVLツリーは最小限です。同じ高さのAVLツリーでノードが少なくなることはありません。
ノードの左右のサブツリーを切り替えても、ツリーのバランスは保たれます。 したがって、左側のサブツリーにはより多くのノードがあると想定します。 次に、が高さのある最小AVLツリーのノード数である場合、次のようになります。
私たちの仮定から、私たちはそれを持っているので、：
高さのあるAVL構造にはノードが1つしかないため、、、および：
したがって、最悪のバランスの場合、AVL木の高さはです。 したがって、検索、挿入、削除などの操作には、対数的な時間計算量があります。
5. 赤黒木
赤黒木（RBT）も、兄弟サブツリーの高さのバランスを取ります。 ただし、 RBTは、赤いノードと黒いノードの2種類のノードを区別します。 RBTは、ノードからその子孫へのすべてのパスが同じ数の黒いノードを通過することを保証します。 また、ノードからその葉までの黒ノードの数（ノードを除く）は、ノードの黒の高さと呼ばれます。 RBT全体の黒の高さは、そのルートの黒の高さです。 たとえば（NULLを使用すると、スペースを節約するために単一のノードに合体したままになります）：
定義上、RBTは次の条件を満たす。
- すべてのノードは黒または赤のいずれかです。
- 根は黒です。
- 空のノード（NULLまたはNIL）はすべて黒です。
- ノードが赤の場合、その子は両方とも黒です。
- すべてのノードについて、それを含まない、その子孫の葉へのパスには、同じ数の黒いノードが含まれます。
いずれにせよツリーを再描画できるため、一部の作成者はルートを黒にする必要はありません。
RBTのプロパティにより、次のことが保証されます。
- ルートからリーフへのパスは、別のリーフへのパスの2倍を超える長さではありません。
- 木の高さはです。
5.1. Rbtの高さが
の黒の高さとします。 最初に、帰納法によって、をルートとするサブツリーに少なくとも内部ノードがあることを証明します。
基本ケースはです。これは、空のノード、つまりリーフであることを意味します。
それで、ベースケースについて説明しました。 帰納的ステップでは、私たちはとその子供たちに焦点を当てます。 それらの黒の高さは、それらの色に応じて、またはに等しくなります。 仮説によれば、それらにはそれぞれ少なくともノードが含まれています。 したがって、ルート化されたツリー全体には、少なくとも次の数のノードが含まれます。
ここで、ルートノードの高さとします。 赤のノードは黒の子しか持てないため、ルートからリーフまでのノードの少なくとも半分は黒である必要があります。したがって、ルートの黒の高さはです。
内部ノードに関する結果を使用すると、次のようになります。
ここでも、ノード数の対数として高さが増加することがわかります。
6. 重量バランスのとれた木
ウェイトバランスツリー（WBT）は、兄弟サブツリーの高さではなく、その中の葉の数のバランスを取ります。したがって、とをサブツリーとし、としましょう。 次の場合、バランスが取れていると言えます。
また、のすべての子孫が同じ条件を満たす必要があります。 これは、ツリー内のすべてのノードに次のようなものが存在することを示すのと同じです。
理由を理解するために、それを覚えて、派生に従ってみましょう。
したがって、これはWBTの再帰的定義です。
(2)
WBTの例を次に示します（リーフの数は各ノード内に書き込まれます）。
木の葉の数はその重さであるため、その名前が付けられています。 WBTの高さもによって制限されることを証明します。
6.1. 平衡二分木の高さが
それが高さがである最小のWBTであると仮定し、その中の葉の数を示しましょう。 WBTの定義から、のサブツリーにはノードのリーフのほとんどが含まれていることがわかります。 また、サブツリーの高さは最大でです。 だから、私たちは持っています：
、はツリー内のノードの数なので、次のようになります。
したがって、WBTの高さもノード数の対数です。
6.2. の価値
大きすぎると、リバランスができなくなる場合があります。 その値はである必要があります。
複雑なカスタムリバランスアルゴリズムを使用する準備ができている場合は、任意の小さいを使用できます。 ただし、を使用することをお勧めします。
7. 結論
この記事では、3種類のバランスの取れたツリーを紹介しました。それらは、AVLツリー、赤黒木、および重量バランスの取れたツリーでした。 さまざまなバランスの概念を使用して、検索、挿入、および削除の時間計算量を保証します。
ただし、樹木は、ノードの数で高さが対数のままになるように、変更時にバランスを取り直す必要があります。 追加の作業により、挿入と削除のアルゴリズムが複雑になり、速度が低下します。 ただし、操作の複雑さが残っているため、オーバーヘッドは報われます。
