Goデータ構造:二分探索木

Goでのバイナリ検索ツリーデータ構造の分析と実装

A階層構造の表現です。家系図の木について考えると、木を想像するのは簡単です。

ハッシュテーブルやグラフのように、非順次データ構造です。

A二分木すべてのノードに最大2つの子があるツリーです。

A二分探索木は、右側のノードの値よりも小さい値を持つ左側のノードのプロパティを持っています。

これは、この記事で作成するものです。これは、データの効率的な保存とインデックス作成、およびデータの取得に非常に役立つデータ構造です。

用語

ルート:ツリーのレベル0

:ルートではないツリーの各ノード

内部ノード:少なくとも子を持つ各ノード

:子を持たない各ノード

サブツリー:特定のノードをルートとするノードのセット

予備情報

二分木データ構造は、これらのメソッドを公開します。

  • Insert(t)アイテムtをツリーに挿入します
  • Search(t)アイテムtがツリーに存在する場合はtrueを返します
  • InOrderTraverse()順番にトラバースしてすべてのノードにアクセスします
  • PreOrderTraverse()プレオーダートラバースですべてのノードにアクセスします
  • PostOrderTraverse()注文後のトラバースですべてのノードにアクセスします
  • Min()ツリーに格納されている最小値を持つアイテムを返します
  • Max()ツリーに格納されている最大値のアイテムを返します
  • Remove(t)ツリーからアイテムtを削除します
  • String()ツリーのCLI読み取り可能なレンダリングを出力します

作成しますItemBinarySearchTreeジェネリック型、並行性セーフ、を使用して任意の型を含むツリーを生成できますgenny、タイプ固有のツリー実装を作成し、データを含む実際の値固有のデータ構造をカプセル化します。

私は各音符を次のように定義します

// Node a single node that composes the tree
type Node struct {
    key   int
    value Item
    left  *Node //left
    right *Node //right
}

キー値を使用すると、あらゆる種類のアイテムタイプを使用でき、別の値を使用して正しい場所を計算できます。私はそれを整数として実装しましたが、比較できる任意のタイプを取ることができます。

アイテムをツリーに挿入するには、正しい場所を見つける必要があるため、再帰を使用する必要があります。ルールは、ノードのキーが現在のノードツリーよりも小さい場合、左の子がない場合は左の子として配置します。それ以外の場合は、左の子をベースノードとして使用して位置を再計算します。同じことが正しい子供にも当てはまります。

トラバースはツリーをナビゲートするプロセスであり、3つの異なるアプローチがあるため、3つの方法を実装します。この二分探索木を取りました:

これが私たちがそれを横断する方法です:

  • 順番に:左端のリーフが見つかるまで最小のリンクをたどってすべてのノードにアクセスし、次にリーフを処理して、現在のノードにリンクされている次に小さいキー値に移動して他のノードに移動します。上の写真:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11
  • 予約注文:子を訪問する前に、このアプローチは最初にノードを訪問します。上の写真:8 -> 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> 10 -> 9 -> 11
  • ポストオーダー:最小の葉(左端の葉)を見つけ、兄弟を処理してから親ノードを処理し、次のサブツリーに移動して、親を上に移動します。上の写真:1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 -> 9 -> 11 -> 10 -> 8

ザ・Stringメソッドに関する視覚的なフィードバックを得るためにテストで使用されるメソッドは、上記のツリーを次のように出力します。

