序文
この記事は、バイナリーツリーの概念をすでに理解している読者をデフォルトとしています。そうでない場合は、バイナリーツリーをクリックしてバイナリーツリーの詳細を見ることができます。
二分探索木
BST(Binary Search Tree)目標は、ルックアップのパフォーマンスを向上させ、平均して、最悪の場合、lognレベルで、バイナリ・ルックアップに近づけることです。
その特徴は
- その左サブツリーが空でない場合、左サブツリー内のすべてのノードの値はそのルートノードの値より小さい。
- 右のサブツリー内のすべてのノードの値がルートノードの値より大きい場合
- その左と右のサブツリーもそれぞれバイナリ探索木です。
図はバイナリ探索木を示しています。
平衡二分木
定義
バランスド・バイナリー・ツリーはAVLツリーとも呼ばれ、バイナリー・サーチ・ツリーを基本として、バランスド・バイナリー・ツリーも以下の条件を満たす必要があります。
- 左右のサブツリーの高さの差の絶対値が1を超えないこと
- 左サブツリーも右サブツリーもバランスの取れたバイナリツリーです。
バランス係数：左の高さから右の高さを引いたもの。 従って、バランス2分木とは、各ノードのバランス係数が1、-1、0のいずれか、または各ノードの左サブツリーと右サブツリーの高さの差が最大でも1である2進ソート木のことです。つまり、バランス2分木は2分探索木でなければなりません。 平衡二分木の目的は、二分探索木のレベルを下げ、探索速度を向上させることであり、一般的な実装方法は、AVL、赤黒木、スケープゴート木、Treap、ストレッチ木などです。
Q:平衡二分木の定義を理解しました。では、次の図にある2つの木を見て、平衡二分木を考えてみましょうか？
木の右側のバランス係数は2なので、答えは左側です。
この時、私はいくつかのパートナーは、検索でバイナリ検索ツリーを使用することができ、なぜあなたはバランスの取れたバイナリツリーを行う必要がある、尋ねると思います？バランス二分木は何か利点がありますか？
バランス二分木を使う理由
一般的な二項探索木の場合、その期待される高さはlog2nであることが知られており、その演算の時間複雑性もこれによって決まります。しかし、ある極端なケースでは、バイナリ探索木は近似連鎖または連鎖に縮退し、その場合、その演算の時間複雑度は線形、すなわちO(n)に縮退します。これは、二項探索木をランダム化によって構築することで可能な限り回避することができますが、何度も操作しているうちに、削除するノードの後継は、削除するときに必ず自分自身を置き換えるノードが選ばれるため、木が左に沈む分、常に右にあるノードの数が減ってしまいます。また、ツリーのバランスが崩れ、操作の時間的複雑さが増します。例えば、データ1,2,3,4,5,6の集合を、それぞれ空のバイナリ・ルックアップ木とAVL木に順次挿入した結果を以下に示します：
上の図からわかるように、同じノードを異なる挿入方法で挿入した場合、木の高さは異なります。特に、正順に挿入されたノードが多い場合、バイナリ木の高さはO(N)になりますが、AVL木の場合はそうではなく、常にO(lgN)の高さになります。高さが小さいほど、木に対するいくつかの基本的な操作の時間複雑度は小さくなります。これがAVL木を導入した理由です。
この時、小さなパートナーは、AVLツリー構造をどのように挿入するのですか？これは、スピンを言うために次のとおりです。
スピン
ツリースピンの一回転と二回転。 まず、一回転 ---> 右回転の場合から見てみましょう。
上の図から、我々は、挿入ツリーがAVLツリーであることがわかりますが、挿入後、ノードTの左と右のサブツリーの高さの差の絶対値は、もはや< 1.この時点で、AVLツリーのバランスが破壊され、それが回転する必要があります。上の図から見ることができる左のサブツリーのノードTの左ノードに要素の挿入を行うには、左左の場合は、右回転を実施する必要がありますこのケースと呼ばれます。具体的な回転の手順は
同時に Y は T の左の子に置かれます。この結果、新しいAVLツリーができあがります：
頭のいい人は、右手スピンを見れば左手スピンがどうできるかがわかると思います。ですから、下の写真を見て、左手スピンのやり方を考えてみてください。
次に、なぜダブルスピンの話をするのですか？
二重回転の最初のケース→左右回転
上の図は、Tノードの左ノードの右サブツリーに要素を挿入すると、ルートTを持つツリーの左サブツリーと右サブツリーの高さの差の絶対値が1以下になることを示しています。以下に示すように、2回目の回転を行う必要があります。
二重回転の2つ目のケース→左右回転
