二分探索ツリーと AVL ツリー |違いは何ですか?

二分探索ツリーと AVL ツリーの違いについて知る前に、二分探索ツリーと AVL ツリーについて別々に知っておく必要があります。

二分探索木とは何ですか?

の二分探索木です木バイナリツリー。ご存知のとおり、そのツリーには「n」個の子を持つことができます。バイナリツリーには最大 2 つの子を含めることができます。したがって、二分木の制約は二分探索木にも適用されます。二分探索ツリー内の各ノードには最大 2 つの子が必要です。言い換えれば、二分探索木は二分木の変形であると言えます。

二分探索ツリーも二分探索のプロパティに従います。二分探索では、配列内のすべての要素がソートされた順序になっている必要があります。二分探索で中央の要素を計算します。中央の要素の左側には中央の値より小さい値が含まれ、中央の要素の右側には中央の値より大きい値が含まれます。

二分探索木では、中央の要素がルートノードになり、右側の部分が右側のサブツリーになり、左側の部分が左側のサブツリーになります。したがって、二分探索木は次のものを組み合わせたものであると言えます。 二分木 そして 二分探索 。

注: 二分探索ツリーは、左側のサブツリーのすべての要素がルートノードより小さく、右側のサブツリーのすべての要素がルートノードより大きい二分木として定義できます。

二分探索木の時間計算量

二分探索木がほぼ平衡木である場合、すべての操作の時間計算量は次のようになります。 O(ログン) 検索が左または右のサブツリーに分割されるためです。

未定義の傾き

二分探索木が左または右に歪んでいる場合、すべての操作の時間計算量は次のようになります。 の上） n 個の要素までトラバースする必要があるためです。

AVL ツリーとは何ですか?

アン AVLツリーは、左右のサブツリーの高さの差が 1 を超えることができない自己平衡型二分探索木です。この差はバランス係数として知られています。 AVL ツリーでは、バランス係数の値は -1、0、または 1 のいずれかになります。

二分探索木の自己平衡化はどのように行われるのでしょうか?

ご存知のとおり、AVL ツリーは自己平衡型二分探索ツリーです。二分探索ツリーのバランスが取れていない場合は、再配置することで自動的にバランスを取ることができます。これらの再配置は、いくつかの回転を使用して行うことができます。

例を通してセルフバランスを理解してみましょう。

を挿入したいとします。 10、20、30 AVL ツリー内。

AVL ツリーに 10、20、30 を挿入する方法は次のとおりです。

挿入順が30、20、10の場合。

ステップ1： まず、以下に示すように二分探索ツリーを作成します。

ステップ2： 上の図では、ノード 30 のバランス係数が 2 であるため、ツリーのバランスが取れていないことがわかります。これを AVL ツリーにするには、いくつかの回転を実行する必要があります。以下に示すように、ノード 20 で右回転を実行すると、ノード 30 は下に移動し、ノード 20 は上に移動します。

Androidでアプリケーションを再表示する方法

見てわかるように、最終的なツリーは、二分探索ツリーとバランスのとれたツリーの特性に従っています。したがって、これは AVL ツリーです。

この場合、その木は、 アンバランスな木を放置し、 したがって、ノード上で右回転を実行します。

挿入順が10、20、30の場合。

ステップ1： まず、以下に示すように二分探索ツリーを作成します。

ステップ2： 上の図では、ノード 10 のバランス係数が -2 であるため、ツリーのバランスが取れていないことがわかります。これを AVL ツリーにするには、いくつかの回転を実行する必要があります。右アンバランスツリーなので左回転を行います。ノード 20 で左回転を実行すると、以下に示すように、ノード 20 は上に移動し、ノード 10 は下に移動します。

ご覧のとおり、最終的なツリーは、 二分探索ツリー そして バランスのとれた木 ;したがって、これは AVL ツリーです。

挿入順が30、10、20の場合

ステップ1： まず、以下に示すように二分探索ツリーを作成します。

アプレットアプレット

ステップ2： 上の図では、ルートノードのバランス係数が 2 であるため、ツリーのバランスが取れていないことがわかります。これを AVL ツリーにするには、いくつかの回転を実行する必要があります。上記のシナリオは、1 つのノードが親ノードの左側にあり、もう 1 つのノードが親ノードの右側にあるため、左右のバランスが取れていません。まず、左回転を実行します。回転はノード 10 と 20 の間で発生します。左回転後、以下に示すように、20 は上に移動し、10 は下に移動します。

それでも、ツリーのバランスが崩れているため、ツリーに対して正しい回転を実行します。ツリーに対して右回転が実行されると、ツリーは次のようになります。

上のツリーでわかるように、このツリーは二分探索ツリーとバランスツリーの特性に従っています。したがって、これは AVL ツリーです。

挿入順が10、30、20の場合

ステップ1： まず、以下に示すように、二分探索ツリーを作成します。

ステップ2： 上の図では、ルートノードのバランス係数が 2 であるため、ツリーのバランスが取れていないことがわかります。これを AVL ツリーにするには、いくつかの回転を実行する必要があります。上のシナリオは、1 つのノードが親ノードの右側にあり、別のノードが親ノードの左側にあるため、左右のバランスが取れていません。まず、ノード 30 と 20 の間で右回転を実行します。右回転後、以下に示すように、20 は上に移動し、30 は下に移動します。

それでも、上記のツリーはバランスが取れていないため、ノードで左回転を実行する必要があります。左回転が実行されると、以下に示すように、ノード 20 は上に移動し、ノード 10 は下に移動します。

上のツリーでわかるように、このツリーは二分探索ツリーとバランスツリーの特性に従っています。したがって、これは AVL ツリーです。

二分探索ツリーと AVL ツリーの違い

二分探索ツリー	AVLツリー
すべての二分探索ツリーは、両方のツリーに最大 2 つの子が含まれるため、二分ツリーです。	AVL ツリーには最大 2 つの子があるため、すべての AVL ツリーはバイナリツリーでもあります。
BSTにはバランスファクターなどの用語は存在しません。	AVL ツリーでは、各ノードにバランス係数が含まれており、バランス係数の値は -1、0、または 1 のいずれかである必要があります。
BST は平衡ツリーまたは不平衡ツリーのいずれかになる可能性があるため、すべての二分探索ツリーは AVL ツリーではありません。	AVL ツリーは BST のプロパティに従うため、すべての AVL ツリーは二分探索ツリーです。
二分探索ツリーの各ノードは、左サブツリー、ノード値、右サブツリーの 3 つのフィールドで構成されます。	AVL ツリーの各ノードは、左サブツリー、ノード値、右サブツリー、バランス係数の 4 つのフィールドで構成されます。
二分探索ツリーの場合、ツリーにノードを挿入する場合は、ノードの値をルートの値と比較します。ノードの値がルートノードの値より大きい場合、ノードは右側のサブツリーに挿入され、それ以外の場合、ノードは左側のサブツリーに挿入されます。ノードが挿入されると、挿入が完了するために高さのバランス係数をチェックする必要はありません。	AVL ツリーの場合、まずノードを挿入する適切な場所を見つけます。ノードが挿入されたら、各ノードのバランス係数を計算します。各ノードのバランス係数を満たしていれば挿入は完了します。バランス係数が 1 より大きい場合は、ツリーのバランスをとるためにいくつかの回転を実行する必要があります。
二分探索ツリーでは、ツリーの高さまたは深さは O(n) です。ここで、n は二分探索ツリー内のノードの数です。	AVL ツリーでは、ツリーの高さまたは深さは O(logn) です。
二分探索プロパティに従ってノードを挿入する必要があるため、実装は簡単です。	AVL ツリーでは、最初に AVL ツリーを構築し、次に高さのバランスをチェックする必要があるため、実装は複雑です。高さが不均衡な場合は、木のバランスを保つために回転を実行する必要があります。
BST はバランス係数の概念に従っていないため、バランスの取れたツリーではありません。	AVL ツリーは、バランス係数の概念に従っているため、高さのバランスがとれたツリーです。
BST では、ツリー内に利用可能なノードが多数ある場合、高さのバランスが取れていないため、検索は非効率的になります。	AVL ツリーでは、ツリー内のノードが多数ある場合でも、高さのバランスが取れているため、検索が効率的になります。