スプレイ ツリーは、自己平衡型または自己調整型の二分探索ツリーです。つまり、スプレイ ツリーは二分探索木の変形であると言えます。二分探索木について知っておくべきスプレイ ツリーの前提条件。
すでに知られているように、あらゆる場合における二分探索木の時間計算量は異なります。平均的な場合の二分探索木の時間計算量は次のとおりです。 O(ログン) 最悪の場合の時間計算量は O(n) です。二分探索木では、左側のサブツリーの値はルート ノードより小さく、右側のサブツリーの値はルート ノードより大きくなります。このような場合、時間計算量は次のようになります。 O(ログン) 。二分木が左または右に歪んでいる場合、時間計算量は O(n) になります。歪度を制限するには、 AVL と赤黒ツリー が入ってきて、 O(ログン ) すべてのケースにおけるすべての操作の時間計算量。また、より実践的な実装を行うことで、今回の複雑さを改善することもできるので、新しいツリー スプレイ ツリーとは何ですか?
スプレイツリーは自己バランスを保つ木ですが、 AVL および Red-Black ツリーも自己バランス型ツリーです。スプレーツリーがユニークな2本の木である理由。これをユニークにするもう 1 つの特性は、広がりです。
スプレイ ツリーには、スプレイ ツリーと同じ操作が含まれます。 二分探索木 つまり、挿入、削除、検索ですが、もう 1 つの操作、つまり、拡張も含まれています。それで。スプレー ツリー内のすべての操作の後に、スプレーが行われます。
スプレー ツリーは厳密にバランスの取れたツリーではありませんが、おおよそバランスの取れたツリーです。スプレイツリーでの検索操作を理解しましょう。
以下に示すように、ツリー内の 7 つの要素を検索するとします。
スプレイ ツリー内の要素を検索するには、まず標準の二分探索ツリー操作を実行します。 7 は 10 より小さいため、ルート ノードの左側に来ます。検索操作を実行した後、展開を実行する必要があります。ここでの拡張とは、要素に対して実行している操作が、いくつかの再配置を実行した後にルート ノードになることを意味します。ツリーの再配置はローテーションによって行われます。
注: スプレイ ツリーは、要素に対して実行される操作によってツリーが再配置され、操作が実行された要素がツリーのルート ノードになる自己調整ツリーとして定義できます。
回転
スプレーに使用される回転には 6 種類があります。
- ジグ回転（右回転）
- ザグ回転（左回転）
- ジグザグ (ジグに続いてザグ)
- ザグジグ (ザグの後にジグが続く)
- ジグジグ（右2回転）
- ザグザグ（左2回転）
回転の種類を選択するために必要な要素
回転のタイプを選択するために使用される要素は次のとおりです。
- 回転させようとしているノードには祖父母がありますか?
- ノードは親の左または右の子ですか?
- ノードは祖父母の左の子ですか、それとも右の子ですか?
ローテーションのケース
ケース 1: ノードに祖父母がなく、ノードが親の右側の子である場合は、左回転を実行します。それ以外の場合は、右回転が実行されます。
ケース 2: ノードに祖父母がある場合は、次のシナリオに基づきます。回転が実行されます。
シナリオ 1: ノードが親の右側にあり、親もその親の右側にある場合、 ジグジグ右右回転 は発表された。
シナリオ 2: ノードが親の左側にあるが、親がその親の右側にある場合、 ジグザグ右左回転 は発表された。
シナリオ 3: ノードが親の右側にあり、親がその親の右側にある場合、 ジグジグ左左回転 は発表された。
シナリオ 4: ノードが親の右側にあるが、親がその親の左側にある場合、 ジグザグの左右回転 は発表された。
ここで、例を使用して上記の回転を理解しましょう。
ツリーを再配置するには、いくつかの回転を実行する必要があります。スプレイ ツリーの回転の種類は次のとおりです。
ジグ回転は、検索対象の項目がルート ノードまたはルート ノードの子 (つまり、左または右の子) である場合に使用されます。
検索中にスプレイ ツリーに存在する可能性があるケースは次のとおりです。
ケース 1: 検索項目がツリーのルート ノードの場合。
ケース 2: 検索項目がルート ノードの子の場合、次の 2 つのシナリオが存在します。
- 子が左の子の場合、ジグ右回転として知られる右回転が実行されます。
- 子が右側の子の場合、ジグ左回転として知られる左回転が実行されます。
例を通して上記の 2 つのシナリオを見てみましょう。
以下の例を考えてみましょう。
上の例では、ツリー内の 7 つの要素を検索する必要があります。以下の手順に従います。
ステップ1： まず、7 をルート ノードと比較します。 7 は 10 より小さいため、ルート ノードの左側の子になります。
ステップ2： 要素が見つかったら、展開を実行します。以下に示すように、7 がツリーのルート ノードになるように右回転が実行されます。
別の例を考えてみましょう。
上の例では、ツリー内の 20 個の要素を検索する必要があります。以下の手順に従います。
ステップ1： まず、20 をルート ノードと比較します。 20 はルート ノードより大きいため、ルート ノードの右側の子になります。
ステップ2： 要素が見つかったら、展開を実行します。 20要素がツリーのルートノードとなるように左回転が行われます。
検索対象のアイテムに祖父母だけでなく親も含まれる場合があります。この場合、広げるために 4 回転を実行する必要があります。
例を通してこのケースを理解しましょう。
以下に示すように、ツリー内の 1 つの要素を検索する必要があるとします。
ステップ1： まず、1 要素を検索するために、標準的な BST 検索操作を実行する必要があります。 1 は 10 および 7 より小さいため、ノード 7 の左側にあります。したがって、要素 1 には親 (7) と祖父母 (10) があります。
ステップ2： このステップでは、スプレイングを実行する必要があります。いくつかの回転を利用して、ノード 1 をルート ノードとして作成する必要があります。この場合、単純にジグまたはザグ回転を実行することはできません。ジグジグ回転を実装する必要があります。
ノード 1 をルート ノードとして作成するには、ジグジグ回転と呼ばれる 2 つの右回転を実行する必要があります。右回転を実行すると、以下の図に示すように、10 が下に移動し、ノード 7 が上に来ます。
再度、ジグ右回転を実行すると、以下に示すように、ノード 7 が下に移動し、ノード 1 が上に来ます。
上の図でわかるように、ノード 1 がツリーのルート ノードになっています。したがって、検索は完了します。
以下のツリーで 20 を検索するとします。
20 個を検索するには、左回転を 2 回実行する必要があります。 20 個のノードを検索するために必要な手順は次のとおりです。
ステップ1： まず、標準的な BST 検索操作を実行します。 20 は 10 および 15 より大きいため、ノード 15 の右側になります。
ステップ2： 2 番目のステップは、スプレイングを実行することです。この場合、2 回の左回転が実行されます。最初の回転では、以下に示すように、ノード 10 が下に移動し、ノード 15 が上に移動します。
2 番目の左回転では、以下に示すように、ノード 15 が下に移動し、ノード 20 がツリーのルート ノードになります。
私たちが観察したように、2 つの左回転が実行されます。したがって、ジグジグ左回転として知られています。
これまで、親と祖父母の両方が RR または LL の関係にあると読みました。次に、親と祖父母の間の RL または LR 関係を見てみましょう。
例を通してこのケースを理解しましょう。
以下に示すツリー内の 13 個の要素を検索するとします。
ステップ1： まず、標準的な BST 検索操作を実行します。 13 は 10 より大きく 15 より小さいため、ノード 13 はノード 15 の左の子になります。
ステップ2： ノード 13 はノード 15 の左側にあり、ノード 15 はノード 10 の右側にあるため、RL 関係が存在します。まず、ノード 15 で右回転を実行すると、以下に示すように、15 は下に移動し、ノード 13 は上に移動します。
それでも、ノード 13 はルート ノードではなく、13 はルート ノードの右側にあるため、ザグ回転として知られる左回転を実行します。以下に示すように、ノード 10 が下に移動し、13 がルート ノードになります。
上のツリーでわかるように、ノード 13 がルート ノードになっています。したがって、検索は完了します。この場合、最初にジグ回転を実行し、次にザグ回転を実行しました。したがって、それはジグザグ回転として知られています。
例を通してこのケースを理解しましょう。
以下に示すように、ツリー内の 9 つの要素を検索するとします。
ステップ1： まず、標準的な BST 検索操作を実行します。 9 は 10 より小さいですが 7 より大きいため、ノード 7 の右側の子になります。
ステップ2： ノード 9 はノード 7 の右側にあり、ノード 7 はノード 10 の左側にあるため、LR 関係が存在します。まず、ノード 7 で左回転を実行します。以下に示すように、ノード 7 は下に移動し、ノード 9 は上に移動します。
それでもノード 9 はルート ノードではなく、9 はルート ノードの左側にあるため、ジグ回転として知られる右回転を実行します。右回転を実行すると、以下に示すように、ノード 9 がルート ノードになります。
上のツリーでわかるように、ノード 13 はルート ノードです。したがって、検索は完了します。この場合、最初にザグ回転（左回転）を実行し、次にジグ回転（右回転）を実行するため、ザグジグ回転と呼ばれます。
スプレイツリーのメリット
- スプレイ ツリーでは、余分な情報を保存する必要はありません。対照的に、AVL ツリーでは、余分なスペースを必要とする各ノードのバランス係数を保存する必要があり、赤黒ツリーでは、ノードの色 (赤または黒) を示す情報を 1 ビット余分に保存する必要もあります。
- これは、さまざまな実用的なアプリケーション向けの最も高速なタイプの二分探索ツリーです。で使用されています Windows NT および GCC コンパイラ 。
- 頻繁にアクセスされるノードがルート ノードに近づくため、スプレイ ツリー内の要素にすばやくアクセスできるため、パフォーマンスが向上します。最近アクセスしたデータがキャッシュに保存されるため、キャッシュの実装で使用されます。これにより、データにアクセスするためにメモリにアクセスする必要がなくなり、時間が短縮されます。
スプレイツリーの欠点
スプレイ ツリーの主な欠点は、ツリーが厳密にはバランスが取れていない、つまり、おおよそバランスが取れていることです。場合によっては、スプレイ ツリーが線形であるため、O(n) 時間の計算量がかかります。
スプレイツリーでの挿入操作
の中に 挿入 操作では、まずツリーに要素を挿入し、次に挿入された要素に対して展開操作を実行します。
15、10、17、7
ステップ1： まず、ツリーにノード 15 を挿入します。挿入後はスプレイングを行う必要があります。 15 はルート ノードなので、拡張を実行する必要はありません。
ステップ2： 次の要素は 10 です。10 は 15 より小さいため、以下に示すように、ノード 10 はノード 15 の左側の子になります。
さて、私たちはパフォーマンスします 広がる 。ルート ノードとして 10 を作成するには、以下に示すように右回転を実行します。
ステップ 3: 次の要素は 17 です。 17 は 10 および 15 より大きいため、ノード 15 の右側の子になります。
では、散布を行っていきます。 17 には祖父母だけでなく親もいますので、ジグジグ回転を実行します。
上の図では、17 がツリーのルート ノードになることがわかります。したがって、挿入は完了します。
ステップ 4: 次の要素は 7 です。7 は 17、15、10 より小さいため、ノード 7 は 10 の左の子になります。
次に、ツリーを展開する必要があります。 7 には親だけでなく祖父母もあるため、以下に示すように 2 つの右回転を実行します。
それでもノード 7 はルート ノードではなく、ルート ノードの左側の子、つまり 17 です。 したがって、次に示すように、もう 1 回右回転を実行して、ノード 7 をルート ノードにする必要があります。
挿入操作のアルゴリズム
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
上記のアルゴリズムでは、T はツリー、n は挿入したいノードです。ルート ノードのアドレスを含む一時変数を作成しました。 temp の値が NULL になるまで while ループを実行します。
挿入が完了すると、拡張が実行されます
スプレー操作のアルゴリズム
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
上記の実装では、x は回転が実行されるノードであり、y はノード x の左の子です。
left.rotation(T, x) の実装
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
上記の実装では、x は回転が実行されるノードであり、y はノード x の右側の子です。
スプレイツリーの削除
ご存知のとおり、スプレイ ツリーは二分探索ツリーの変形であるため、スプレイ ツリーでの削除操作は BST と似ていますが、唯一の違いは、スプレイ ツリーでは削除操作の後にスプレイ操作が行われることです。
削除の種類:
スプレイ ツリーには 2 種類の削除があります。
- ボトムアップスプレー
- トップダウンの広がり
ボトムアップスプレー
ボトムアップ展開では、まずツリーから要素を削除し、次に削除されたノードに対して展開を実行します。
Splay ツリーの削除について理解しましょう。
以下に示すツリーから 12、14 を削除するとします。
Javaのプリミティブデータ型
- まず、標準の BST 削除操作を実行して 12 個の要素を削除します。 12 はリーフ ノードなので、単純にツリーからノードを削除します。
まだ削除は完了していません。削除されたノードの親、つまり 10 を表示する必要があります。 スプレイ(10) 木の上で。上のツリーでわかるように、10 はノード 7 の右側にあり、ノード 7 はノード 13 の左側にあります。したがって、最初にノード 7 で左回転を実行し、次にノードで右回転を実行します。以下に示すように、13:
それでも、ノード 10 はルート ノードではありません。ノード 10 はルート ノードの左側の子です。したがって、以下に示すように、ルート ノード (つまり 14) で右回転を実行して、ノード 10 をルート ノードにする必要があります。
- ここで、以下に示す 14 番目の要素をツリーから削除する必要があります。
ご存知のとおり、内部ノードを単純に削除することはできません。次のいずれかを使用してノードの値を置き換えます。 順番に前任者 または 順番の後継者 。値を右のサブツリーに存在する最小値に置き換える順序後続法を使用するとします。ノード 14 の右側のサブツリーの最小値は 15 なので、値 14 を 15 に置き換えます。ノード 14 はリーフ ノードになるため、以下に示すように単純に削除できます。
それでも削除は完了しません。もう 1 つ操作を実行する必要があります。つまり、削除されたノードの親をルート ノードとして作成する必要がある拡張です。削除前は、ノード 14 の親がルート ノード、つまり 10 であったため、この場合は拡張を実行する必要があります。
トップダウンの広がり
トップダウン展開では、まず削除対象の展開を実行してから、ツリーからノードを削除します。要素が削除されたら、結合操作を実行します。
例を通してトップダウンの広がりを理解しましょう。
以下に示すツリーから 16 を削除するとします。
ステップ1： トップダウン スプレイングでは、最初にノード 16 でスプレイングを実行します。ノード 16 には親と祖父母の両方があります。ノード 16 はその親の右側にあり、親ノードもその親の右側にあるため、これはザグザグの状況です。この場合、以下に示すように、まずノード 13 で左回転を実行し、次にノード 14 で左回転を実行します。
ノード 16 はまだルート ノードではなく、ルート ノードの右側の子であるため、ノード 12 に対して左回転を実行してノード 16 をルート ノードにする必要があります。
ノード 16 がルート ノードになったら、ノード 16 を削除し、以下に示すように 2 つの異なるツリー、つまり左のサブツリーと右のサブツリーを取得します。
ご存知のとおり、左側のサブツリーの値は常に右側のサブツリーの値よりも小さくなります。左側のサブツリーのルートは 12、右側のサブツリーのルートは 17 です。最初のステップは、左側のサブツリーで最大の要素を見つけることです。左側のサブツリーでは、最大要素は 15 であるため、15 に対して拡張操作を実行する必要があります。
上のツリーでわかるように、要素 15 には祖父母だけでなく親もあります。ノードはその親の右側にあり、親ノードもその親の右側にあるため、以下に示すように、ノード 15 をルート ノードにするために 2 回の左回転を実行する必要があります。
ツリー上で 2 回の回転を実行すると、ノード 15 がルート ノードになります。ご覧のとおり、15 の右の子は NULL であるため、以下に示すように 15 の右部分にノード 17 を接続します。この操作は、 参加する 手術。
注: 削除される要素がスプレイ ツリーに存在しない場合は、スプレイが実行されます。拡張は、NULL に達する前に最後にアクセスされた要素に対して実行されます。
削除操作のアルゴリズム
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
上記のアルゴリズムでは、まずルートが Null かどうかを確認します。ルートが NULL の場合は、ツリーが空であることを意味します。ツリーが空でない場合は、削除される要素に対して展開操作を実行します。展開操作が完了したら、ルート データと削除する要素を比較します。両方が等しくない場合は、その要素がツリー内に存在しないことを意味します。それらが等しい場合、次のようなケースが発生する可能性があります。
ケース1 : ルートの左側は NULL、ルートの右側はルート ノードになります。
ケース2 : 左と右の両方が存在する場合、左のサブツリーの最大の要素を展開します。展開が完了すると、最大の要素が左側のサブツリーのルートになります。右のサブツリーは、左のサブツリーのルートの右の子になります。