二叉搜索树 (Binary Search Tree BST)

什么是二叉搜索树

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有以下性质：

1. 每个节点最多有两个子节点，分别称为左子节点和右子节点。
2. 左子树中的所有节点的值都小于根节点的值。
3. 右子树中的所有节点的值都大于根节点的值。
4. 左子树和右子树也都是二叉搜索树(递归性)。

二叉搜索树的性质

1. 有序性：通过中序遍历（In-order Traversal）二叉搜索树，可以得到一个递增的有序序列。
2. 动态性：支持动态集合操作，如插入、删除、查找等，且平均时间复杂度为 O(log n)。
3. 平衡性：理想情况下的二叉搜索树是平衡的，即左右子树的高度差较小。但普通的二叉搜索树不保证自平衡，需要结合其他算法（如AVL树、红黑树）保持平衡。

二叉搜索树的实现

二叉搜索树的结构

// 二叉搜索树的节点
type BinarySearchTreeNode struct {
	Value int                   // 值
	Left  *BinarySearchTreeNode // 左子树
	Right *BinarySearchTreeNode // 右子树
}

// 二叉搜索树
type BinarySearchTree struct {
	Root *BinarySearchTreeNode
}

// 实例化
func NewBinarySearchTree() *BinarySearchTree {
	return &BinarySearchTree{}
}

二叉搜索树的插入操作

// 二叉搜索树 插入节点
func (BST *BinarySearchTree) Insert(val int) {
	// 定义一个递归函数 插入节点
	var insertNode func(node *BinarySearchTreeNode, val int) *BinarySearchTreeNode
	insertNode = func(node *BinarySearchTreeNode, val int) *BinarySearchTreeNode {
		// 如果节点为空，则创建新节点
		if node == nil {
			return &BinarySearchTreeNode{Val: val}
		}
		// 如果值小于节点值，则插入到左子树
		if val < node.Val {
			node.Left = insertNode(node.Left, val)
		} else if val > node.Val { // 如果值大于节点值，则插入到右子树
			node.Right = insertNode(node.Right, val)
		}
		return node
	}
	// 调用递归函数插入节点 从根节点开始
	BST.Root = insertNode(BST.Root, val)
}

二叉搜索树的查找操作

// 二叉搜索树 查找
func (BST *BinarySearchTree) Find(val int) *BinarySearchTreeNode {
	var findNode func(node *BinarySearchTreeNode, val int) *BinarySearchTreeNode
	findNode = func(node *BinarySearchTreeNode, val int) *BinarySearchTreeNode {
		if node == nil {
			return nil
		}
		if node.Val == val {
			return node
		} else if val < node.Val {
			return findNode(node.Left, val)
		} else {
			return findNode(node.Right, val)
		}
	}
	return findNode(BST.Root, val)
}

二叉搜索树的删除操作

// 二叉搜索树 删除
func (BST *BinarySearchTree) Delete(val int) {
	var deleteNode func(node *BinarySearchTreeNode, val int) *BinarySearchTreeNode
	deleteNode = func(node *BinarySearchTreeNode, val int) *BinarySearchTreeNode {
		if node == nil {
			return nil
		}
		if val < node.Val {
			node.Left = deleteNode(node.Left, val)
		} else if val > node.Val {
			node.Right = deleteNode(node.Right, val)
		} else {
			// 有两个子节点 找到右子树的最小节点
			if node.Left != nil && node.Right != nil {
				var findMin func(node *BinarySearchTreeNode) *BinarySearchTreeNode
				findMin = func(node *BinarySearchTreeNode) *BinarySearchTreeNode {
					if node.Left == nil {
						return node
					}
					return findMin(node.Left)
				}
				minNode := findMin(node.Right)
				node.Val = minNode.Val
				node.Right = deleteNode(node.Right, minNode.Val)
			} else if node.Left != nil { // 只有一个左子节点
				node = node.Left
			} else if node.Right != nil { // 只有一个右子节点
				node = node.Right
			} else { // 没有子节点 直接删除
				node = nil
			}
		}
		return node
	}
	BST.Root = deleteNode(BST.Root, val)
}

总结

时间复杂度

• 查找、插入、删除：平均时间复杂度为 O(log n)，但在最坏情况下（例如，插入有序数据导致树退化为链表），时间复杂度为 O(n)。

• 遍历操作：由于需要访问每个节点，时间复杂度为 O(n)。

优缺点

• 优点
  • 结构简单，易于实现：相比其他复杂的数据结构，二叉搜索树的概念和实现都较为直观。
  • 支持动态操作：能够高效地进行查找、插入和删除操作。
• 缺点
  • 不稳定的性能：在最坏情况下会退化为链表，导致时间复杂度上升为 O(n)。
  • 需要维护平衡：为了保证高效的性能，通常需要额外的机制（如旋转操作）来保持树的平衡。

改进与扩展

为了克服普通二叉搜索树的缺点，计算机科学家们设计了多种平衡二叉树：

• AVL树：通过严格的平衡条件，保证树的高度在 O(log n) 内。
• 红黑树：放宽平衡条件，使用颜色属性，提供较好的性能，同时维护成本较低。
• 伸展树（Splay Tree）：一种自调整的二叉搜索树，最近访问的节点会被旋转到根部，提高局部性。