------------------------------------------------
                     ---[ 1
              ---[ 2
                     ---[ 3
       ---[ 4
                     ---[ 5
              ---[ 6
                     ---[ 7
---[ 8
              ---[ 9
       ---[ 10
              ---[ 11
------------------------------------------------

実装

// Package binarysearchtree creates a ItemBinarySearchTree data structure for the Item type
package binarysearchtree

import ( “fmt” “sync”

<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>

)

// Item the type of the binary search tree type Item generic.Type

// Node a single node that composes the tree type Node struct { key int value Item left Node //left right Node //right }

// ItemBinarySearchTree the binary search tree of Items type ItemBinarySearchTree struct { root *Node lock sync.RWMutex }

// Insert inserts the Item t in the tree func (bst *ItemBinarySearchTree) Insert(key int, value Item) { bst.lock.Lock() defer bst.lock.Unlock() n := &Node{key, value, nil, nil} if bst.root == nil { bst.root = n } else { insertNode(bst.root, n) } }

// internal function to find the correct place for a node in a tree func insertNode(node, newNode *Node) { if newNode.key < node.key { if node.left == nil { node.left = newNode } else { insertNode(node.left, newNode) } } else { if node.right == nil { node.right = newNode } else { insertNode(node.right, newNode) } } }

// InOrderTraverse visits all nodes with in-order traversing func (bst *ItemBinarySearchTree) InOrderTraverse(f func(Item)) { bst.lock.RLock() defer bst.lock.RUnlock() inOrderTraverse(bst.root, f) }

// internal recursive function to traverse in order func inOrderTraverse(n *Node, f func(Item)) { if n != nil { inOrderTraverse(n.left, f) f(n.value) inOrderTraverse(n.right, f) } }

// PreOrderTraverse visits all nodes with pre-order traversing func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(Item)) { bst.lock.Lock() defer bst.lock.Unlock() preOrderTraverse(bst.root, f) }

// internal recursive function to traverse pre order func preOrderTraverse(n *Node, f func(Item)) { if n != nil { f(n.value) preOrderTraverse(n.left, f) preOrderTraverse(n.right, f) } }

// PostOrderTraverse visits all nodes with post-order traversing func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(Item)) { bst.lock.Lock() defer bst.lock.Unlock() postOrderTraverse(bst.root, f) }

// internal recursive function to traverse post order func postOrderTraverse(n *Node, f func(Item)) { if n != nil { postOrderTraverse(n.left, f) postOrderTraverse(n.right, f) f(n.value) } }

// Min returns the Item with min value stored in the tree func (bst ItemBinarySearchTree) Min() Item { bst.lock.RLock() defer bst.lock.RUnlock() n := bst.root if n == nil { return nil } for { if n.left == nil { return &n.value } n = n.left } }

// Max returns the Item with max value stored in the tree func (bst ItemBinarySearchTree) Max() Item { bst.lock.RLock() defer bst.lock.RUnlock() n := bst.root if n == nil { return nil } for { if n.right == nil { return &n.value } n = n.right } }

// Search returns true if the Item t exists in the tree func (bst *ItemBinarySearchTree) Search(key int) bool { bst.lock.RLock() defer bst.lock.RUnlock() return search(bst.root, key) }

// internal recursive function to search an item in the tree func search(n *Node, key int) bool { if n == nil { return false } if key < n.key { return search(n.left, key) } if key > n.key { return search(n.right, key) } return true }

// Remove removes the Item with key key from the tree func (bst *ItemBinarySearchTree) Remove(key int) { bst.lock.Lock() defer bst.lock.Unlock() remove(bst.root, key) }

// internal recursive function to remove an item func remove(node Node, key int) Node { if node == nil { return nil } if key < node.key { node.left = remove(node.left, key) return node } if key > node.key { node.right = remove(node.right, key) return node } // key == node.key if node.left == nil && node.right == nil { node = nil return nil } if node.left == nil { node = node.right return node } if node.right == nil { node = node.left return node } leftmostrightside := node.right for { //find smallest value on the right side if leftmostrightside != nil && leftmostrightside.left != nil { leftmostrightside = leftmostrightside.left } else { break } } node.key, node.value = leftmostrightside.key, leftmostrightside.value node.right = remove(node.right, node.key) return node }

// String prints a visual representation of the tree func (bst *ItemBinarySearchTree) String() { bst.lock.Lock() defer bst.lock.Unlock() fmt.Println("------------------------------------------------") stringify(bst.root, 0) fmt.Println("------------------------------------------------") }

// internal recursive function to print a tree func stringify(n *Node, level int) { if n != nil { format := “” for i := 0; i < level; i++ { format += " " } format += “—[ " level++ stringify(n.left, level) fmt.Printf(format+”%d\n", n.key) stringify(n.right, level) } }

テスト

テストでは、上記の実装の使用法について説明します。

package binarysearchtree

import ( “fmt” “testing” )

var bst ItemBinarySearchTree

func fillTree(bst *ItemBinarySearchTree) { bst.Insert(8, “8”) bst.Insert(4, “4”) bst.Insert(10, “10”) bst.Insert(2, “2”) bst.Insert(6, “6”) bst.Insert(1, “1”) bst.Insert(3, “3”) bst.Insert(5, “5”) bst.Insert(7, “7”) bst.Insert(9, “9”) }

func TestInsert(t *testing.T) { fillTree(&bst) bst.String()

<span style="color:#a6e22e">bst</span>.<span style="color:#a6e22e">Insert</span>(<span style="color:#ae81ff">11</span>, <span style="color:#e6db74">"11"</span>)
<span style="color:#a6e22e">bst</span>.<span style="color:#a6e22e">String</span>()

}

// isSameSlice returns true if the 2 slices are identical func isSameSlice(a, b []string) bool { if a == nil && b == nil { return true } if a == nil || b == nil { return false } if len(a) != len(b) { return false } for i := range a { if a[i] != b[i] { return false } } return true }

func TestInOrderTraverse(t *testing.T) { var result []string bst.InOrderTraverse(func(i Item) { result = append(result, fmt.Sprintf("%s", i)) }) if !isSameSlice(result, []string{“1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9”, “10”, “11”}) { t.Errorf(“Traversal order incorrect, got %v”, result) } }

func TestPreOrderTraverse(t *testing.T) { var result []string bst.PreOrderTraverse(func(i Item) { result = append(result, fmt.Sprintf("%s", i)) }) if !isSameSlice(result, []string{“8”, “4”, “2”, “1”, “3”, “6”, “5”, “7”, “10”, “9”, “11”}) { t.Errorf(“Traversal order incorrect, got %v instead of %v”, result, []string{“8”, “4”, “2”, “1”, “3”, “6”, “5”, “7”, “10”, “9”, “11”}) } }

func TestPostOrderTraverse(t *testing.T) { var result []string bst.PostOrderTraverse(func(i Item) { result = append(result, fmt.Sprintf("%s", i)) }) if !isSameSlice(result, []string{“1”, “3”, “2”, “5”, “7”, “6”, “4”, “9”, “11”, “10”, “8”}) { t.Errorf(“Traversal order incorrect, got %v instead of %v”, result, []string{“1”, “3”, “2”, “5”, “7”, “6”, “4”, “9”, “11”, “10”, “8”}) } }

func TestMin(t testing.T) { if fmt.Sprintf("%s", bst.Min()) != “1” { t.Errorf(“min should be 1”) } }

func TestMax(t testing.T) { if fmt.Sprintf("%s", bst.Max()) != “11” { t.Errorf(“max should be 11”) } }

func TestSearch(t *testing.T) { if !bst.Search(1) || !bst.Search(8) || !bst.Search(11) { t.Errorf(“search not working”) } }

func TestRemove(t testing.T) { bst.Remove(1) if fmt.Sprintf("%s", bst.Min()) != “2” { t.Errorf(“min should be 2”) } }

具体的なツリーデータ構造の作成

この一般的な実装を使用して、を使用してタイプ固有のツリーを生成できます。

//generate a `IntBinarySearchTree` binary search tree of `int` values
genny -in binarysearchtree.go -out binarysearchtree-int.go gen "Item=int"

//generate a </span>StringBinarySearchTree<span style="color:#e6db74"> binary search tree of </span>string<span style="color:#e6db74"> values genny -in binarysearchtree.go -out binarysearchtree-string.go gen “Item=string”


その他のチュートリアル: