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”
その他のチュートリアル：
- NGINXリバースプロキシを使用してGoサービスを提供する
- Goで構造体のコピーを作成する
- GoWebサーバーの基本
- Goでのマップタイプの並べ替え
- 一言で言えばポインタを移動します
- タグの説明に行く
- 日付と時刻のフォーマットに移動
- Goを使用したJSON処理
- 可変個引数関数に移動
- GoStringsチートシート
- GoEmptyインターフェイスの説明
- Go withVSCodeとDelveのデバッグ
- NamedGoはパラメータを返します
- Goで乱数と文字列を生成する
- Goプロジェクトのファイルシステム構造
- Goに実装された二分探索アルゴリズム
- Goでのコマンドラインフラグの使用
- GOPATHの説明
- Goでコマンドラインアプリを作成する：lolcat
- Goを使用したCLIコマンドの作成：cowsay
- Goでのシェルパイプの使用
- CLIチュートリアルに移動：フォーチュンクローン
- Goを使用してフォルダ内のファイルを一覧表示します
- Goを使用して、GitHubからリポジトリのリストを取得します
- 移動し、文字列のスライスをファイルに追加します
- 文字列をバイトスライスに変換します
- GoでローカルGitの貢献を視覚化する
- GoCPUとメモリプロファイリングの開始
- Goプログラムの「インデックス作成をサポートしていません」エラーを解決する
- Goプログラムでの実行時間の測定
- 重複するタイトルを検出するためにGoを使用してWebクローラーを構築する
- ベストプラクティスに進む：ポインターまたは値のレシーバー？
- ベストプラクティスに進む：メソッドまたは関数を使用する必要がありますか？
- データ構造の移動：設定
- マップのチートシートに移動
- Goでジェネリック型の実装を生成する
- Goデータ構造：辞書
- Goデータ構造：ハッシュテーブル
- Go throughChannelsにイベントリスナーを実装する
- Goデータ構造：スタック
- データ構造の移動：キュー
- Goデータ構造：二分探索木
- Goデータ構造：グラフ
- Goデータ構造：リンクリスト
- Goデータ構造の完全ガイド
- Go値の比較
- Goはオブジェクト指向ですか？
- GoでのSQLデータベースの操作
- Goでの環境変数の使用
- チュートリアルに進む：PostgreSQLに裏打ちされたREST API
- GoWebサーバーでのCORSの有効化
- DockerコンテナへのGoアプリケーションのデプロイ
- GoがPHP開発者として学ぶための強力な言語である理由
- 移動し、io.Reader.ReadString改行文字を削除します
- 移動、変更を監視してプログラムを再構築する方法
- 行って、日付からの月を数えます
- GoでHTTPPOSTパラメーターにアクセスする