加工并存储数据的数据-二叉搜索树

• 插入一个数值
• 查询是否包含否个数值
• 删除某个数值
  

节点的左孩子节点比自己小，右孩子比自己大。因此，在中序遍历下，是递增的结果。

搜索： 从根节点开始比较，如果比根节点大，则往右走，否则往左走。如此反复，直至找到为止。

假设想要查找10：

插入： 插入过程与搜索类似，找到自己的位置插入。

插入6的例子：

删除： 这种情况需要分两类讨论。因为，二叉搜索树需要满足小中大的关系。因此：

1. 需要删除的节点有左孩子就提左孩子，没有左孩子就提右孩子。
2. 以上两种情况都不满足，就把左孩子的子孙最大的节点提到删除的节点上。

O(logn)

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

func (node *Node) insert(x int) *Node {
	if node == nil {
		node = &Node{Val: x, Left: nil, Right: nil}
	} else {
		if node.Val > x {
			node.Left = node.Left.insert(x)
		} else {
			node.Right = node.Right.insert(x)
		}
	}
	return node
}

func (node *Node) find(x int) bool {
	if node == nil {
		return false
	} else if x == node.Val {
		return true
	} else if x < node.Val {
		return node.Left.find(x)
	} else {
		return node.Right.find(x)
	}
}

func (node *Node) remove(x int) *Node {
	if node == nil {
		return nil
	} else if x < node.Val {
		node.Left = node.Left.remove(x)
	} else if x > node.Val {
		node.Right = node.Right.remove(x)
	} else if node.Left == nil {
		return node.Right
	} else if node.Left.Right == nil {
		node.Left.Right = node.Right
		return node.Left
	} else {
		var q *Node
		for q = node.Left; q.Right.Right != nil; q = q.Right {
		}
		r := q.Right
		q.Right = r.Left
		r.Left = node.Left
		r.Right = node.Right
		return r
	}
	return node
}

Go中没有提供二叉搜索树的标准库，Go的map是基于哈希的，无序的。与C++中的map不同，C++中的map是基于红黑树构建的。Go有红黑树的第三方库，有兴趣的可以了解和使用。