golangでスキップテーブルのデータ構造を実装する方法

スキップリストは、バランスツリーに似たリンクリストに基づいたデータ構造であり、高速な検索、挿入、削除操作を実現できます。スキップ リストは 1990 年に William Pugh によって提案されました。その実装はリンク リストに基づいています。リンク リストに基づいてマルチレベルのインデックスが追加され、インデックスを通じてリンク リストのノードを迅速に見つけることができます。 。ジャンプ リストの下部にあるリンク リストには、一方向リンク リスト、二重リンク リストなどがありますが、最も一般的に使用されるのは一方向リンク リストです。この記事では主にGolang言語を使用してスキップテーブルのデータ構造を実装する方法を紹介します。

スキップ リストの構造

スキップ リストの主な構造は、ヘッド ノード、配列、リンク リストの 3 つの部分で構成されます。ヘッド ノードは、ジャンプ リストの開始ノードを見つけるために使用されます。配列はマルチレベルのインデックスを格納するために使用され、配列の各要素はリンク リスト ノードへのポインタです。リンク リストはスキップ リストの中核であり、データを保存するために使用されます。

ジャンプ リストの各レベルにはいくつかのノードが含まれており、ノードはポインターを介して相互に接続されています。各レベルのノードの数は徐々に減少します。最下層にはすべてのデータ ノードが含まれます。この層は通常「ベース層」と呼ばれ、「レベル 0 リンク リスト」とも呼ばれます。各ノードはデータ ノードまたはインデックス ノードのいずれかです。インデックス ノードは次のレベルのノードを指し、n はデータ ノードの数として、logn レベルのインデックスまで存在できます。 k レベルのインデックスがある場合、i 番目のレベル インデックスのノードは、i-1 番目のレベル インデックス ノードのすべての 2^i ノードが i 番目のレベル インデックスのノードを指すようにします。各ノードには、同じ場所にある次のレベルのノードへのポインタが含まれています。

Golang によるスキップ テーブルの実装

Golang 言語でスキップ テーブルのデータ構造を実装するには、主に以下の関数を実装する必要があります。

1. createNode 関数: ジャンプ テーブル ノードの作成を担当します。

type stopNode struct {

forward []*skipNode 
key int
val interface{}

}

func createNode(level int, key int, valinterface{}) *skipNode {

return &skipNode{
    forward: make([]*skipNode, level),
    key: key,
    val: val,
}

}

2. insert 関数: ジャンプ テーブルにデータを挿入します。

func (list *SkipList) insert(key int, val Interface{}, level int) {

 update := make([]*skipNode, list.level+1)
 currentNode := list.head
 for i := list.level; i >= 0; i-- {
    for currentNode.forward[i] != nil && currentNode.forward[i].key < key {
        currentNode = currentNode.forward[i]
    }
    update[i] = currentNode
 }
 currentNode = currentNode.forward[0]
 if currentNode != nil && currentNode.key == key {
    currentNode.val = val
 } else {
    newNode := createNode(level, key, val)
    for i := 0; i <= level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
 }

}

3. delete 関数: 責任者データを削除します。

func (list *SkipList) delete(key int) {

update := make([]*skipNode, list.level+1)
currentNode := list.head

for i := list.level; i >= 0; i-- {
    for currentNode.forward[i] != nil && currentNode.forward[i].key < key {
        currentNode = currentNode.forward[i]
    }
    update[i] = currentNode
}

currentNode = currentNode.forward[0]
if currentNode != nil && currentNode.key == key {
    for i := 0; i <= list.level; i++ {
        if update[i].forward[i] != currentNode {
            break
        }
        update[i].forward[i] = currentNode.forward[i]
    }
}

}

4. find 関数: スキップ リスト内のデータを検索します。

func (list SkipList) find(key int) skipNode {

currentNode := list.head
for i := list.level; i >= 0; i-- {
    for currentNode.forward[i] != nil && currentNode.forward[i].key < key {
        currentNode = currentNode.forward[i]
    }
}
currentNode = currentNode.forward[0]
if currentNode != nil && currentNode.key == key {
    return currentNode
} else {
    return nil
}

}

上記は、を実装するための主な要件です。スキップリスト機能。さらに、ヘッド ノード、最大深度などのスキップ リストのいくつかの属性を含む SkipList 構造を実装する必要があります。

結論

スキップ テーブルは、平均 O(log n) 時間の計算量で挿入、削除、検索操作を実装できる効率的なデータ構造です。 Golang 言語は比較的使いやすい構文と標準ライブラリを提供するため、Golang 言語を使用してジャンプ テーブルを実装するのは比較的簡単です。この記事を読むことで、読者の皆様はスキップテーブルについての理解が深まるだけでなく、Golang言語によるスキップテーブルの実装方法も習得できると思います。

以上がgolangでスキップテーブルのデータ構造を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。