二分探索ツリーと 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 ツリーの違い