スキップリスト（Skip List）は確率的なデータ構造であり、標準の順序付きリストに複数のインデックス層を追加することで、高速な検索、挿入、削除操作を実現します。この構造は平衡木と同等の効率を持つことができ、各操作の時間計算量はO(log n)です。また、その実装が比較的シンプルであるという利点があります。
スキップリストの主要特徴
- マルチレベル構造：スキップリストは複数のレベルで構成されています。最も低いレベル（レベル0）にはすべての要素が含まれます。各レベルは次のレベルへの「高速パス」であり、要素が上位レベルに出現する確率は通常1/2です。
- ヘッドノード：スキップリストにはヘッドノード（head）が存在し、すべてのレベルにわたって共通して配置されます。このノードの値は実際のデータを格納せず、探索、挿入、削除の操作を一貫した起点として提供します。
- ランダムなレベル割り当て：新しい要素が挿入される際、そのレベルはランダムプロセスによって決定され、バランスを保つように設計されています。これにより、高レベルのインデックスが過密または疎になることを防ぎます。
データ構造の構成要素
- ノード（SkipListNode）：各ノードには以下の情報が含まれます：
- 値（value）：格納されるデータ。
- 前進ポインタ（forward）：現在のレベルの次のノードや上位レベルの対応するノードを指すポインタ配列。
- ヘッドノード（Head）：特殊なノードで、
forwardポインタ配列の長さはスキップリストの最大レベルに等しくなります。これはすべてのレベルにおいて、そのレベルの最初の実際のノードを指します（存在する場合）。 - レベル（Level）：スキップリストの最大レベル数です。これは動的に変化し、新しいノードの挿入に応じて増加します。
操作の仕組み
- 検索（Search）：ヘッドノードから開始し、最も高いレベルから順に探索を行います。現在のノードの次の要素が検索値より小さい場合は進み、大きい場合は次のレベルに移動します。目的の値が見つかるか、探索が失敗するまで続けられます。
- 挿入（Insert）：まずランダムに新規ノードのレベルを決定します。次に、最も高いレベルから順に挿入位置を探し、下位レベルへと降りながら適切な位置に挿入します。各レベルにおいて、ノードを挿入し、関連するポインタを更新します。
- 削除（Delete）：検索と同様に、削除対象のノードを特定します。その後、最も高いレベルから順に削除を行い、ポインタを更新します。
利点と応用分野
- 単純性：スキップリストの構造およびアルゴリズムは、平衡木やB木などの他の構造と比較して比較的シンプルです。
- 動的変更可能：動的なデータセットに対する操作（リアルタイムでの挿入・削除）を容易にサポートします。
- 効率性：主な操作において対数時間で処理できるため、高速な検索が必要な場面（例えばデータベースのインデックスやメモリデータベース）に適しています。
スキップリストは複雑な再平衡処理を回避するために、単純なランダム化手法を使用し、効率的かつ実装しやすいデータ構造として利用できます。
スキップリストの簡単な実装例
import java.util.Random;
class SkipListNode {
int value;
SkipListNode[] forward;
public SkipListNode(int value, int level) {
this.value = value;
this.forward = new SkipListNode[level + 1];
}
}
public class SkipList {
private static final float P = 0.5f;
private static final int MAX_LEVEL = 16;
private SkipListNode head;
private int level;
private Random random;
public SkipList() {
level = 0;
head = new SkipListNode(0, MAX_LEVEL);
random = new Random();
}
private int randomLevel() {
int lvl = 1;
while (random.nextFloat() < P && lvl < MAX_LEVEL) {
lvl++;
}
return lvl;
}
public void insert(int value) {
int lvl = randomLevel();
SkipListNode newNode = new SkipListNode(value, lvl);
SkipListNode current = head;
SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < value) {
current = current.forward[i];
}
update[i] = current;
}
for (int i = 0; i <= lvl; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
if (lvl > level) {
level = lvl;
}
}
public boolean search(int value) {
SkipListNode current = head;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < value) {
current = current.forward[i];
}
}
current = current.forward[0];
return current != null && current.value == value;
}
public void delete(int value) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
SkipListNode current = head;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < value) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current.value == value) {
for (int i = 0; i <= level; i++) {
if (update[i].forward[i] != current) break;
update[i].forward[i] = current.forward[i];
}
while (level > 0 && head.forward[level] == null) {
level--;
}
}
}
public void display() {
System.out.println("SkipList: ");
for (int i = 0; i <= level; i++) {
SkipListNode node = head.forward[i];
System.out.print("Level " + i + ": ");
while (node != null) {
System.out.print(node.value + " ");
node = node.forward[i];
}
System.out.println();
}
}
}
public class Main {
public static void main(String[] args) {
SkipList list = new SkipList();
list.insert(3);
list.insert(6);
list.insert(7);
list.insert(9);
list.insert(12);
list.insert(19);
list.insert(17);
list.display();
System.out.println("Searching 6: " + list.search(6));
System.out.println("Searching 15: " + list.search(15));
list.delete(6);
System.out.println("After deleting 6: ");
list.display();
}
}
このコードでは、SkipListNodeクラスがスキップリストのノードを定義しており、ノードの値と各レベルへのポインタ配列forwardを保持します。SkipListクラスは初期化、挿入、検索、削除、表示の各機能を実装しています。
insertメソッドは新しいノードを挿入します。searchメソッドは指定された値を検索し、存在すればtrueを返します。deleteメソッドは指定された値を削除します。displayメソッドはスキップリストの各レベルの内容を出力します。
スキップリストの挿入手順の具体例
現在のスキップリストが以下のような状態であると仮定します。各行はレベルを示しており、レベル0が最下位レベルで、すべての要素が含まれています。
Level 3: 1 --------------------------------> 9
Level 2: 1 ------------> 5 ------------> 9
Level 1: 1 ----> 3 ----> 5 ----> 7 ----> 9
Level 0: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 9
新たに値8を持つノードを挿入し、ランダムプロセスによりノードはレベル0、1、2にのみ出現すると仮定します（レベル3には出現しません）。挿入手順は以下の通りです。
ステップ1：各レベルでの挿入位置の探索
スキップリストの最上位レベル（この例ではレベル3）から開始し、挿入値よりも小さな最大ノードを探索します。8はレベル3に挿入されないため、レベル2から探索を開始します。
- レベル2：
1から開始し、5に到達します。9が8より大きいので、5が挿入位置となります。 - レベル1：同様に
1から開始し、5→7と進みます。9が8より大きいので、7が挿入位置となります。 - レベル0：
1から順に進み、7に到達します。9が8より大きいので、7が挿入位置となります。
ステップ2：ノードの挿入とポインタの更新
- レベル2：
5と9の間に8を挿入し、5のポインタを8に、8のポインタを9に更新します。 - レベル1：
7と9の間に8を挿入し、7のポインタを8に、8のポインタを9に更新します。 - レベル0：
7と9の間に8を挿入し、7のポインタを8に、8のポインタを9に更新します。
挿入後、スキップリストは以下のようになります：
Level 3: 1 --------------------------------> 9
Level 2: 1 ------------> 5 -------> 8 ----> 9
Level 1: 1 ----> 3 ----> 5 ----> 7 -> 8 -> 9
Level 0: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
ステップ3：全体のレベル数の調整（必要に応じて）
この例では、挿入されたノード8によりレベル数が増加しないため、調整は不要です。
この例を通じて、各レベルにおいて適切な挿入位置を特定し、ポインタを更新することでスキップリストの構造を維持する方法を確認できます。このプロセスにより、検索、挿入、削除の操作がO(log n)時間で実行可能になります。