ケープゴートの木

今日は、Scapegoatツリーと呼ばれるデータ構造に注目します。 知らない「Scapegoat」は、「scapegoat」と翻訳されます。これにより、構造の名前の文字通りの翻訳が奇妙になります。したがって、元の名前を使用します。 おそらくご存知のように 、さまざまな種類の検索ツリーがあり、それらはすべて同じ考え方に基づいています：「 しかし、行内のデータセット全体だけでなく、一部、できればサイズだけを要素全体で検索するのは良いことです注文ログ（N） 。」



このため、各頂点には、その子へのリンクと、どの子の頂点に移動する必要があるかを検索するときに明確になる何らかの種類の基準が格納されます。 対数時間では、ツリーのバランスが取れている場合（これがうまくいく、またはそうなる傾向がある場合）、つまり、 各頂点の各サブツリーの「高さ」がほぼ同じ場合。 ただし、各ツリータイプには独自のバランス調整方法があります。「赤」マーカーは、ツリーのバランスをとるタイミングと方法を示す上部の赤黒ツリーに格納されます。AVLツリーでは、検索操作中などにツリーを変更する



Scapegoatツリーには、ツリーのバランスをとるという問題を解決する独自のアプローチもあります。 他のすべてのケースに関しては、理想的ではありませんが、状況によっては非常に適切です。



Scapegoatツリーの利点は次のとおりです。

• 頂点に追加のデータを保存する必要はありません（つまり、赤黒、AVL、およびデカルトのツリーからメモリで勝ちます）
• 検索操作中にツリーのバランスを再調整する必要はありません（つまり、償却O（log N）のみが保証されるSplay-treeとは異なり、最大検索時間O（log N）を保証できます）
• O（log N）の挿入および削除操作の償却された複雑さは、基本的に他のツリータイプに似ています
• ツリーを構築するとき、特定の「厳密な」係数αを選択します。これにより、ツリーを「調整」し、変更操作を遅くすることで検索操作を高速化します。 データ構造を実装し、実際のデータのテスト結果とツリーの使用の詳細に従って係数を選択できます。

欠点は次のとおりです。

• 最悪の場合、ツリーの変更操作にはO（n）時間かかる可能性があります（償却された複雑さは依然としてO（log N）ですが、「不良」なケースに対する保護はありません）。
• ツリーでさまざまな操作の頻度を誤って評価し、係数αの選択を間違える可能性があります-結果として、頻繁に使用される操作は長時間機能し、めったに使用されない操作は迅速に機能しますが、それはどういうわけか良くありません。

Scapegoatツリーとは何か、その検索、挿入、削除操作を実行する方法を理解しましょう。



使用される概念（上記の表記の角括弧は、この値を明示的に格納することを意味します。つまり、O（1）を時間内に取ることができます。括弧は、値がプロセスで計算されることを意味します。計算する時間）

• T-したがって、ツリーを示します
• ルート[T]-ツリーTのルート
• 左[x]-頂点xの左「息子」
• 右[x]-頂点xの右の「息子」
• brother（x）-頂点xの兄弟（xと共通の親を持つ頂点）
• depth（x）-頂点xの深さ。 これは、そこからルートまでの距離です（rib骨の数）
• 高さ（T）はツリーTの深さです。これはツリーTの最も深い最上部の深さです。
• サイズ（x）は頂点xの重みです。 これは、そのすべての子頂点の数+ 1（彼女自身）です。
• size [T]-ツリーTのサイズ。これは、その中の頂点の数です（ルートの重み）

次に、Scapegoatツリーに必要な概念を紹介します。

