1.2 博主手记：核心特性

1.2.1 多元化的结构： 灵活的数据结构

BST支持动态数据集合的高效操作，适合频繁插入、删除和查找的场景。

1.2.2 天然的搜索优势：擅长搜索的数据结构

利用二叉树的分支特性，BST在平均情况下能实现O(logn)的搜索效率。

---

2 ~> 二叉搜索树性能分析

2.1 时间复杂度分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：logN； 最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：N； 所以综合而言二叉搜索树增删查改时间复杂度为：O(N)。

那么这样的效率显然是无法满足我们需求的，因此后面艾莉丝会介绍二叉搜索树的变形——平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。

2.2 二分查找的局限性

另外需要说明的是，二分查找也可以实现O(logN)级别的查找效率，但是二分查找有两大缺陷——

（1）需要存储在支持下标随机访问的结构中，并且有序； （2）插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

（1）数据越有序，插入结果越坏——高度高、递归深、效率低，如右图所示； （2）插入越无序的数据，左右会平衡一点，结果反而越好，如左图所示

2.3 博主手记：性能优化要点

---

3 ~> 实现二叉搜索树的定义

3.1 命名规范

二叉搜索树常简写为BST，提高代码可读性（SBT不好听），二叉搜索树也叫搜索二叉树。

3.2 定义节点

代码语言：javascript

AI代码解释

template<class K>
struct BSTreeNode {
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;
    
    BSTreeNode(const K& key)
        : _left(nullptr), _right(nullptr), _key(key)
    {}
};

3.3 实践：完整的类定义

提供插入、查找、删除等基本操作的接口设计。

---

4 ~> 二叉树搜索的插入操作详解

4.1 插入算法流程

从根节点开始，根据键值大小选择左子树或右子树，直到找到空位置插入新节点。

插入分成以下三种情况——

（1）树为空，则直接新增结点，赋值给root指针； （2）树不空，按二叉搜索树性质，插入值比当前结点大就往右走，插入值比当前结点小就往左走，找到空位置，插入新结点； （3）如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点（要注意保持逻辑一致性，插入相等的值不要一会往右走，一会又往左走）。