バランスのとれたバイナリ ツリーは、高さバランスのとれたツリーとも呼ばれます。左のサブツリーと右のサブツリーの高さの差が m 以下の場合、これは二分木として定義されます。ここで、m は通常 1 に等しいです。木の高さは、二分木間の最長パス上のエッジの数です。ルートノードとリーフノード。

上の木は、 二分探索木 。二分探索木は、左側の各ノードが親ノードよりも低い値を持ち、右側のノードが親ノードよりも高い値を持つ木です。上記ツリーにおいて、n1 はルート ノード、n4、n6、n7 はリーフ ノードです。 n7 ノードはルート ノードから最も遠いノードです。 n4 と n6 には 2 つのエッジが含まれており、ルート ノードと n7 ノードの間には 3 つのエッジが存在します。 n7 はルート ノードから最も遠いため、n7 はルート ノードから最も遠いです。したがって、上記の木の高さは 3 です。

ここで、上のツリーのバランスが取れているかどうかを見てみましょう。左側のサブツリーにはノード n2、n4、n5、および n7 が含まれ、右側のサブツリーにはノード n3 および n6 が含まれます。左側のサブツリーには 2 つのリーフ ノード、つまり n4 と n7 があります。ノード n2 と n4 の間には 1 つのエッジがあり、ノード n7 と n2 の間には 2 つのエッジがあります。したがって、ノード n7 はルート ノードから最も遠いです。左側のサブツリーの高さは 2 です。右側のサブツリーにはリーフ ノード (n6) が 1 つだけ含まれており、エッジも 1 つだけあります。したがって、右側のサブツリーの高さは 1 です。左側のサブツリーと右側のサブツリーの高さの差は 1 です。値 1 が得られたので、上のツリーは高さのバランスがとれたツリーであると言えます。この高さの差を計算するプロセスは、n2、n3、n4、n5、n6、n7 などのノードごとに実行する必要があります。各ノードを処理すると、k の値が 1 以下であることがわかり、上記のツリーはバランスが取れていると言えます。 二分木 。

上記のツリーでは、n6、n4、および n3 はリーフ ノードであり、n6 はルート ノードから最も遠いノードです。ルート ノードとリーフ ノードの間には 3 つのエッジが存在します。したがって、上記のツリーの高さは 3 です。 n1 をルート ノードと考えると、左側のサブツリーにはノード n2、n4、n5、および n6 が含まれ、サブツリーにはノード n3 が含まれます。左側のサブツリーでは、n2 がルート ノード、n4 と n6 がリーフ ノードです。 n4 ノードと n6 ノードのうち、n6 はルート ノードから最も遠いノードであり、n6 には 2 つのエッジがあります。したがって、左側のサブツリーの高さは 2 です。右側のサブツリーには左右に子があります。したがって、右側のサブツリーの高さは 0 です。左側のサブツリーの高さは 2、右側のサブツリーの高さは 0 であるため、左側のサブツリーと右側のサブツリーの高さの差は 2 です。定義によれば、差は左のサブツリーと右のサブツリーの高さの差は 1 を超えてはなりません。この場合、差は 2 となり、1 より大きくなります。したがって、上記の二分木は不平衡二分探索木です。

なぜバランスの取れた二分木が必要なのでしょうか?

例を通して、バランスのとれたバイナリ ツリーの必要性を理解しましょう。

上のツリーは、すべての左側のサブツリー ノードがその親ノードより小さく、すべての右側のサブツリー ノードがその親ノードより大きいため、二分探索ツリーです。上記のツリーで値 79 を見つけたいとします。まず、ノード n1 の値を 79 と比較します。値 79 は 35 に等しくなく、35 より大きいため、ノード n3、つまり 48 に移動します。値 79 は 48 に等しくなく、79 は 48 より大きいため、右に移動します。ノード 48 の右の子の値は 79 で、検索対象の値と同じです。要素 79 を検索するのに必要なホップ数は 2 で、任意の要素を検索するのに必要な最大ホップ数は 2 です。要素を検索する平均ケースは O(logn) です。

上のツリーは、すべての左側のサブツリー ノードがその親ノードより小さく、すべての右側のサブツリー ノードがその親ノードより大きいため、二分探索ツリーでもあります。上のツリーで値 79 を見つけたいとします。まず、値 79 をノード n4、つまり 13 と比較します。値 79 は 13 より大きいため、ノード 13 の右側の子、つまり n2 (21) に移動します。ノード n2 の値は 21 で、79 より小さいため、再びノード 21 の右に移動します。ノード 21 の右の子の値は 29 です。値 79 は 29 より大きいため、右に移動します。ノード 29 の子。ノード 29 の右の子の値は 35 で、79 より小さいため、ノード 35 の右の子、つまり 48 に移動します。値 79 は 48 より大きいため、右の子に移動します。ノード 48 の右の子ノードの値は 79 で、検索対象の値と同じです。この場合、要素の検索に必要なホップ数は 5 です。この場合、最悪のケースは O(n) です。

ノードの数が増えると、ツリー図 2 で使用する式よりもツリー図 1 で使用する式の方が効率的になります。上記の両方のツリーで利用可能なノードの数が 100,000 であると仮定します。ツリー ダイアグラム 2 内の要素を検索するのにかかる時間は 100,000 μs ですが、ツリー ダイアグラム内の要素を検索するのにかかる時間は log(100,000) で、これは 16.6 μs です。上の 2 つの木の間では、時間に大きな違いがあることがわかります。したがって、バランスバイナリツリーは線形ツリーデータ構造よりも高速な検索を提供すると結論付けます。