二叉搜索树

树

说明

左子树小于根、右子树大于根；平均查找 O(log n)，退化时 O(n)。

分析

插入时从根比较，小值走左、大值走右，直到找到空位置。搜索和插入平均只经过树的高度，但有序输入可能把普通树退化成链表。

按2、1、3插入得到分叉，查3只需比较2和3；若按1、2、3插入则形成右链。O(log n)平均界依赖输入分布等假设；此实现遇相等键直接返回，不会新增重复节点。

查看图表代码

适用前提与边界

需要稳定对数复杂度时，应使用 AVL、红黑树等平衡结构。 空根插入会返回新根，调用方必须保存返回值；相等键在本例被忽略。

示例输入与调用

root := Insert(nil, 2)
	Insert(root, 1)
	Insert(root, 3)
	fmt.Println(root.Left.Value, root.Right.Value)

运行输出

1 3

完整 Go 示例

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func Insert(root *Node, x int) *Node {
	if root == nil {
		return &Node{Value: x}
	}
	if x < root.Value {
		root.Left = Insert(root.Left, x)
	} else if x > root.Value {
		root.Right = Insert(root.Right, x)
	}
	return root
}

func main() {
	root := Insert(nil, 2)
	Insert(root, 1)
	Insert(root, 3)
	fmt.Println(root.Left.Value, root.Right.Value)
}