Go 資料結構：二元搜尋樹

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

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

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

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

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

詞彙定義：

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

預備信息：

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

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

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

我將節點定義為：

// 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
------------------------------------------------

下面是實現所需的代碼：

// 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)
    }
}

測試：

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

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：

genny -in binarysearchtree.go -out binarysearchtree-int.go gen "Item=int"

生成 StringBinarySearchTree，其中元素的類型是 string：

genny -in binarysearchtree.go -out binarysearchtree-string.go gen "Item=string"