/

Go 資料結構：二元搜尋樹

Go 資料結構：二元搜尋樹

在這篇文章中，我們將分析和實現二元搜尋樹的資料結構。

樹 是一個有階層結構的表示法。通常我們可以通過想像一個家族的族譜樹來理解樹的概念。

二元搜尋樹是一種每個節點最多有兩個子節點的樹。

二元搜尋樹具有左節點的值小於右節點的值的特性。

這是我們在本文中要建構的資料結構。它是一個非常有用的資料結構，可以有效地存儲和索引數據，並且可以快速檢索數據。

詞彙定義：

  • 根：樹的第 0 層
  • 子節點：除了根節點以外的每個節點
  • 內部節點：具有至少一個子節點的節點
  • 葉節點：沒有子節點的每個節點
  • 子樹：以特定節點為根的一組節點

預備信息：

一個二元搜尋樹資料結構將公開以下方法：

  • Insert(t)：插入項目 t 到樹中
  • Search(t)：如果項目 t 存在於樹中，則返回 true
  • InOrderTraverse()：按中序遍歷訪問所有節點
  • PreOrderTraverse()：按先序遍歷訪問所有節點
  • PostOrderTraverse()：按後序遍歷訪問所有節點
  • Min()：返回存儲在樹中的最小值項目
  • Max()：返回存儲在樹中的最大值項目
  • Remove(t)：從樹中刪除項目 t
  • String()：打印可讀取的樹形結構

我將創建一個 ItemBinarySearchTree 的泛型類型，並且支持併發，它可以通過使用 genny 來生成包含任何類型的樹，從而封裝了包含數據的實際值特定資料結構。

我將節點定義為：

1
2
3
4
5
6
7
// Node 組成樹的單個節點
type Node struct {
    key   int
    value Item
    left  *Node // 左節點
    right *Node // 右節點
}

這個 key 值允許使用任何類型的項目，並且使用一個單獨的值來計算正確的位置。我實現它為整數，但它可以使用任何可以進行比較的類型。

將項目插入樹中需要使用遞歸，因為我們需要找到確定的位置來插入它。規則是，如果節點的鍵值小於當前節點的鍵值，我們將其作為左子節點插入，如果沒有左子節點。否則，我們使用左子節點作為基礎節點重新計算位置。對於右子節點也是同樣的原則。

遍歷是指遍歷樹的過程。我們實現三種不同的方法來遍歷，因為有三種不同的方法。以二元搜尋樹為例：

我們可以以以下方式進行遍歷：

  • 中序遍歷：通過遵循最小鏈接來訪問所有節點，直到找到最左側的葉節點，然後處理該葉節點，通過進入與當前節點關聯的下一個最小鍵值來移動到其他節點。在上面的圖中，遍歷順序為：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
12
13
------------------------------------------------
   ---[ 1
   ---[ 2
   ---[ 3
   ---[ 4
   ---[ 5
   ---[ 6
   ---[ 7
---[ 8
   ---[ 9
   ---[ 10
   ---[ 11
------------------------------------------------

下面是實現所需的代碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
// Package binarysearchtree 創建 ItemBinarySearchTree 的 Item 型資料結構
package binarysearchtree

import (
    "fmt"
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Item 是二元搜尋樹的類型
type Item generic.Type

// Node 組成樹的單個節點
type Node struct {
    key    int
    value  Item
    left   *Node  // 左節點
    right  *Node  // 右節點
}

// ItemBinarySearchTree 是 Item 的二元搜尋樹
type ItemBinarySearchTree struct {
    root *Node
    lock sync.RWMutex
}

// Insert 將項目 t 插入樹中
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)
    }
}

// 尋找樹中某一個節點的正確位置的內部函數
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 通過中序遍歷訪問所有節點
func (bst *ItemBinarySearchTree) InOrderTraverse(f func(Item)) {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    inOrderTraverse(bst.root, f)
}

// 中序遞歸遍歷的內部函數
func inOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        inOrderTraverse(n.left, f)
        f(n.value)
        inOrderTraverse(n.right, f)
    }
}

// PreOrderTraverse 通過先序遍歷訪問所有節點
func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(Item)) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    preOrderTraverse(bst.root, f)
}

// 先序遞歸遍歷的內部函數
func preOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        f(n.value)
        preOrderTraverse(n.left, f)
        preOrderTraverse(n.right, f)
    }
}

// PostOrderTraverse 通過後序遍歷訪問所有節點
func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(Item)) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    postOrderTraverse(bst.root, f)
}

// 後序遞歸遍歷的內部函數
func postOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        postOrderTraverse(n.left, f)
        postOrderTraverse(n.right, f)
        f(n.value)
    }
}

// Min 返回存儲在樹中的最小值項目
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 返回存儲在樹中的最大值項目
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 如果項目 t 存在於樹中，則返回 true
func (bst *ItemBinarySearchTree) Search(key int) bool {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    return search(bst.root, key)
}

// 在樹中搜索項目的內部遞歸函數
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 從樹中刪除鍵為 key 的項目
func (bst *ItemBinarySearchTree) Remove(key int) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    remove(bst.root, key)
}

// 刪除項目的內部遞歸函數
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 {
        // 在右邊找到最小值
        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 打印樹的可視化結果
func (bst *ItemBinarySearchTree) String() {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    fmt.Println("------------------------------------------------")
    stringify(bst.root, 0)
    fmt.Println("------------------------------------------------")
}

// 打印樹的內部遞歸函數
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)
    }
}

測試：

下面的測試描述了上述實現的用法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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()

    bst.Insert(11, "11")
    bst.String()
}

// 如果兩個切片完全相同，則返回 true
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("遍歷順序不正確，得到的結果是：%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("遍歷順序不正確，得到的結果是：%v", result)
    }
}

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("遍歷順序不正確，得到的結果是：%v", result)
    }
}

func TestMin(t *testing.T) {
    if fmt.Sprintf("%s", *bst.Min()) != "1" {
        t.Errorf("最小值應為 1")
    }
}

func TestMax(t *testing.T) {
    if fmt.Sprintf("%s", *bst.Max()) != "11" {
        t.Errorf("最大值應為 11")
    }
}

func TestSearch(t *testing.T) {
    if !bst.Search(1) || !bst.Search(8) || !bst.Search(11) {
        t.Errorf("搜索不正常")
    }
}

func TestRemove(t *testing.T) {
    bst.Remove(1)
    if fmt.Sprintf("%s", *bst.Min()) != "2" {
        t.Errorf("最小值應為 2")
    }
}

創建具體的樹資料結構：

您可以使用此泛型實現生成特定類型的樹，例如：

  • 生成 IntBinarySearchTree，其中元素的類型是 int：
1
genny -in binarysearchtree.go -out binarysearchtree-int.go gen "Item=int"
  • 生成 StringBinarySearchTree，其中元素的類型是 string：
1
genny -in binarysearchtree.go -out binarysearchtree-string.go gen "Item=string"

tags: [“Go”, “Data Structures”, “Binary Search Tree”, “Golang”]