1. 二叉搜索树的概念
二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它或者是一棵空树，或者是一棵具有以下性质的树：
- 如果它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
- 如果它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
- 它的左右子树也分别为二叉搜索树。
- 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，这取决于具体的使用场景。本文讨论的二叉搜索树实现不支持插入相等的值。
🌳 二叉搜索树的特性：
- 每个节点都带着唯一编号（键值）
- 左分拣区的所有包裹编号 < 当前包裹编号
- 右分拣区的所有包裹编号 > 当前包裹编号
📦 递归定义：
假设收到一个编号为50的包裹：
- 如果当前货架是空的 ➔ 直接把这个包裹放上去
- 如果货架上已有编号70的包裹 ➔ 把新包裹扔到左边货架区（因为 50<70）
- 如果货架上已有编号30的包裹 ➔ 把新包裹扔到右边货架区（因为 50>30）
每个货架都会对后续包裹重复这个操作，最终形成这样的结构：
[50] / \ [30] [70] / \ / \ [20][40][60][80]
⚡ 核心优势：
- 闪电查找：找编号 63 的包裹？从 50→70→60→... 每次淘汰一半错误选项
- 自动排序：中序遍历（左→中→右）直接输出有序序列
- 动态更新：新增/删除包裹时，整个货架体系会自动重新组织路线
💣 常见误区：
[50] / \ [30] [70] / \ [60] [80] / [55] // 合法！60>55 且 55>50？ // 不！虽然 55>50，但它出现在 70 的左子树里 // 而 55<70 是合法的，整体依然满足 BST 定义
❌ 这不是二叉搜索树：
[50] / \ [30] [70] / \ [20] [80] // 灾难！20 出现在 70 的左子树 // 但 20<50，应该在整个左半区
2. 二叉搜索树的性能分析
2.1. 样例对比
如果需要对一组数据进行搜索，常见的解法有：
1. 纯暴力求解
通过循环一个一个进行查找。如果数据恰巧在最后一个位置，则需要遍历整组数据，时间复杂度较高。对于新手来说较为友好，但在大数据量下效率低下。
2. 二分查找算法
时间复杂度为 O(logN)，对比暴力求解已有很大提升。但该算法有个很大的局限性：数组必须是'有序'的。此外，二分算法在插入和删除数据时效率较低。
2.2. 二叉搜索树的价值
根据二叉搜索树的定义，左边的结点的数据小，右边的数据大。利用这一特性可以进行查找：如果查找的数比根节点小，则找左子树；反之则找右子树。
1. 最优情况： 二叉搜索树为完全二叉树（或接近完全二叉树），其高度为 log₂N，时间复杂度大致为 O(logN)。
2. 最差情况： 二叉搜索树退化为单支树（或类似单支），其高度为 N，时间复杂度大致为 O(N)。
综合来看，二叉搜索树进行数据增删查的时间复杂度在平均情况下优于暴力查找，且比二分查找更灵活。大多数情况下我们遇不到最差的二叉搜索树。不过其实二叉搜索树也不是一颗比较完美的树，后期的 AVL 树和红黑树才算是真正意义上的比较完美的树，不过这些都是后话了。如果我们一上来就说 AVL 和红黑树，相信不少读者会觉得难以啃下。二叉搜索树作为它们的基础，可以为它们的学习打好基础。
当然，学习二叉搜索树不仅仅是为了理论知识，其实现也是重点。后续将介绍具体的代码实现细节。
