目录
引言
二叉搜索树
一、基本概念
二、性能分析
三、具体实现
1.基本结构
2.初始化和销毁
3.插入操作
4.查找操作
5.删除操作
四、应用场景
1.K模型
2.KV模型
五、源码
结束语
引言
在之前的学习中，我们已经对二叉树有所了解。详细内容可以看看我写的这篇文章：
数据结构——二叉树
本篇文章是二叉树的进阶部分，我们要学习的是二叉搜索树。
二叉搜索树
一、基本概念
二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树数据结构（也称二叉排序树或二叉查找树）。它有如下几点性质：
1.它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树
4.空树也是一颗二叉搜索树
下面这棵树就是一个二叉搜索树：
二、性能分析
1.最优情况：当二叉搜索树为完全二叉树时，树的高度最小，为log₂N（其中N为节点数），此时查找、插入、删除等操作的时间复杂度最优，为O(log₂N)。
2.最坏情况：当二叉搜索树退化为链表时（所有节点都在同一侧），树的高度最大，为N，此时查找、插入、删除等操作的时间复杂度最坏，为O(N)。
三、具体实现
1.基本结构
二叉搜索树的构建与二叉树类似，为了使其能适应其他不同的数据类型，我们可以定义一个模板：
template<class T>struct BSTNode
{// 构造函数BSTNode(const T& key):_left(nullptr), _right(nullptr), _key(key){// ...}BSTNode<T>* _left; // 左子树BSTNode<T>* _right; // 右子树T _key; // 键值
};有了BSTNode构造体，接下来我们就可以试着构建二叉搜索树：
template<class T>
class BSTree
{typedef BSTNode<T> Node;
public:// ...
private:Node* _root = nullptr;
};2.初始化和销毁
（1）定义一个无参的构造函数
BSTree()
{// ...
}（2）递归实现拷贝构造函数
BSTree(const BSTree& t)
{_root = copy(t._root);
}
Node* copy(Node* root)
{if (root == nullptr){return nullptr;}Node* newnode = new Node(root->_key);newnode->_left = copy(root->_left);newnode->_right = copy(root->_right);return newnode;
}（3）实现赋值运算符的重载
BSTree<T>& operator=(const BSTree<T> t)
{//赋值重载this->swap(_root, t._root);return *this;
}（4）递归释放
~BSTree()
{Destroy(_root);
}
void Destroy(Node*& root)
{if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;
}3.插入操作
我们要如何实现二叉搜索树的插入功能呢？
1.比较值： 如果待插入的值小于当前节点的值，则递归或迭代到左子树。 如果待插入的值大于当前节点的值，则递归或迭代到右子树。 如果待插入的值等于当前节点的值，可以根据具体需求决定是否允许重复（通常二叉搜索树不允许重复值）。
2.插入节点： 当找到合适的位置（即当前节点为空）时，创建一个新节点并将其插入。
实现二叉搜索树的插入功能可以使用递归或者循环。
这两种方法各有优缺点：
递归方法
优点：
代码简洁：递归方法通常使代码更加简洁和直观，因为递归调用可以自然地反映树的结构。
逻辑清晰：递归方法符合分治法的思想，将大问题分解为小问题，每个小问题都与大问题具有相同的结构，这使得逻辑更加清晰。
缺点：
栈空间开销：递归方法需要系统栈来保存每次递归调用的状态，如果树很深，可能会导致栈溢出。
调试困难：递归调用栈的深度可能使得调试变得困难，因为需要跟踪多个递归层级的调用。
循环方法
优点：
空间效率高：循环不会占用额外的栈空间，适合处理深度较大的树。
性能较好：循环避免了函数调用的开销，通常比递归更快。
缺点：
代码复杂：循环的实现通常比递归复杂，需要手动维护指针或栈。
可读性差：逻辑可能不如递归直观。
我们来试着实现一下：
递归方法：
bool InsertR(const T& key){return _InsertR(_root, key);}bool _insertR(Node*& root, const T& key){if (root == nullptr){root = new Node(key);return true;}if (key < root->_key){// 递归地在左子树中插入return _InsertR(root->_left, key);}else if (key > root->_key){// 递归地在右子树中插入return _InsertR(root->_right, key);}else{return false;}}循环方法：
bool Insert(const T& key){// 如果树为空，则创建树if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr; // 记录父节点Node* cur = _root; // 记录根节点// 循环查找插入位置while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if{parent = cur;cur = cur->_right;}else{return false;}}// 找到插入位置后，创建一个新节点cur = new Node(key);// 判断新节点应该插入到父节点的左子树还是右子树if (key < parent->_key) {parent->_left = cur; }else {parent->_right = cur; }return true; }4.查找操作
1.从根节点开始： 查找操作从根节点开始。
2.比较目标值： 如果目标值等于当前节点的值，查找成功，返回当前节点。 如果目标值小于当前节点的值，继续在左子树中查找。 如果目标值大于当前节点的值，继续在右子树中查找。
3.终止条件： 如果遍历到空节点（nullptr），说明目标值不存在，查找失败。
递归方法：
bool FindR(const T& key){return _FindR(_root, key);}bool _FindR(Node* root, const T& key){if (root == nullptr){return false;}if (key < root->_key){return _FindR(root->_left, key);}else if (key > root->_key){return _FindR(root->_right, key);}else{return true;}}循环方法：
bool Find(const T& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}// 遇空则返回falsereturn false;}5.删除操作
删除操作比较复杂，我们需要分情况详细讨论一下：
1.节点是叶子节点：如果要删除的节点是叶子节点（即没有子节点），那么直接删除该节点即可。
2.节点有一个子节点：如果要删除的节点只有一个子节点，那么用该子节点替换被删除的节点。
3.节点有两个子节点：如果要删除的节点有两个子节点，则需要找到该节点的中序后继（右子树中的最小节点）或中序前驱（左子树中的最大节点），用该后继或前驱节点的值替换被删除的节点，然后递归删除该后继或前驱节点（此时该后继或前驱节点最多只能有一个子节点，或者是一个叶子节点，因此删除操作会变得相对简单）。
递归方法：
bool Erase(const T& key){return _EraseR(_root, key);}bool _EraseR(Node*& root, const T& key){if (root == nullptr){return false;}if (key < root->_key){return _EraseR(root->_left, key);}else if (key > root->_key){return _EraseR(root->_right, key);}// 找到要删除的节点else{// 记录要删除的节点Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{// 寻找左子树中的最大节点Node* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(maxleft->_key, root->_key);// 左子树中原来最大节点的键值// （现在等于原来要删除的键值 key）成为了要删除的键值。// 因此，我们递归地调用 _EraseR 函数，在左子树中查找并删除这个节点。return _EraseR(root->_left, key);}delete del;return true;}}循环方法：
bool Erase(const T& key){// 定义两个指针变量parent和cur，// 分别用于追踪当前节点的父节点和当前节点Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{// 目标节点没有左子节点if (cur->_left == nullptr){// 如果目标节点是根节点// 则根节点更新为目标节点的右子节点if (cur == _root){_root = cur->_right;}// 否则，根据目标节点是父节点的左子节点// 还是右子节点，更新父节点的相应指针为目标节点的右子节点else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;cur = nullptr;}// 目标节点没有右子节点else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_right;}}delete cur;cur = nullptr;}// 目标节点既有左子节点又有右子节点else{Node* replaceParent = cur;Node* replace = cur->_right;// 找到目标节点右子树中的最小节点while (replace->_left){replaceParent = replace;replace = replace->_left;}// 替换key值cur->_key = replace->_key;// 删除最小节点时的指针更新if (replaceParent->_left == replace){replaceParent->_left = replace->_right;}else{replaceParent->_right = replace->_right;}delete replace;replace = nullptr;}return true;}}return false;}四、应用场景
二叉搜索树有以下两种应用场景：
1.K模型
定义：
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
特点：
节点结构简单，只包含键值和指向左、右子节点的指针。
插入、查找和删除操作的时间复杂度在最优情况下为O(logN)，最坏情况下为O(N)，其中N为树中节点的数量。
由于只存储键值，因此不支持直接通过键值获取相关联的值。
2.KV模型
定义：
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
特点：
节点结构相对复杂，包含键值、与键值相关联的值以及指向左、右子节点的指针。
插入、查找和删除操作的时间复杂度同样在最优情况下为O(logN)，最坏情况下为O(N)。
支持通过键值快速查找对应的值。
我们上面所说的就是K模型，而KV模型需要在K模型的基础上改造一下，我们就不多论述了。各位可以去试着实现一下，
五、源码
头文件.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include <utility>
using namespace std;
template<class T>struct BSTNode
{// 构造函数BSTNode(const T& key):_left(nullptr), _right(nullptr), _key(key){// ...}BSTNode<T>* _left; // 左子树BSTNode<T>* _right; // 右子树T _key; // 键值
};template<class T>
class BSTree
{typedef BSTNode<T> Node;
public:BSTree(){// ...}BSTree(const BSTree& t){_root = copy(t._root);}Node* copy(Node* root){if (root == nullptr){return nullptr;}Node* newnode = new Node(root->_key);newnode->_left = copy(root->_left);newnode->_right = copy(root->_right);return newnode;}BSTree<T>& operator=(BSTree<T> t){//赋值重载swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool InsertR(const T& key){return _InsertR(_root, key);}bool Insert(const T& key){// 如果树为空，则创建树if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr; // 记录父节点Node* cur = _root; // 记录根节点// 循环查找插入位置while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{return false;}}// 找到插入位置后，创建一个新节点cur = new Node(key);// 判断新节点应该插入到父节点的左子树还是右子树if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;}bool FindR(const T& key){return _FindR(_root, key);}bool Find(const T& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}// 遇空则返回falsereturn false;}bool EraseR(const T& key){return _EraseR(_root, key);}bool Erase(const T& key){// 定义两个指针变量parent和cur，// 分别用于追踪当前节点的父节点和当前节点Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{// 目标节点没有左子节点if (cur->_left == nullptr){// 如果目标节点是根节点// 则根节点更新为目标节点的右子节点if (cur == _root){_root = cur->_right;}// 否则，根据目标节点是父节点的左子节点// 还是右子节点，更新父节点的相应指针为目标节点的右子节点else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;cur = nullptr;}// 目标节点没有右子节点else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_right;}}delete cur;cur = nullptr;}// 目标节点既有左子节点又有右子节点else{Node* replaceParent = cur;Node* replace = cur->_right;// 找到目标节点右子树中的最小节点while (replace->_left){replaceParent = replace;replace = replace->_left;}// 替换key值cur->_key = replace->_key;// 删除最小节点时的指针更新if (replaceParent->_left == replace){replaceParent->_left = replace->_right;}else{replaceParent->_right = replace->_right;}delete replace;replace = nullptr;}return true;}}return false;}void InOrder() {InOrder(_root);}void InOrder(Node* root) {if (root == nullptr) {return;}InOrder(root->_left);cout << root->_key << " ";InOrder(root->_right);}private:Node* _root = nullptr;bool _InsertR(Node*& root, const T& key){if (root == nullptr){root = new Node(key);return true;}if (key < root->_key){// 递归地在左子树中插入return _InsertR(root->_left, key);}else if (key > root->_key){// 递归地在右子树中插入return _InsertR(root->_right, key);}else{return false;}}bool _FindR(Node* root, const T& key){if (root == nullptr){return false;}if (key < root->_key){return _FindR(root->_left, key);}else if (key > root->_key){return _FindR(root->_right, key);}else{return true;}}bool _EraseR(Node*& root, const T& key){if (root == nullptr){return false;}if (key < root->_key){return _EraseR(root->_left, key);}else if (key > root->_key){return _EraseR(root->_right, key);}// 找到要删除的节点else{// 记录要删除的节点Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{// 寻找左子树中的最大节点Node* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(maxleft->_key, root->_key);// 左子树中原来最大节点的键值// （现在等于原来要删除的键值 key）成为了要删除的键值。// 因此，我们递归地调用 _EraseR 函数，在左子树中查找并删除这个节点。return _EraseR(root->_left, key);}delete del;return true;}}
};测试文件.cpp
#include"二叉搜索树.h"int main()
{// 创建一个二叉搜索树BSTree<int> bst;// 测试插入功能bst.Insert(10);bst.Insert(5);bst.Insert(15);bst.Insert(3);bst.Insert(7);// 测试递归插入功能bst.InsertR(12);bst.InsertR(8);bst.InOrder();cout << endl;if (bst.Find(5)){cout << "find" << endl;}else{cout << "no find" << endl;}//bst.Erase(5);bst.EraseR(5);bst.InOrder();return 0;
}结束语
在某些情况下，二叉搜索树的性能可能受到树的高度不平衡的影响，导致操作的时间复杂度接近O(N)。在接下来的学习中我们会试着解决这个问题。
求点赞收藏评论关注~
十分感谢！！！