二叉搜索树

简介

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它的每个节点都包含一个可比较的键，并且满足特定的排序性质。

特性

1. 左子树的所有节点的值都小于当前节点的值
2. 右子树的所有节点的值都大于当前节点的值
3. 左右子树也都是二叉搜索树

基本操作

1. 查找
   • 平均时间复杂度：O(log n)
   • 最坏时间复杂度：O(n)
2. 插入
   • 平均时间复杂度：O(log n)
   • 最坏时间复杂度：O(n)
3. 删除
   • 平均时间复杂度：O(log n)
   • 最坏时间复杂度：O(n)

优缺点

优点

1. 支持快速查找、插入和删除操作
2. 保持数据的有序性
3. 适合范围查询

缺点

1. 可能退化为链表
2. 不是自平衡的
3. 性能依赖于输入顺序

应用场景

1. 数据库索引
2. 文件系统
3. 符号表