【数据结构进阶】二叉搜索树

在这里插入图片描述

🔥个人主页： Forcible Bug Maker
🔥专栏： C++ || 数据结构

🌈前言

本篇博客主要内容：二叉搜索树的介绍及自实现。

基础的二叉树在前面的C数据结构阶段已经讲过（初阶数据结构之—二叉树链式结构）。之前因为用C语言的话，实现更高级数据结构比较困难，所以并没有往后展开。到了现在，已经有了一定的C++功底，就可以开启我们数据结构进阶部分的内容了。对于二叉搜索树的特性了解，有助于后续更好的理解map和set的特性。本节课作为学习更高阶数据结构的基础，对后续学习来说至关重要。

🔥二叉搜索树

二叉搜索树的概念：
二叉搜索树又称二叉排序树，它或者是一颗空树，或者具有以下三种性质：

若它的左子树不为空，则左子树上的所有结点都小于根节点的值
若它的右子树不为空，则右子树上的所有结点都大于根节点的值
它的左右子树也分别为二叉搜索树

二叉搜索树的中序遍历是有序的。

在这里插入图片描述

🔥 二叉搜索树的实现

在这里插入图片描述
以下是需要实现的二叉搜索树的头文件内容

#pragma once
#include<iostream>namespace ForcibleBugMaker
{template<class K>struct BSTreeNode{BSTreeNode<K>(const K& k = K()):_key(k), _left(nullptr), _right(nullptr){}K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;};template<class K>class BSTree{typedef BSTreeNode<K> Node;public:BSTree() = default;BSTree(const BSTree<K>& t);bool Insert(const K& key);Node* Find(const K& key);bool Erase(const K& key);~BSTree();void InOrder();private:Node* _root = nullptr;};
}

二叉搜索树的结点中有三个成员变量，分别是
_key：存储数据；_left：指向左子树；_right：指向右子树。将其在BSTree中typedef成Node方便后续使用。

Insert（插入）

二叉树的插入，主要考虑两种情况：

树为空，则直接新增结点，赋给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 (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else return false;}if (parent->_key < key) parent->_right = new Node(key);else parent->_left = new Node(key);return true;
}

find（查找）

二叉搜索树的查找：

从根开始比较，比跟大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到空，还没找到，这个值不存在。

Node* Find(const K& key)
{Node* cur = _root;while (cur) {if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;else return cur;}return nullptr;
}

erase(删除)

删除的逻辑相比其他的实现来说复杂很多，二叉搜索树的删除：
首先查找元素是否在二叉搜索树中，如果不存在，则返回；否则要删除结点可能分以下三种情况：

被查找到的结点无孩子（直接删除）
被查找到的结点有一个孩子（删除结点，将孩子交给父亲）
被查找到的结点有两个孩子（在其右孩子中找最左边的孩子（如果此孩子不存在，则为该结点右孩子），用它的值填补到被删除结点中，再来处理增补结点的删除。）相当于找一个合适的子节点替代

在这里插入图片描述

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else {if (cur == _root && cur->_left == nullptr) {_root = cur->_right;delete cur;return true;}else if (cur == _root && cur->_right == nullptr) {_root = cur->_left;delete cur;return true;}if (cur->_left == nullptr) {if (parent->_right == cur)parent->_right = cur->_right;elseparent->_left = cur->_right;delete cur;}else if (cur->_right == nullptr) {if (parent->_right == cur)parent->_right = cur->_left;elseparent->_left = cur->_left;delete cur;}else {Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left) {rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;cur->_value = rightMin->_value;if (rightMinP == cur)rightMinP->_right = rightMin->_right;elserightMinP->_left = rightMin->_right;delete rightMin;}return true;}}return false;
}

destroy（析构）

二叉树的析构需要传入根结点，通过后序遍历递归实现，但是从外界无法访问对象内部的私有成员_root。所以咱们可以实现一个工具函数，用来帮助完成二叉搜索树的析构。

~BSTree()
{Destroy(_root);_root = nullptr;
}void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}

InOrder（中序遍历）

逻辑跟析构一样。中序遍历下来的key是有序的。

void InOrder()
{_InOrder(_root);std::cout << std::endl;
}void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);
}

拷贝构造

本质上就是实现一次二叉树的深拷贝，也是嵌套了一个递归。

BSTree(const BSTree<K>& t)
{_root = _Copy(t._root);
}Node* _Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;
}

🔥二叉搜索树的应用

像我们刚刚实现的，只存一个数据，是典型的K模型；如果存两个数据，那就是KV模型。

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

**KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。**该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

在以上实现K模型的基础上，实现KV模型无非就是让结点多存储一个元素，给模板增添一个类型，具体实现代码如下：

#pragma once
#include<iostream>namespace ForcibleBugMaker
{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>(const K& k = K(), const V& v = V()):_key(k), _value(v), _left(nullptr), _right(nullptr){}K _key;V _value;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:BSTree() = default;BSTree(const BSTree<K, V>& t){_root = _Copy(t._root);}bool Insert(const K& key, const V& value){if (_root == nullptr) {_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else return false;}if (parent->_key < key) parent->_right = new Node(key, value);else parent->_left = new Node(key, value);return true;}Node* Find(const K& key){Node* cur = _root;while (cur) {if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;else return cur;}return nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else {if (cur == _root && cur->_left == nullptr) {_root = cur->_right;delete cur;return true;}else if (cur == _root && cur->_right == nullptr) {_root = cur->_left;delete cur;return true;}if (cur->_left == nullptr) {if (parent->_right == cur)parent->_right = cur->_right;elseparent->_left = cur->_right;delete cur;}else if (cur->_right == nullptr) {if (parent->_right == cur)parent->_right = cur->_left;elseparent->_left = cur->_left;delete cur;}else {Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left) {rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;cur->_value = rightMin->_value;if (rightMinP == cur)rightMinP->_right = rightMin->_right;elserightMinP->_left = rightMin->_right;delete rightMin;}return true;}}return false;}~BSTree(){Destroy(_root);_root = nullptr;}void InOrder(){_InOrder(_root);std::cout << std::endl;}private:Node* _Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_key << ":" << root->_value << " ";_InOrder(root->_right);}Node* _root = nullptr;};
}

🔥二叉搜索树的性能

二叉搜索树（Binary Search Tree, BST）的性能主要取决于其结构。理想情况下，二叉搜索树是一个平衡树，其中每个节点的左子树只包含小于节点值的元素，右子树只包含大于节点值的元素，且左、右子树的高度大致相等。然而，在实际应用中，由于插入和删除操作的随机性，二叉搜索树可能会退化为链表状结构（即所有节点都偏向一侧），这会导致其性能急剧下降。
在这里插入图片描述
时间复杂度：

搜索（Search）：在平衡的二叉搜索树中，搜索操作的时间复杂度为O(log n)，其中n是树中节点的数量。这是因为每次递归或迭代都排除了一半的搜索空间。但在最坏的情况下（树退化为链表），时间复杂度会退化为O(n)。
插入（Insert）和删除（Delete）：同样，在平衡的二叉搜索树中，插入和删除操作的时间复杂度也是O(log n)。但在最坏的情况下，时间复杂度会退化为O(n)。

空间复杂度：