• max_size [T]-ツリーの最大サイズ。 これは、最後のリバランス以降にサイズ[T]が取った最大値です。 リバランスが発生したばかりの場合、max_size [T] = size [T]
• 係数αは、[0.5; 1）、ツリーのバランス調整に必要な品質の程度を決定します。 左の息子の体重がα*サイズ（x）以下で、右の息子の体重がα*サイズ（x）以下の場合、頂点xは「α-weight-balanced」と呼ばれます。
  
  
  
  サイズ（左[x]）≤α*サイズ（x）
  
  サイズ（右[x]）≤α*サイズ（x）
  
  

この基準を理解してみましょう。 α= 0.5の場合、左側のサブツリーに、右側のサブツリーとまったく同じ数の頂点（±1）が必要です。 つまり これは実際には完全にバランスの取れたツリーの要件です。 α> 0.5の場合、「OK、バランスが完全ではなく、サブツリーの1つが他よりも多くの頂点を持つことができるようにします」と言います。 α= 0.6の場合、頂点xのサブツリーの1つは、サブツリーxのすべての頂点の最大60％を含むことができるため、頂点xは「α加重」と見なされます。 αが1になると、通常のリンクされたリストでさえ「重量でαバランス」と見なすことに実際に同意することがわかります。



次に、Scapegoatツリーで通常の操作がどのように実行されるかを見てみましょう。

ツリーの操作の開始時に、範囲[0.5;のパラメーターαを選択します。 1）。 また、2つの変数を開始して、サイズ[T]およびmax_size [T]の現在の値を格納し、それらをゼロにします。



検索する

そのため、Scapegoatツリーがあり、その中の要素を見つけたいと思います。 これはバイナリ検索ツリーであるため、検索は標準となります。ルートから目的の値と頂点を比較し、見つかった場合はそれを返し、頂点の値が小さい場合は、左のサブツリーで再帰的に検索します。 検索中にツリーは変更されません。



ご想像のとおり、検索操作の複雑さはαに依存し、次の式で表されます。



つまり もちろん、複雑さは対数ですが、対数の基礎は興味深いものです。 αが0.5に近い場合、2進数（またはほぼ2進数）の対数が得られます。これは、理想的な（またはほぼ完璧な）検索速度を意味します。 αが1に近い場合、対数の底は1になる傾向があります。これは、全体の複雑さがO（N）になる傾向があることを意味します。 ええ、そして誰も理想を約束しませんでした。



挿入

Scapegoatツリーへの新しい要素の挿入は、古典的な方法で始まります。検索することで、新しい頂点を掛ける場所を探し、それを掛けます。 このアクションが1つ以上のツリー頂点のαウェイトバランシングを混乱させる可能性があることは容易に理解できます。 そして、データ構造に名前を付けたものから始まります。「スケープゴート」（スケープゴートピーク）を探しています。これは、αバランスが失われ、そのサブツリーを再構築するピークです。 挿入されたばかりのピークは、バランスの損失のせいですが、「スケープゴート」になることはできません。まだ「子供」がいないため、バランスが完璧です。 したがって、この頂点からルートまでツリーを通過し、パスに沿った各頂点の重みを再カウントする必要があります。 このパスに沿って、重量によるαバランスの基準に違反する頂点がある場合、対応するサブツリーを完全に再構築して、重量によるαバランスを復元します。



途中で、いくつかの質問が発生します。

- そして、トップ「アップ」からルートに到達する方法は？ 親へのリンクを維持する必要がありますか？

-いいえ。 ツリーのルートから新しい頂点を挿入する場所に来たので、ルートから新しいトップまでのすべてを含むスタックがあります。 私たちはそれから両親を取ります。



- そして、ピークの「重量」を計算する方法 - ピーク自体にそれを保存しませんか？

-いいえ、保存しません。 新しい頂点の場合、重み=1。親の場合、重み= 1（新しい頂点の重み）+ 1（親自体の重み）+サイズ（兄弟（x））。



- さて、大丈夫ですが、サイズの計算方法（兄弟（x））？

-再帰的に。 はい、O（サイズ（brother（x）））時間かかります。 最悪の場合、ツリーの半分の重みを計算する必要があるかもしれないことを理解します-最悪の場合、非常に複雑なO（N）が表示されます。 しかし、α-weight-balancedtreeのサブツリーをバイパスするため、操作の償却された複雑さがO（log N）を超えないことが示されます。



- しかし、αバランスに違反しているいくつかのピークがある可能性があります-どうすればよいですか？

-簡単な答え：どれでも選択できます。 長い答え：データ構造を説明している元の文書には、「特定のスケープゴート」（それは用語です！）を選択する方法に関するいくつかの発見的手法がありますが、実際には「そうして、このようにして、それは良いですが、理由を説明することはできません。」



- そして、見つかったScapegoatピークのバランスを取り直す方法は？

-2つの方法があります：些細な方法と少しトリッキーです。

些細なリバランス

1. 順序探索を使用して 、Scapegoat頂点のサブツリー全体（その頂点を含む）をバイパスします。出力では、ソートされたリスト（バイナリ検索ツリーを走査する順序プロパティ）を取得します。
2. このセグメントの中央値を見つけ、サブツリーのルートとして一時停止します。
3. 「左」および「右」のサブツリーについて、同じ操作を再帰的に繰り返します。

このすべてにはO（サイズ（Scapegoat-vertex））時間と同じ量のメモリが必要であることがわかります。

少し難しいリバランス

リバランスの動作時間を改善することはできそうにありません-結局のところ、各頂点は新しい場所に「中断」されなければなりません。 しかし、メモリを節約することはできます。 「簡単な」アルゴリズムを詳しく見てみましょう。 ここで、中央値を選択し、ルートでそれを吊るし、ツリーは2つのサブツリーに分割されます-それは非常に明確に分割されています。 「他の中央値」を選択したり、左のサブツリーではなく「右の」サブツリーを一時停止することはできません。 同じ曖昧さは、次の各ステップで私たちを悩ませます。 つまり 昇順でソートされた頂点のリストの場合、このアルゴリズムによって生成されるツリーは1つだけになります。 そして、ソートされた頂点のリストはどこで取得しましたか？ 元のツリーの順序通りの走査から。 つまり 再バランスされたツリーの順序走査中に見つかった各頂点は、新しいツリーの特定の1つの位置に対応します。 そして、ソートされたリスト自体を作成することなく、原則としてこの位置を計算できます。 そして計算した-すぐにそこに書きます。 問題は1つだけです-結局、これはいくつかの（おそらくまだ表示されていない）ピークを上書きします-何をすべきでしょうか？ 彼女を保管してください。 どこ？ さて、そのような頂点のリストにメモリを割り当てます。 ただし、このメモリにはO（サイズ（N））は必要なくなり、O（log N）のみが必要になります。



練習として、3つのピークで構成されるツリーを想像してください。ルートと「左」の息子として吊るされた2つのピークです。 順序付けられたラウンドは、これらの頂点を「最も深い」ルートから順に返しますが、このラウンド中に別のメモリに格納するために、頂点が1つ（最も深い）になります。それは中央値であり、それがルートであり、他の2つのピークがその子になるということです。 つまり ここでのメモリ消費は、1つの頂点を格納することです。これは、3つの頂点のツリーの上限推定値（log（3））と一致しています。



トップ除去

バイナリ検索ツリーの最上部の通常の削除によって、頂点を削除します（子の検索、削除、再中断の可能性）。

次に、状態を確認します

サイズ[T] <α* max_size [T]

実行されると、ツリーは重量によってαバランスを失う可能性があります。つまり、ツリーの完全なリバランス（ルートから開始）を実行し、max_size [T] = size [T]を割り当てる必要があります。

これはどれほど生産的ですか？

検索時のメモリオーバーヘッドとリバランスの不足は良好であり、私たちにとっては有効です。 一方で、修正との再調整はそれほど安くはありません。 さて、αの選択は特定の操作のパフォーマンスに大きく影響します。 発明者自身は、Scapegoatツリーのパフォーマンスを赤黒ツリーおよびSplayツリーと比較しました 。 彼らは、ランダムなデータで、Scapegoatツリーが他のすべてのタイプのツリーよりも優れたパフォーマンスを発揮するようにαを選択することができました（実際にはかなり良いです）。 残念ながら、単調に増加するデータセットでは、Scapegoatツリーは挿入操作の観点からはうまく機能せず、Scapegoatはどのαでも勝ちませんでした。