スプレイ ツリーは、自己調整型の二分探索ツリー データ構造です。つまり、アクセスまたは挿入された要素に基づいてツリー構造が動的に調整されます。つまり、頻繁にアクセスまたは挿入される要素がルート ノードに近づくように、ツリー自体が自動的に再編成されます。
- スプレイ ツリーは、1985 年に Daniel Dominic Sleator と Robert Endre Tarjan によって初めて導入されました。これは、検索、挿入、削除操作を O(log n) の償却時間計算量で実行できるシンプルで効率的な実装を備えています。ここで、n はツリー内の要素の数。
- スプレイ ツリーの背後にある基本的な考え方は、スプレイと呼ばれる一連のツリー回転を実行することによって、最後にアクセスまたは挿入された要素をツリーのルートに移動することです。拡張とは、最後にアクセスまたは挿入された要素を新しいルートにし、残りのノードを徐々にルートに近づけることによってツリーを再構築するプロセスです。
- スプレイ ツリーは、その自己調整の性質により実際には非常に効率的であり、頻繁にアクセスされる要素の全体的なアクセス時間が短縮されます。このため、キャッシュ システム、データ圧縮、ネットワーク ルーティング アルゴリズムなど、高速で動的なデータ構造を必要とするアプリケーションに適しています。
- ただし、スプレイ ツリーの主な欠点は、バランスの取れたツリー構造が保証されていないため、最悪のシナリオではパフォーマンスの低下につながる可能性があることです。また、スプレイ ツリーは、リアルタイム システムやセーフティ クリティカル システムなど、最悪の場合のパフォーマンスの保証が必要なアプリケーションには適していません。
全体として、スプレイ ツリーは、頻繁にアクセスまたは挿入される要素への高速かつ効率的なアクセスを提供する、強力で汎用性の高いデータ構造です。これらはさまざまなアプリケーションで広く使用されており、パフォーマンスとシンプルさの間で優れたトレードオフを実現します。
スプレイ ツリーは自己平衡型の二分探索ツリーであり、キー値に基づいてデータ要素に効率的にアクセスできるように設計されています。
- スプレイ ツリーの主な特徴は、要素がアクセスされるたびに要素がツリーのルートに移動され、その後のアクセスに対してよりバランスの取れた構造が作成されることです。
- スプレイ ツリーは、回転を使用することを特徴としています。回転とは、形状を変更しながら要素の順序を維持するツリーのローカル変換です。
- 回転は、アクセスされた要素をツリーのルートに移動するために使用され、また、複数のアクセス後にツリーのバランスが崩れた場合にツリーのバランスを再調整するためにも使用されます。
スプレイ ツリーでの操作:
- 挿入： 新しい要素をツリーに挿入するには、まず通常の二分探索ツリーの挿入を実行します。次に、回転を適用して、新しく挿入された要素をツリーのルートに移動します。
- 削除 : ツリーから要素を削除するには、まず二分探索ツリー検索を使用して要素を見つけます。次に、要素に子がない場合は、単純に削除します。子が 1 つある場合は、その子をツリー内のその位置に昇格させます。 2 つの子がある場合は、要素の後続要素 (右側のサブツリー内の最小要素) を見つけ、そのキーを削除する要素と交換し、代わりに後続要素を削除します。
- 検索 : ツリー内の要素を検索するには、まず二分探索ツリー検索を実行します。要素が見つかった場合は、回転を適用してツリーのルートに移動します。見つからない場合は、検索で最後に訪問したノードに回転を適用します。これが新しいルートになります。
- 回転 : スプレイ ツリーで使用される回転は、ジグ回転またはジグジグ回転のいずれかです。ジグ回転はノードをルートに移動するために使用され、ジグジグ回転は同じサブツリー内の要素に複数回アクセスした後にツリーのバランスをとるために使用されます。
回転操作を段階的に説明します。
- ジグ回転 : ノードに右の子がある場合は、右回転を実行してその子をルートに移動します。左の子がある場合は、左ローテーションを実行します。
- ジグジグ回転: ノードにその子の右または左の子でもある孫がある場合、ツリーのバランスをとるために二重回転を実行します。たとえば、ノードに右の子があり、右の子に左の子がある場合は、右から左への回転を実行します。ノードに左の子があり、左の子に右の子がある場合は、左右の回転を実行します。
- 注記： 使用される正確な回転を含む具体的な実装の詳細は、スプレイ ツリーの正確な形式によって異なる場合があります。
スプレイ ツリーの回転
- ジグ回転
- ザグ回転
- ジグ – ジグ回転
- ザグ – ザグ回転
- ジグ – ザグ回転
- ザグ – ジグ回転
1) ジグ回転:
スプレイ ツリーのジグ回転は、AVL ツリー回転の 1 つの右回転と同様の方法で動作します。この回転により、ノードは現在の位置から 1 つ右に移動します。たとえば、次のシナリオを考えてみましょう。
ジグ回転（単回転）
2) ザグ回転:
スプレイ ツリーのザグ回転は、AVL ツリー回転の単一の左回転と同様の方法で動作します。この回転中に、ノードは現在の位置から 1 つ左に位置をシフトします。たとえば、次の図を考えてみましょう。
前方連鎖
ザグ回転（左片回転）
3) ジグジグ回転:
スプレイ ツリーのジグジグ回転は、二重ジグ回転です。この回転により、ノードは現在の位置から右に 2 位置移動します。より深く理解するために、次の例を見てください。
ジグジグ回転（右ダブル回転）
4) ザグザグ回転:
スプレイ ツリーでは、ザグザグ回転はダブル ザグ回転です。この回転により、ノードは現在の位置から 2 つ左に移動します。例えば：
ザグザグ回転（左二重回転）
5) ジグザグ回転:
スプレイ ツリーのジグザグ回転は、ジグ回転とそれに続くザグ回転の組み合わせです。この回転の結果、ノードは現在の位置から右に 1 位置移動し、次に左に 1 位置移動します。次の図は、この概念を視覚的に表したものです。
スキャナJava
ジグザグ回転
6) ザグジグ回転:
スプレイ ツリーのザグジグ回転は、一連のザグ回転の後にジグ回転が続くことです。これにより、ノードは現在の位置から 1 位置左に移動し、その後 1 位置右に移動します。次の図は、この概念を視覚的に表したものです。
ザグジグ回転
部分的な依存関係
以下は、Splay ツリーで回転を実装するための C++ コードです。
C++ #include using namespace std; struct Node { int key; Node *left, *right; }; Node* newNode(int key) { Node* node = new Node(); node->キー = キー; ノード->左 = ノード->右 = nullptr; リターンノード; } ノード* rightRotate(ノード* x) { ノード* y = x->left; x->左 = y->右; y->右 = x; y を返します。 } ノード* leftRotate(ノード* x) { ノード* y = x->right; x->右 = y->左; y->left = x; y を返します。 } Node* splay(Node* root, int key) { if (root == nullptr || root->key == key) return root; if (root->key> key) { if (root->left == nullptr) ルートを返します。 if (root->left->key> key) { root->left->left = splay(root->left->left, key); ルート = rightRotate(ルート); else if (ルート->左->キー< key) { root->left->right = スプレイ(root->left->right, key); if (root->left->right != nullptr) root->left = leftRotate(root->left); return (root->left == nullptr) ?ルート : rightRotate(root); } else { if (root->right == nullptr) ルートを返します。 if (root->right->key> key) { root->right->left = splay(root->right->left, key); if (root->right->left != nullptr) root->right = rightRotate(root->right); else if (ルート->右->キー< key) { root->right->right = スプレイ(root->right->right, key); root = leftRotate(root); return (root->right == nullptr) ?ルート : leftRotate(root); Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key); ルート = スプレイ(ルート, キー); if (root->key == key) ルートを返します。 ノード* ノード = newNode(キー); if (ルート->キー> キー) { ノード->右 = ルート; ノード->左 = ルート->左; ルート->左 = nullptr; } else { ノード->左 = ルート; ノード->右 = ルート->右; ルート->右 = nullptr; ノードを返します。 } void preOrder(Node* ノード) { if (node != nullptr) { cout<< node->鍵<< ' '; preOrder(node->左）; preOrder(ノード->右); int main() { ノード * ルート = nullptr; ルート = 挿入(ルート, 100); ルート = 挿入(ルート, 50); ルート = 挿入(ルート, 200); ルート = 挿入(ルート, 40); ルート = 挿入(ルート, 60); コート<< 'Preorder traversal of the modified Splay tree:' << endl; preOrder(root); return 0; }> ジャワ // Java Program for the above approach class Node { public int key; public Node left, right; } class SplayTree { static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return node; } static Node rightRotate(Node x) { Node y = x.left; x.left = y.right; y.right = x; return y; } static Node leftRotate(Node x) { Node y = x.right; x.right = y.left; y.left = x; return y; } static Node splay(Node root, int key) { if (root == null || root.key == key) return root; if (root.key>key) { if (root.left == null) ルートを返します。 if (root.left.key> key) { root.left.left = splay(root.left.left, key); ルート = rightRotate(ルート); else if (root.left.key< key) { root.left.right = splay(root.left.right, key); if (root.left.right != null) root.left = leftRotate(root.left); } return (root.left == null) ? root : rightRotate(root); } else { if (root.right == null) return root; if (root.right.key>key) { root.right.left = スプレイ(root.right.left, key); if (root.right.left != null) root.right = rightRotate(root.right); else if (root.right.key< key) { root.right.right = splay(root.right.right, key); root = leftRotate(root); } return (root.right == null) ? root : leftRotate(root); } } static Node insert(Node root, int key) { if (root == null) return newNode(key); root = splay(root, key); if (root.key == key) return root; Node node = newNode(key); if (root.key>key) {node.right = ルート; ノード.左 = ルート.左; root.left = null; } else {node.left = ルート; ノード.右 = ルート.右; root.right = null; ノードを返します。 静的 void preOrder(Node ノード) { if (node != null) { System.out.println(); System.out.print(node.key + ' '); preOrder(node.left); preOrder(node.right); public static void main(String[] args) { ノードルート = null; ルート = 挿入(ルート, 100); ルート = 挿入(ルート, 50); ルート = 挿入(ルート, 200); ルート = 挿入(ルート, 40); ルート = 挿入(ルート, 60); System.out.println('変更されたスプレイ ツリーの事前順序走査:'); preOrder(ルート); } } // このコードは、princekumaras によって提供されました>> Python3 class Node: def __init__(self, key): self.key = key self.left = None self.right = None def new_node(key): return Node(key) def right_rotate(x): y = x.left x.left = y.right y.right = x return y def left_rotate(x): y = x.right x.right = y.left y.left = x return y def splay(root, key): if root is None : return new_node(key) if root.key == key: return root if root.key>key: root.left が None の場合: root.left.key> key の場合は root を返します: root.left.left = splay(root.left.left, key) root = right_rotate(root) elif root.left.key< key: root.left.right = splay(root.left.right, key) if root.left.right: root.left = left_rotate(root.left) return root.left if root.left is None else right_rotate(root) else: if root.right is None: return root if root.right.key>key: root.right.left = splay(root.right.left, key) if root.right.left: root.right = right_rotate(root.right) elif root.right.key< key: root.right.right = splay(root.right.right, key) root = left_rotate(root) return root.right if root.right is None else left_rotate(root) def insert(root, key): if root is None: return new_node(key) root = splay(root, key) if root.key == key: return root node = new_node(key) if root.key>key：node.right = ルートnode.left = root.left root.left = なしその他：node.left = ルートnode.right = root.right root.right = なしreturnノードdef pre_order(node):ifノード: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = None root = insert(root, 100) root = insert(root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('変更されたスプレイ ツリーの事前順序走査:') pre_order(root)>> C# // C# program for the above approach using System; class Node { public int key; public Node left, right; } class SplayTree { static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return node; } static Node rightRotate(Node x) { Node y = x.left; x.left = y.right; y.right = x; return y; } static Node leftRotate(Node x) { Node y = x.right; x.right = y.left; y.left = x; return y; } static Node splay(Node root, int key) { if (root == null || root.key == key) return root; if (root.key>key) { if (root.left == null) ルートを返します。 if (root.left.key> key) { root.left.left = splay(root.left.left, key); ルート = rightRotate(ルート); else if (root.left.key< key) { root.left.right = splay(root.left.right, key); if (root.left.right != null) root.left = leftRotate(root.left); } return (root.left == null) ? root : rightRotate(root); } else { if (root.right == null) return root; if (root.right.key>key) { root.right.left = スプレイ(root.right.left, key); if (root.right.left != null) root.right = rightRotate(root.right); else if (root.right.key< key) { root.right.right = splay(root.right.right, key); root = leftRotate(root); } return (root.right == null) ? root : leftRotate(root); } } static Node insert(Node root, int key) { if (root == null) return newNode(key); root = splay(root, key); if (root.key == key) return root; Node node = newNode(key); if (root.key>key) {node.right = ルート; ノード.左 = ルート.左; root.left = null; } else {node.left = ルート; ノード.右 = ルート.右; root.right = null; ノードを返します。 } static void preOrder(Node node) { if (node != null) { Console.Write(node.key + ' '); preOrder(node.left); preOrder(node.right); public static void Main(string[] args) { ノードルート = null; ルート = 挿入(ルート, 100); ルート = 挿入(ルート, 50); ルート = 挿入(ルート, 200); ルート = 挿入(ルート, 40); ルート = 挿入(ルート, 60); Console.WriteLine( '変更されたスプレイ ツリーの事前順序走査:'); preOrder(ルート); } } // このコードは Prince Kumar によって寄稿されました>> JavaScript // Javascript code addition class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } class SplayTree { static newNode(key) { const node = new Node(key); return node; } static rightRotate(x) { const y = x.left; x.left = y.right; y.right = x; return y; } static leftRotate(x) { const y = x.right; x.right = y.left; y.left = x; return y; } static splay(root, key) { if (root == null || root.key == key) { return root; } if (root.key>key) { if (root.left == null) { ルートを返します。 if (root.left.key> key) { root.left.left = SplayTree.splay(root.left.left, key); root = SplayTree.rightRotate(root); else if (root.left.key< key) { root.left.right = SplayTree.splay(root.left.right, key); if (root.left.right != null) { root.left = SplayTree.leftRotate(root.left); } } return root.left == null ? root : SplayTree.rightRotate(root); } else { if (root.right == null) { return root; } if (root.right.key>key) { root.right.left = SplayTree.splay(root.right.left, key); if (root.right.left != null) { root.right = SplayTree.rightRotate(root.right); else if (root.right.key< key) { root.right.right = SplayTree.splay(root.right.right, key); root = SplayTree.leftRotate(root); } return root.right == null ? root : SplayTree.leftRotate(root); } } static insert(root, key) { if (root == null) { return SplayTree.newNode(key); } root = SplayTree.splay(root, key); if (root.key == key) { return root; } const node = SplayTree.newNode(key); if (root.key>key) {node.right = ルート; ノード.左 = ルート.左; root.left = null; } else {node.left = ルート; ノード.右 = ルート.右; root.right = null; ノードを返します。 } static preOrder(node) { if (node != null) { console.log(node.key + ' '); SplayTree.preOrder(node.left); SplayTree.preOrder(node.right); root = null にします。 root = SplayTree.insert(root, 100); root = SplayTree.insert(root, 50); root = SplayTree.insert(root, 200); root = SplayTree.insert(root, 40); root = SplayTree.insert(root, 60); console.log('変更されたスプレイ ツリーの事前注文トラバーサル:'); SplayTree.preOrder(ルート); // コードは Nidhi goel によって寄稿されました。>> 出力
Preorder traversal of the modified Splay tree:>
スプレイ ツリー データ構造の欠点:
- アンバランスな木: スプレー ツリーが同じ方向に繰り返し回転されると、バランスが崩れ非効率になる可能性があります。
- メモリ使用量： スプレイ ツリーは、各ノードに追加情報が含まれるため、他のデータ構造と比較して大量のメモリを使用する可能性があります。
- 複雑： スプレイ ツリーでは、操作のたびにツリーを再編成する必要があるため、挿入や削除などの基本的な操作が非常に複雑になる可能性があります。
- 再編成のオーバーヘッド: すべての操作で必要な拡張操作は時間がかかり、オーバーヘッドが高くなる可能性があります。
- 限られた使用例 : スプレイ ツリーはすべてのデータ構造に適しているわけではなく、重複キーを効率的に処理できないため、使用例が限られています。
スプレーツリーの用途:
- キャッシング : スプレイ ツリーを使用すると、キャッシュ メモリ管理を実装できます。これにより、最も頻繁にアクセスされる項目がツリーの先頭に移動され、より迅速にアクセスできるようになります。
- データベースのインデックス作成 : スプレイ ツリーを使用してデータベースのインデックスを作成し、データの検索と取得を高速化できます。
- ファイルシステム : スプレイ ツリーを使用して、アロケーション テーブル、ディレクトリ構造、ファイル属性などのファイル システム メタデータを保存できます。
- データ圧縮: スプレイ ツリーを使用すると、繰り返しパターンを識別してエンコードすることでデータを圧縮できます。
- テキスト処理 : スプレイ ツリーは、スペル チェッカーなどのテキスト処理アプリケーションで使用できます。スプレイ ツリーでは、単語がスプレイ ツリーに保存され、迅速な検索と取得が可能です。
- グラフアルゴリズム: スプレイ ツリーを使用して、重み付きグラフでの最短パスを見つけるなどのグラフ アルゴリズムを実装できます。
- オンラインゲーム： スプレイ ツリーは、オンライン ゲームでハイスコア、リーダーボード、プレーヤー統計を保存および管理するために使用できます。
もちろん、ここではスプレー ツリーの長所と短所、およびこのトピックについて詳しく学ぶための推奨書籍をいくつか紹介します。
スプレイツリーの利点:
スプレイ ツリーは、多くの操作で O(log n) の償却時間計算量を持ち、場合によっては他の多くのバランス ツリー データ構造よりも高速になります。
スプレイ ツリーは自己調整機能を備えており、アイテムの挿入や削除に応じて自動的にバランスが取れます。これは、ツリーのバランスが崩れたときに発生する可能性のあるパフォーマンスの低下を回避するのに役立ちます。
スプレーツリーの欠点:
スプレイ ツリーは、一部の操作で最悪の場合の時間計算量が O(n) になる可能性があり、AVL ツリーや赤黒ツリーなどの他のバランス ツリー データ構造よりも予測しにくくなります。
スプレイ ツリーは、予測可能なパフォーマンスが必要な特定のアプリケーションには適さない場合があります。
スプレー ツリーに関するおすすめの本:
Java のデータ構造とアルゴリズム分析 (Mark Allen Weiss)
アルゴリズム入門 (トーマス H. コーメン、チャールズ E. ライザーソン、ロナルド L. リベスト、クリフォード スタイン)
C++ のデータ構造とアルゴリズム Michael T. Goodrich および Roberto Tamassia 著
結論：
結論として、スプレイ ツリーは、要素の検索、挿入、削除の効率的な方法を提供する動的自己平衡型二分探索ツリー データ構造です。これらは、各操作の後にツリーを再編成して、最近アクセスしたノードをルートに持ってくるため、AVL や Red-Black ツリーなどの従来のバランス型二分探索ツリーとは異なります。これにより、ツリーの高さが低くなり、操作が高速化されます。スプレイ ツリーは柔軟性が高く、さまざまなユースケースに適応できます。回転の点でオーバーヘッドが高くなりますが、そのシンプルさと多用途性により、さまざまな問題を解決するための便利なツールとなります。