数据结构——二叉搜索树

目录

引言

二叉搜索树

一、基本概念

二、性能分析 

三、具体实现

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 K> struct BSTNode { // 构造函数 BSTNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) { // ... } BSTNode<K>* _left; // 左子树 BSTNode<K>* _right; // 右子树 K _key; // 键值 };

有了BSTNode构造体，接下来我们就可以试着构建二叉搜索树：

template<class K> class BSTree { typedef BSTNode<K> 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<K> 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 K& key) { return _InsertR(_root, key); } bool _insertR(Node*& root, const K& 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 K& 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 K& key) { return _FindR(_root, key); } bool _FindR(Node* root, const K& 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 K& key) { Node* cur = _root; while (cur) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return true; } } // 遇空则返回false return false; }

5.删除操作

删除操作比较复杂，我们需要分情况详细讨论一下：

1.节点是叶子节点：如果要删除的节点是叶子节点（即没有子节点），那么直接删除该节点即可。

2.节点有一个子节点：如果要删除的节点只有一个子节点，那么用该子节点替换被删除的节点。

3.节点有两个子节点：如果要删除的节点有两个子节点，则需要找到该节点的中序后继（右子树中的最小节点）或中序前驱（左子树中的最大节点），用该后继或前驱节点的值替换被删除的节点，然后递归删除该后继或前驱节点（此时该后继或前驱节点最多只能有一个子节点，或者是一个叶子节点，因此删除操作会变得相对简单）。

递归方法：

 bool Erase(const K& key) { return _EraseR(_root, key); } bool _EraseR(Node*& root, const K& 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 K& 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模型的基础上改造一下，我们就不多论述了。

五、源码

K模型

头文件.h

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include <utility> using namespace std; namespace K { template<class K> struct BSTNode { // 构造函数 BSTNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) { // ... } BSTNode<K>* _left; // 左子树 BSTNode<K>* _right; // 右子树 K _key; // 键值 }; template<class K> class BSTree { typedef BSTNode<K> 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<K>& operator=(BSTree<K> 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 K& key) { return _InsertR(_root, key); } bool Insert(const K& 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 K& key) { return _FindR(_root, key); } bool Find(const K& key) { Node* cur = _root; while (cur) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return true; } } // 遇空则返回false return false; } bool EraseR(const K& key) { return _EraseR(_root, key); } bool Erase(const K& 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 K& 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 K& 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 K& 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() { // 创建一个二叉搜索树 K::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; }

KV模型

头文件：

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include <utility> using namespace std; namespace KV { template<class K,class V> struct BSTNode { // 构造函数 BSTNode(const K& key,const V& val) :_left(nullptr) , _right(nullptr) , _key(key) , _val(val) { // ... } BSTNode<K, V>* _left; // 左子树 BSTNode<K, V>* _right; // 右子树 K _key; // 键值 V _val; }; template<class K,class V> class BSTree { typedef BSTNode<K,V> Node; public: BSTree() { // ... } BSTree(const BSTree<K,V>& 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<K,V>& operator=(BSTree<K,V> 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 K& key,const V& val) { return _InsertR(_root, key, val); } bool Insert(const K& key, const V& val) { // 如果树为空，则创建树 if (_root == nullptr) { _root = new Node(key, val); 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, val); // 判断新节点应该插入到父节点的左子树还是右子树 if (key < parent->_key) { parent->_left = cur; } else { parent->_right = cur; } return true; } bool FindR(const K& key) { return _FindR(_root, key); } bool Find(const K& key) { Node* cur = _root; while (cur) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return true; } } // 遇空则返回false return false; } bool EraseR(const K& key) { return _EraseR(_root, key); } bool Erase(const K& 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->_val << " "; InOrder(root->_right); } private: Node* _root = nullptr; bool _InsertR(Node*& root, const K& key, const V&val) { if (root == nullptr) { root = new Node(key, val); return true; } if (key < root->_key) { // 递归地在左子树中插入 return _InsertR(root->_left, key, val); } else if (key > root->_key) { // 递归地在右子树中插入 return _InsertR(root->_right, key, val); } else { return false; } } bool _FindR(Node* root, const K& 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 K& 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; } } }; }

测试文件：

#include "二叉搜索树KV模型.h" int main() { // 创建一个英汉词典 KV::BSTree<string, string> dictionary; // 插入一些单词和对应的中文翻译 dictionary.Insert("apple", "苹果"); dictionary.Insert("banana", "香蕉"); dictionary.Insert("cherry", "樱桃"); dictionary.Insert("date", "枣"); dictionary.Insert("grape", "葡萄"); // 测试查找功能 cout << "查找单词 'banana' 的中文翻译: "; if (dictionary.Find("banana")) { cout << "找到！" << endl; } else { cout << "未找到！" << endl; } cout << "查找单词 'grape' 的中文翻译: "; if (dictionary.Find("grape")) { cout << "找到！" << endl; } else { cout << "未找到！" << endl; } // 测试中序遍历（按英文单词的字典序输出） cout << "中序遍历（按英文单词的字典序输出）: "; dictionary.InOrder(); cout << endl; // 测试删除功能 cout << "删除单词 'banana'..." << endl; dictionary.Erase("banana"); // 再次中序遍历 cout << "删除后中序遍历: "; dictionary.InOrder(); cout << endl; return 0; }

结束语

在某些情况下，二叉搜索树的性能可能受到树的高度不平衡的影响，导致操作的时间复杂度接近O(N)。在接下来的学习中我们会试着解决这个问题。

求点赞收藏评论关注~

十分感谢！！！