1. 二叉搜索树的概念
二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它要么是一棵空树，要么是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
- 它的左右子树也分别为二叉搜索树。
- 二叉搜索树中可以支持插入相等的值，也可以不支持，具体取决于使用场景。例如，C++ STL 中的
std::map/std::set不支持插入相等值，而std::multimap/std::multiset支持。
2. 二叉搜索树的性能分析
- 最优情况：二叉搜索树为完全二叉树（或接近完全二叉树），其高度为
O(log₂N)。 - 最差情况：二叉搜索树退化为单支树（类似链表），其高度为
O(N)。 因此，二叉搜索树增删查改的平均时间复杂度为O(log N)，最坏情况下为O(N)。
这种效率在极端情况下无法满足需求，因此后续引入了平衡二叉搜索树（如 AVL 树、红黑树）以保证内存中数据的存储和搜索效率。
对比二分查找：二分查找也能实现
O(log N)级别的查找效率，但存在两大缺陷：
- 数据必须存储在支持下标随机访问的结构中，且必须保持有序。
- 插入和删除效率低，因为需要移动大量数据。
3. 二叉搜索树的插入
插入的具体过程如下：
- 树为空，则直接新增节点，赋值给
root指针。 - 树不为空，则按照二叉搜索树的性质进行比较：插入值比当前节点大则往右走，比当前节点小则往左走，直到找到空位置插入新节点。
- 若支持插入相等的值，当插入值与当前节点值相等时，可统一约定往左或往右走，找到空位置后插入。（注意：需保证逻辑一致性，避免混乱）
示例数组：int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
插入后的树结构如下：
