1. 理论推导过程
二叉搜索树的基本定义
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其每个节点都满足以下性质：
左子树所有节点的键值均小于根节点的键值；
右子树所有节点的键值均大于根节点的键值；
左右子树本身也是二叉搜索树。
这一性质保证了在树中查找一个元素时，可以利用二分查找的思想，从根节点出发，根据键值大小选择左子树或右子树，从而大大减少查找次数。
理论推导
查找操作：
对于给定的键值x：从根节点开始比较，如果
x等于当前节点的键值，则查找成功；如果
x小于当前节点的键值，则递归地在左子树中查找；如果
x大于当前节点的键值，则递归地在右子树中查找。
插入操作：
插入一个新键时，利用查找操作定位到应插入的位置（即找到一个空子树），然后将新键作为该空位置的节点插入，同时保证新树依然满足 BST 的定义。删除操作：
删除一个节点时需要考虑三种情况：叶子节点：直接删除即可；
只有一个子树的节点：用子树替代该节点；
有两个子树的节点：通常找该节点右子树中最小的节点（或左子树中最大的节点）来替代，然后删除该节点，保证树的有序性。
2. 使用步骤
以常见操作为例，说明 BST 的使用步骤：
查找操作
从根节点开始；
若当前节点为空，则返回“未找到”；
比较
x与当前节点的键值：若相等，则查找成功；
若
x小于当前节点键值，则移动到左子树；若
x大于当前节点键值，则移动到右子树；
重复步骤 2-3，直到查找结束。
插入操作
从根节点开始；
若当前节点为空，则插入新节点；
比较新键
x与当前节点键值：若
x小于当前节点键值，则递归插入到左子树；若
x大于当前节点键值，则递归插入到右子树；
插入后返回根节点，保证树结构不变。
删除操作
查找要删除的节点；
根据该节点的子树情况分类讨论：
叶子节点：直接删除；
一个子树：用子树代替该节点；
两个子树：找右子树中最小节点（或左子树中最大节点）替换当前节点，然后删除替换节点；
调整链接，保证 BST 性质不变。
3. 时间复杂度推导
平均情况：
在一棵平衡的 BST 中，每次操作沿着树的高度进行查找、插入或删除。
平均情况下，树的高度为 O(logn) （n 为节点数），因此平均时间复杂度为：查找：O(logn)
插入：O(logn)
删除：O(logn)
最坏情况：
当 BST 退化为链表（例如插入的键已经有序），树的高度为 O(n) ；
此时，操作的时间复杂度退化为：查找：O(n)
插入：O(n)
删除：O(n)
4. 应用场景
二叉搜索树因其高效的查找、插入和删除操作，在以下场景中被广泛应用：
字典/映射数据结构： 用于存储键值对，实现快速查找和动态更新。
集合操作： 用于集合的存储和去重，支持高效的范围查询。
数据库索引： 在数据库中，通过 BST 或其平衡变种（如 AVL 树、红黑树）加速数据检索。
符号表： 在编译器和解释器中维护标识符与其属性的映射。
5. 示例
假设我们有一组待插入的键：[50, 30, 70, 20, 40, 60, 80]，我们一步步构造 BST。
插入过程
插入 50
当前树为空，50 成为根节点。
当前树结构：
50插入 30
比较 30 与根 50，30 < 50，插入到左子树。
当前树结构：
50 / 30插入 70
比较 70 与根 50，70 > 50，插入到右子树。
当前树结构：
50 / \ 30 70插入 20
20 < 50，进入左子树；20 < 30，插入到 30 的左侧。
当前树结构：
50 / \ 30 70 / 20插入 40
40 < 50，进入左子树；40 > 30，插入到 30 的右侧。
当前树结构：
50 / \ 30 70 / \ 20 40插入 60
60 > 50，进入右子树；60 < 70，插入到 70 的左侧。
当前树结构：
50 / \ 30 70 / \ / 20 40 60插入 80
80 > 50，进入右子树；80 > 70，插入到 70 的右侧。
最终 BST 结构：
50 / \ 30 70 / \ / \ 20 40 60 80
查找操作示例
例如查找 60：
从根 50 开始：60 > 50，进入右子树；
在节点 70：60 < 70，进入左子树；
在节点 60：找到目标。
删除操作示例
例如删除 70：
节点 70 有两个子树，常见做法是找右子树中最小的节点，此处为 80 的左子树为空，则 80 为最小；
或者找左子树中最大的节点（这里为 60）。
假设我们选择使用 60 替换 70：将 60 替换到 70 的位置，然后删除原来的 60 节点（由于 60 为叶子节点，直接删除）。
最终树结构变为：50 / \ 30 60 / \ \ 20 40 80