概念

二叉排序树（Binary Sarech/Sort Tree）或者是一颗空树；或者是具有如下性质的二叉树：

(1) 若它的左子树不空，则 左子树 上所有结点的值 均小于 它的根结点的值；
(2) 若它的右子树不空，则 右子树 上所有结点的值 均大于 它的根结点的值；
(3) 它的 左、右子树又分别为二叉排序树 。

比如一下值: 8、3、10、1、6、14、4、7、13，构造BTS的过程如下：

存储结构

1
2
3
4
5
type Node struct {
    Value string
    Left *Node
    Right *Node
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// SearchBST 这里假设值都是int，不做异常预期判断了，咱们就简单理解算法即可
func SearchBST(targetNode *Node,value int) *Node {
	// 如果根节点为nil， 则肯定不存在
	if targetNode ==  nil {
		return nil
	}

	if value == targetNode.Value.(int)  {
		return targetNode
	}

	if value < targetNode.Value.(int) {
		return SearchBST(targetNode.Left, value)
	}

	if value > targetNode.Value.(int) {
		return SearchBST(targetNode.Right, value)
	}

	return nil
}

插入

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
func InsertBST(targetNode *Node, value int) {
	if targetNode == nil {
		targetNode.Value = value
		return
	}

	if targetNode.Value.(int) == value {
		return
	}

	if value < targetNode.Value.(int) {
		// 如果当前节点不存在左子树，则将该目标节点作为当前节点的左子树
		if targetNode.Left == nil {
			targetNode.Left = &Node{
				Value: value,
			}

			return
		}

		InsertBST(targetNode.Left, value)
	}

	if value > targetNode.Value.(int) {
		// 如果当前节点不存在右子树，则将该目标节点作为当前节点的右子树
		if targetNode.Right == nil {
			targetNode.Right = &Node{
				Value: value,
			}

			return
		}
		InsertBST(targetNode.Right, value)
	}

	return
}

删除

删除二叉搜索树的节点相对而言复杂一点，如果待删除的节点同时包含左右子树，删除后如何恢复搜索树是一个问题。

比如删除节点8， 那么是选举3作为根节点还是10呢？所以就需要我们一点点去梳理：

  1. 如果删除的节点是叶子结点（即没有左右子树），那么直接删除即可，比如上面的1、7、9、13.
  2. 如果删除的节点只有左子树或者只有右子树，则删除后将子节点直接指向删除节点的位置即可，比如6、14
  3. 还有一种情况就是同时存在左右子树的情况，比如8，为了维持删除后的树依然符合二叉搜索树特性，其实可以将左子树的最大值或者右子树的最小值转移到删除点位置比如将7放在8的位置，但是这里的7是叶子结点，直接删除即可，如果7还包含左右子树，其实可以递归删除替换即可。我们可以用一个比较大的BST来举例：
    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

    func DeleteBST(node *Node, value int) *Node {
    	// 如果二叉搜索树为nil，则直接返回
    	if node == nil {
    		return nil
    	}

    	// 如果当前节点的值等于待删除值
    	if node.Value == value {
    		// 如果当前节点没有左右子树，则直接删除
    		if node.Left == nil && node.Right == nil {
    			node = nil
    			return node
    		}

    		// 只有右边子树，直接用右子树覆盖
    		if node.Left == nil {
    			node = node.Right
    			return node
    		}

    		// 只有左子树，直接用左子树覆盖
    		if node.Right == nil {
    			node = node.Left
    			return node
    		}

    		if node.Left != nil && node.Right != nil {
    			// 找到左子树中最大值，将其设置为当前的值
    			maxInLeft := FindMaxInNodeBST(node.Left)
    			node.Value = maxInLeft.Value
    			node.Left = DeleteBST(node.Left, maxInLeft.Value.(int))
    			return node
    		}

    		return node
    	}

    	// 有左子树，并且当前节点的值小于目标值，则进入左子树递归查找删除
    	if node.Left != nil && value < node.Value.(int)  {
    		node.Left =  DeleteBST(node.Left, value)
    		return node
    	}

    	// 有右子树，并且当前节点的值大于目标值，则进入右子树递归查找删除
    	if node.Right != nil && value > node.Value.(int) {
    		node.Right = DeleteBST(node.Right, value)
    		return node
    	}

    	return node
    }

    func FindMaxInNodeBST(node *Node) *Node {
    	if node == nil {
    		return nil
    	}

    	// 树中的最大值肯定在根节点或者右子树中

    	// 如果左右子树都为空，则就是当前节点
    	if node.Left == nil && node.Right == nil {
    		return node
    	}