二叉搜索树（BST）是一种左子树值均小于根、右子树值均大于根的有序二叉树，支持查找、插入、删除等操作平均时间复杂度为O(log n)；Java实现需定义含值与左右子节点的TreeNode类及BinarySearchTree类，核心操作严格遵循“左小右大”规则，中序遍历天然有序，但树失衡时性能退化为O(n)，适用于动态增删与快速检索场景。
二叉搜索树（BST）在 Java 中实现高效动态检索，核心在于利用其“左小右大”的有序结构，把查找、插入、删除都控制在平均 O(log n) 时间内。它不依赖数组的连续内存或预排序，而是靠树形分支实时缩小范围，特别适合数据频繁增删又需快速定位的场景，比如用户权限索引、订单时间范围查询、词典自动补全等。
构建符合 BST 规则的节点与树结构
节点必须能存值、连左右子节点，并支持比较逻辑。Java 中常用泛型 + 自定义比较，避免硬编码 int 类型：
- 定义 TreeNode<T> 类，含
data、left、right字段；若需删除时回溯父节点，可加parent引用 - 树类（如
BinarySearchTree<T>）持有一个root引用，所有操作从根出发递归或迭代执行 - 关键约束：插入时严格遵循「左子树所有值 < 当前节点值 < 右子树所有值」，重复值通常丢弃（也可设计为允许重复并挂到左/右子树末端）
查找操作：像走迷宫一样逐层缩小范围
查找不是遍历，而是根据大小关系决定方向——每次比较后直接排除半个子树：
- 从
root开始，若目标值等于当前节点值，返回该节点 - 若目标值更小，转向
left；若更大，转向right - 走到
null说明不存在，返回null或抛异常 - 无需额外空间，迭代写法比递归更节省栈深度，尤其对深树更安全
插入操作：找到空位，一插即止
插入本质是查找的延伸——找到第一个空子节点位置，把新节点挂上去，全程保持 BST 性质：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
立即学习“Java免费学习笔记（深入）”；
- 空树时，新节点直接设为
root - 非空时，沿查找路径下行，记录最后的父节点
- 比较父节点值与新值：新值小则挂左，大则挂右；相等按策略处理（跳过 or 允许重复）
- 注意：插入不改变已有结构，只新增叶子或半叶子节点，无重平衡开销
删除操作：分三类处理，重点解决“双子节点”情况
删除最难，因要维持 BST 结构。分三种情况统一处理：
-
无子节点（叶子）：直接移除，父节点对应指针置
null - 仅一个子节点：用该子节点替代被删节点，接回父节点
- 两个子节点：找中序后继（右子树最左节点）或中序前驱（左子树最右节点），用它的值覆盖被删节点，再递归删掉那个后继/前驱节点——这样既保序，又把复杂删除转为简单叶子删除
中序遍历：天然输出有序序列
BST 的中序遍历（左→根→右）结果必为升序排列，这是它区别于普通二叉树的关键价值：
- 可用于快速获取范围数据，比如查“价格在 100–500 之间的商品”，只需中序遍历中截取对应区间
- 配合递归或栈模拟，时间复杂度 O(n)，空间 O(h)（h 为树高）
- 实际业务中常封装为
toList()或rangeQuery(low, high)方法，直接返回有序列表
BST 的效率高度依赖树形是否平衡。理想情况下高度约 log₂n，但连续插入递增数据会让它退化成链表，操作变 O(n)。生产环境若要求稳定性能，应在 BST 基础上升级为 AVL 树或红黑树——它们通过旋转或染色自动维持近似平衡，确保最坏情况仍为 O(log n)。单纯用原生 BST，适合教学、中小规模动态数据或已知输入较随机的场景。
