golang 二叉查找树-Go服务器开发

二叉查找树（Binary Search Tree，简称 BST）是一种常用的数据结构，它具有以下特点：

左子树上所有节点的值均小于其父节点的值。
右子树上所有节点的值均大于其父节点的值。
左右子树也分别为二叉查找树。

在 golang 中实现一个二叉查找树可以使用如下代码：

type Node struct {
    value int   // 节点存储的值
    left  *Node // 左子节点指针
    right *Node // 右子节点指针
}

// 插入新元素
func (n *Node) Insert(value int) *Node {
    if n == nil { // 当前节点为空，创建一个新节点并返回
        return &Node{value: value}
    }
    if value < n.value { // 插入左子树
        n.left = n.left.Insert(value)
    } else if value > n.value { // 插入右子树
        n.right = n.right.Insert(value)
    }
    return n 
}

// 查找元素是否存在
func (n *Node) Search(value int) bool {
    if n == nil { // 根节点为空，直接返回 false 
        return false 
    }
    if value == n.value { // 找到了目标元素 
        return true 
    } else if value < n.value { // 在左子树中查找 
        return n.left.Search(value)
    } else { // 在右子树中查找 
        return n.right.Search(value)
    }
}

// 删除指定元素
func (n *Node) Delete(value int) *Node {
    if n == nil { // 根节点为空，直接返回 
        return nil 
    }
    if value < n.value { // 在左子树中删除目标元素 
        n.left = n.left.Delete(value)
        return n
    } else if value > n.value { // 在右子树中删除目标元素 
        n.right = n.right.Delete(value)
        return n 
    } else { // 找到了目标元素
        if n.left == nil && n.right == nil { // 情况1：没有子节点，直接删除 
            return nil
        } else if n.left == nil || n.right == nil { // 情况2：只有一个子节点，用该子节点替换当前节点即可 
            var child *Node
            if n.left != nil {
                child = n.left
            } else {
                child = n.right
            }
            return child 
        } else { // 情况3：有两个子节点，找到右子树的最小值来替换当前节点，并在右子树中递归删除该最小值节点。  
            min := findMin(n.right)
            minCopy := &Node{value: min}
            right := deleteMin(n.right)
            minCopy.left, minCopy.right = n.left, right
            return minCopy
        }
    }
}

// 查找右子树的最小值（用于删除情况3）
func findMin(n *Node) int {
    for ;n.left != nil; {
        n = n.left
    }
    return n.value 
}

// 删除右子树的最小值（用于删除情况3）
func deleteMin(n *Node) *Node {
    if n.left == nil {
        return n.right 
    }
    n.left = deleteMin(n.left)
    return n 
}

在该代码中，我们使用 Node 结构体来表示二叉查找树的节点，其中包含一个 value 值和左右子节点指针。具体实现如下：

插入新元素：从根节点开始遍历 BST，如果当前节点为空，则创建一个新节点并返回；否则比较插入值与当前节点值的大小关系，选择向左子树或右子树递归插入。
查找元素是否存在：从根节点开始遍历 BST，如果当前节点为空，则说明未找到目标元素；否则比较查找值与当前节点值的大小关系，选择向左子树或右子树递归查找。
删除指定元素：从根节点开始遍历 BST，如果当前节点为空，则说明未找到目标元素；否则比较删除值与当前节点值的大小关系，选择向左子树或右子树递归删除。对于要删除的三种情况分别进行处理：没有子节点直接删除、只有一个子节点用该子节点替换、有两个子节点则将其替换为右子树中最小值，并在右子树中递归删除该最小值节点。

时间复杂度：插入、查找和删除操作的平均时间复杂度为 \(O(log n)\)，但在最坏情况下可能会退化成链表，时间复杂度为 \(O(n)\)。

空间复杂度：\(O(n)\)

稳定性：不稳定