C++ | 二叉搜索树

前言

本篇博客讲解c++中的继承

💓 个人主页：普通young man-CSDN博客

⏩ 文章专栏：C++_普通young man的博客-CSDN博客

⏩ 本人giee:   普通小青年 (pu-tong-young-man) - Gitee.com

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章
————————————————

目录

  二叉搜索树的概念

二叉搜索树的性能分析

最优情况

最差情况

平均情况

二分查找对比

平衡二叉搜索树

二叉搜索树的插入

二叉搜索树的查找

二叉搜索树的删除

二叉搜索树的实现代码

BSTNode 类

BSTree 类

内部细节

辅助函数

二叉搜索树key使用场景

场景1：小区无人值守车库

场景2：英文文章单词拼写检查

二叉搜索树key和key/value使用场景

场景1：简单的中英互译字典

场景2：商场无人值守车库

场景3：统计文章中单词出现的次数

key/value代码实现

BSTNode 类

BSTree 类

内部细节

二叉搜索树的概念

        二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，它满足特定的排序属性，这使得在树中的查找、插入和删除操作变得高效。以下是二叉搜索树的一些关键概念和性质：

  1. 定义：

    • 二叉搜索树是一种二叉树，每个节点最多有两个子节点，并且每个节点的值大于其左子树上的任何其他节点的值，小于其右子树上的任何其他节点的值。
    • 这意味着对于任意节点 n，所有左子树中的节点值 x 都满足 x ≤ n，所有右子树中的节点值 y 都满足 y ≥ n。

  2. 性质：

    • 左子树上所有结点的值均小于或等于根结点的值。
    • 右子树上所有结点的值均大于或等于根结点的值。
    • 根结点的左子树和右子树本身也必须是二叉搜索树。
    • 二叉搜索树中可以支持插入重复的键值，这取决于具体的应用场景。在一些实现中，如标准模板库(STL)中的 std::set 和 std::map 不允许重复键值；而 std::multiset 和 std::multimap 则允许重复键值。

  3. 操作：

    • 查找：给定一个键值，在二叉搜索树中查找该键值对应的节点。
    • 插入：将一个新的节点添加到树中，同时保持二叉搜索树的性质。
    • 删除：从树中移除一个节点，并调整树以维持其为二叉搜索树。
    • 中序遍历：按照左-根-右的顺序访问树中的节点，可以得到一个递增的有序序列。

代码结构：

// 节点结构定义
template<class T>
class BSTNode {
public:T _key; // 节点存储的键值BSTNode<T>* _left; // 左子节点指针BSTNode<T>* _right; // 右子节点指针// 构造函数BSTNode(const T& key) :_key(key), // 初始化键值_left(nullptr), // 初始化左子节点指针为nullptr_right(nullptr) // 初始化右子节点指针为nullptr{}
};

二叉搜索树的性能分析

二叉搜索树（BST）的性能主要依赖于树的高度。下面是对不同情况下的性能分析：

最优情况

  • 当二叉搜索树是一棵完全二叉树（或者接近完全二叉树）时，树的高度是最小的，此时高度大约为 log⁡2N，其中 N 是树中的节点数量。
  • 在这种情况下，二叉搜索树的所有基本操作（查找、插入、删除）的时间复杂度都是 O(log⁡2N)，这是非常高效的。

最差情况

  • 当二叉搜索树退化成一条链（单支树），即所有的节点只有一个子节点时，树的高度最大，此时高度为 N。
  • 在这种情况下，二叉搜索树的操作时间复杂度退化为 O(N)，这意味着查找、插入、删除可能需要遍历整个树。

平均情况

  • 如果二叉搜索树的构建是随机的，并且没有明显的偏向性，那么平均情况下树的高度大致为 log⁡2N，因此平均时间复杂度为 O(log⁡2N)。

二分查找对比

  • 二分查找可以在 O(log⁡2N) 时间内完成查找，但前提是数据必须存储在一个支持随机访问的数据结构（如数组）中，并且数据必须是有序的。
  • 二分查找的缺点在于，对于插入和删除操作，由于数据存储在数组中，可能需要移动大量的元素来保持有序性，导致效率较低，通常是 O(N)。

平衡二叉搜索树

  • 为了解决二叉搜索树在最坏情况下的性能问题，引入了自平衡二叉搜索树的概念，如AVL树和红黑树。(这个后面我也会学习)
  • 这些树通过旋转等方法自动保持树的平衡，确保任何操作都不会使树的高度超过 O(log⁡2N)，从而提供了更稳定的性能。

二叉搜索树的插入

  1. 树为空的情况：

    • 如果二叉搜索树为空，那么直接创建一个新的节点，并将这个新节点作为树的根节点（root指针指向这个新节点）。

  2. 树不为空的情况：

    • 如果二叉搜索树不为空，则根据二叉搜索树的性质进行插入操作：
      • 比较待插入值与当前节点的值：
        • 如果待插入值小于当前节点的值，则向当前节点的左子树方向移动。
        • 如果待插入值大于当前节点的值，则向当前节点的右子树方向移动。
      • 继续沿着左子树或右子树向下寻找，直到找到一个空的位置（即当前节点的左子节点或右子节点为空）。
      • 在找到的空位置处插入新的节点。

  3. 处理相等值的情况：

    • 如果二叉搜索树支持插入相等的值，那么当待插入值等于当前节点的值时，可以选择向左子树方向移动或向右子树方向移动，找到空位置后插入新节点。
    • 注意保持逻辑的一致性，即如果选择向左插入相等的值，那么应该始终如此，或者始终选择向右插入，避免在不同的情况下选择不同的方向，这样可以避免混乱并保持树的一致性和可预测性。

代码展示：

bool insert(const T& key) {// 判断根节点是否为空if (_root == nullptr) {// 如果树为空，则创建一个新的节点作为根节点_root = new Node(key);return true; // 插入成功}// 使用两个指针，person 用来记录最近访问过的父节点，cur 用来记录当前正在访问的节点Node* person = nullptr;Node* cur = _root;// 循环遍历树直到找到空位置while (cur != nullptr) {if (key >= cur->_key) { // 如果待插入的键值大于等于当前节点的键值person = cur; // 更新父节点指针cur = cur->_right; // 向右子树移动}else if (key < cur->_key) { // 如果待插入的键值小于当前节点的键值person = cur; // 更新父节点指针cur = cur->_left; // 向左子树移动}else { // 如果键值已经存在，则返回失败return false;}}// 创建新的节点cur = new Node(key);// 将新节点链接到适当的位置if (key >= person->_key) { // 如果键值大于等于父节点的键值，则作为右子节点插入person->_right = cur;} else { // 否则作为左子节点插入person->_left = cur;}return true; // 插入成功
}

可以用这组数据测试：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
	key::BSTree<int> s1;//插入int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto it : a){s1.insert(it);}s1.InOrder();//

    s1.InOrder();->中序打印，是有序的，大家可以自己画画递归展开图，方便自己理解

 void _InOrder(BSTNode<T>* _root) {if (_root == nullptr) {return;}_InOrder(_root->_left); // 遍历左子树cout << _root->_key << " "; // 访问当前节点_InOrder(_root->_right); // 遍历右子树}


二叉搜索树的查找

查找操作的具体过程

  1. 从根开始比较：

    • 从根节点开始，比较查找值 x 与当前节点的值。
    • 如果 x 大于当前节点的值，则向当前节点的右子树方向移动。
    • 如果 x 小于当前节点的值，则向当前节点的左子树方向移动。

  2. 最多查找高度次：

    • 查找操作最多需要进行树的高度次比较。
    • 如果一直走到某个节点的左子节点或右子节点为空，还没有找到目标值 x，则说明该值不在树中。

  3. 不支持插入相等的值：

    • 如果二叉搜索树不支持插入相等的值，那么一旦找到目标值 x 即可立即返回成功。

  4. 支持插入相等的值：

    • 如果二叉搜索树支持插入相等的值，这意味着可能存在多个值为 x 的节点。
    • 在这种情况下，一般要求查找中序遍历的第一个值为 x 的节点。
    • 例如，在查找值 3 时，如果有多于一个 3，则应返回第一个在中序遍历中出现的 3。

代码展示：

// 查找操作
bool find(const T& key) {Node* cur = _root; // 从根节点开始查找// 循环直到找到节点或到达空节点while (cur != nullptr) {if (key > cur->_key) { // 如果查找的键值大于当前节点的键值cur = cur->_right; // 向右子树移动} else if (key < cur->_key) { // 如果查找的键值小于当前节点的键值cur = cur->_left; // 向左子树移动} else { // 如果找到目标键值return true; // 找到目标键值，返回 true}}// 没有找到目标键值return false;
}

 测试代码：

	//查找if (s1.find(7)){cout << "OK"<<endl;}else{cout << "NO" << endl;}

二叉搜索树的删除

        删除二叉搜索树中的节点是一个稍微复杂的过程，因为它需要保持树的性质——对于任何节点，其所有左子树的节点的键值小于该节点的键值，所有右子树的节点的键值大于该节点的键值。下面是针对不同情况的解决方案：

情况总结表：

情况描述解决方案
1N的左右孩子均为空直接将N的父亲节点对应的子节点指针设为空，然后删除N节点。（也可以当作情况2或3处理）
2N的左孩子为空，右孩子不为空将N的父亲节点对应的子节点指针指向N的右孩子，然后删除N节点。
3N的右孩子为空，左孩子不为空将N的父亲节点对应的子节点指针指向N的左孩子，然后删除N节点。
4N的左右孩子均不为空使用N的左子树中的最大值节点R（最右节点）或N的右子树中的最小值节点R（最左节点）来替代N节点。替换后，转而删除R节点，此时R节点符合情况2或3。

文字描述：

  1. N的左右孩子均为空：

    • 这是最简单的情况，只需要将N的父亲节点的相应孩子指针设为空，然后删除N即可。这种情况下，N没有子节点，因此不会影响树的结构。

  1. N的左孩子为空，右孩子不为空：

    • 这种情况下，可以用N的右孩子来代替N的位置。具体操作是将N的父亲节点的相应孩子指针指向N的右孩子，然后删除N节点。

  2. N的右孩子为空，左孩子不为空：

    • 类似于情况2，只是这次使用N的左孩子来代替N的位置。具体操作是将N的父亲节点的相应孩子指针指向N的左孩子，然后删除N节点。

  1. N的左右孩子均不为空：

    • 这种情况比较复杂，不能直接删除N。可以找到N的左子树中的最大值节点R（即最右侧的节点）或N的右子树中的最小值节点R（即最左侧的节点），并将R的值与N交换。之后，问题转化为删除R节点，这时R节点只可能有一个孩子或者没有孩子，属于情况2或3。

这边一定是去找右子树的最左边的值，才是最合适的值

这里就可以发现为什么replacePerson为什么不给nullptr，而是要给cur，当我们要删除root就会野指针

代码实现：

bool erase(const T& key) {Node* person = nullptr; // person用于记录cur的父节点，以便在删除节点时调整父节点的指向Node* cur = _root; // 从根节点开始搜索目标键值对应的节点// 循环查找要删除的节点while (cur) {if (key > cur->_key) { // 如果目标键值大于当前节点键值，则向右子树搜索person = cur; // 更新person为当前节点，因为下一步将进入右子树cur = cur->_right; // 向右子树继续查找}else if (key < cur->_key) { // 如果目标键值小于当前节点键值，则向左子树搜索person = cur; // 更新person为当前节点，因为下一步将进入左子树cur = cur->_left; // 向左子树继续查找}else { // 找到了要删除的节点// 情况1: 要删除的是叶子节点或只有一个孩子的节点if (cur->_left == nullptr) { // 没有左孩子// 判断是否是根节点if (cur == _root) {_root = cur->_right; // 将根节点设置为其右孩子}else { // 不是根节点if (person->_left == cur) { // 要删除的节点是其父节点的左孩子person->_left = cur->_right; // 将其父节点的左孩子设置为要删除节点的右孩子}else { // 要删除的节点是其父节点的右孩子person->_right = cur->_right; // 将其父节点的右孩子设置为要删除节点的右孩子}}delete cur; // 删除该节点}else if (cur->_right == nullptr) { // 没有右孩子// 判断是否是根节点if (cur == _root) {_root = cur->_left; // 将根节点设置为其左孩子}else { // 不是根节点if (person->_left == cur) { // 要删除的节点是其父节点的左孩子person->_left = cur->_left; // 将其父节点的左孩子设置为要删除节点的左孩子}else { // 要删除的节点是其父节点的右孩子person->_right = cur->_left; // 将其父节点的右孩子设置为要删除节点的左孩子}}delete cur; // 删除该节点}// 情况2: 要删除的节点有两个孩子（左右孩子都有）else {Node* replacePerson = cur; // replacePerson记录待替换节点的父节点Node* replace = cur->_right; // replace记录待替换的节点，初始化为当前节点的右孩子// 寻找右子树中的最小节点while (replace->_left) {replacePerson = replace; // 更新replacePerson为当前节点replace = replace->_left; // 向左子树继续查找最小值}// 将找到的最小节点的键值复制到当前节点cur->_key = replace->_key;// 删除替换用的节点if (replacePerson->_left == replace) { // 如果待删除节点是其父节点的左孩子replacePerson->_left = replace->_right; // 将其父节点的左孩子设置为待删除节点的右孩子}else { // 如果待删除节点是其父节点的右孩子replacePerson->_right = replace->_right; // 将其父节点的右孩子设置为待删除节点的右孩子}delete replace; // 删除替换用的节点}return true; // 成功删除节点}}return false; // 未找到要删除的节点
}

二叉搜索树的实现代码

#include<iostream>
using namespace std;
//key搜索
namespace key {//节点结构template<class T>class BSTNode{public:T _key;BSTNode<T>* _left;BSTNode<T>* _right;//构造BSTNode(const T& key) ://初始化列表_key(key), _left(nullptr), _right(nullptr){}};//树的结构template<class T>class BSTree{//typedef BSTNode<T> Nodeusing Node = BSTNode<T>;public:/*插入*/bool insert(const T& key) {//判断根是否为空if (_root == nullptr) {_root = new Node(key);return true;}//双指针Node* person = nullptr;Node* cur = _root;//循环while (cur){if (key >= cur->_key) {person = cur;cur = cur->_right;}else if (key < cur->_key){person = cur;cur = cur->_left;}else{return false;}}//链接节点cur = new Node(key);if (key >= person->_key){person->_right = cur;}else{person->_left = cur;}return true;}/*查找*/bool find(const T& key) {Node* cur = _root;while (cur){if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else{return true;}}return false;}/*删除*/bool erase(const T& key) {//双指针Node* person = nullptr;Node* cur = _root;//循环while (cur){if (key > cur->_key) {person = cur;cur = cur->_right;}else if (key < cur->_key){person = cur;cur = cur->_left;}else{//叶子节点+只有一个节点的if (cur->_left == nullptr) {//判断是否是根节点if (cur == _root){_root = cur->_right;}else{if (person->_left == cur) {person->_left = cur->_right;}else{person->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){//判断是否是根节点if (cur == _root) {_root = cur->_left;}else{if (person->_left == cur) {person->_left = cur->_left;}else{person->_right = cur->_left;}}delete cur;}//两个节点else{Node* replacePerson = cur;//指向cur是防止删除根节点的时候越界Node* replace = cur->_right;//右子树的最小值(最合适，可以带左子树试一下，不构成BST)while (replace->_left){replacePerson = replace;replace = replace->_left;}//将这个值赋值给cur位置cur->_key = replace->_key;//删除节点if (replacePerson->_left == replace){replacePerson->_left = replace->_right;}else{replacePerson->_right = replace->_right;}delete replace;}return true;}}return false;}//类内部调用中序遍历void InOrder() {_InOrder(_root);cout << endl;}private://中序(递归)void _InOrder(Node* _root) {if (_root == nullptr){return;}_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}private:Node* _root = nullptr;
};
}

BSTNode 类

这是用于表示树中的节点的类。每个节点包含：

  • _key：键，用于排序。
  • _left 和 _right：指向左子节点和右子节点的指针。

构造函数用于初始化节点的键值和左右子节点指针，默认左右子节点均为 nullptr。

BSTree 类

这个类定义了二叉搜索树的行为：

  • 插入操作 (insert)：向树中添加一个新的键。如果键已经存在，则插入失败。
  • 查找操作 (find)：在树中查找具有指定键的节点。
  • 删除操作 (erase)：从树中移除具有指定键的节点。
  • 中序遍历 (InOrder)：按升序打印树中的所有键。

内部细节

  • 树的根节点 _root 是一个私有成员变量，初始值为 nullptr 表示空树。
  • 插入、查找和删除操作都使用了“双指针”技术来找到正确的插入或删除位置。
  • 插入操作处理了树为空的情况，直接将新节点作为根节点。
  • 删除操作处理了三种情况：叶子节点、有一个子节点、有两个子节点的情况。

辅助函数

  • _InOrder：递归地执行中序遍历。

二叉搜索树key使用场景

场景1：小区无人值守车库

在这个场景下，小区的物业管理公司将所有购买了车位的业主车牌号录入后台系统中。当车辆试图进入小区时，入口处的系统会自动扫描车牌号，并与后台系统中的车牌号进行比对。如果车牌号存在于二叉搜索树中，则意味着该车辆拥有进入小区的权利，此时系统会自动抬起栏杆让车辆通过；反之，如果车牌号不在二叉搜索树中，则系统会提示该车辆不属于本小区，并阻止其进入。

在这个应用中，车牌号作为唯一的标识符（key），同时也是用来判断车辆是否有权进入的关键信息。由于车牌号通常是唯一的，并且不会经常改变，因此这种情况下非常适合使用二叉搜索树来高效地存储和查询这些车牌号。

场景2：英文文章单词拼写检查

这个场景涉及到检查一篇英文文章中的单词拼写是否正确。为了实现这一功能，首先需要构建一个包含所有正确拼写的单词的词库，并将这些单词按照字母顺序插入到二叉搜索树中。当文章被读取时，系统会对文章中的每个单词进行检查，通过二叉搜索树来确定该单词是否存在。如果一个单词没有出现在二叉搜索树中，这意味着它可能是拼写错误的单词，此时可以将其用波浪线标出或以其他方式高亮显示，以便用户进一步检查和修正。

在这种情况下，单词本身作为key，同时也是要验证的信息。二叉搜索树允许快速定位特定单词，从而使得拼写检查过程更加高效。

二叉搜索树key和key/value使用场景

场景1：简单的中英互译字典

在这个场景中，我们创建一个简单的中英互译字典，其中英文单词作为key，中文翻译作为value。当用户输入一个英文单词时，系统会在二叉搜索树中查找该key，如果找到，就会返回对应的中文翻译。这样就实现了基于key的快速查找功能。需要注意的是，虽然不允许直接修改key，但是value是可以更新的，例如可以在原有条目的基础上增加新的翻译或更正现有的翻译。

场景2：商场无人值守车库

在这个场景下，商场的无人值守车库系统会在车辆入场时记录其车牌号码（作为key）以及入场时间（作为value）。当车辆离开停车场时，出口处的系统会再次扫描车牌号码，并通过二叉搜索树查找对应的入场时间。然后，系统计算停车时长（当前时间减去入场时间），并据此计算停车费用。用户支付费用之后，栏杆升起，车辆可以离开。这种情况下，车牌号码作为唯一标识符，并且保持不变，而入场时间是可以根据实际情况更新的value。

场景3：统计文章中单词出现的次数

在这个场景中，我们需要统计一篇文章中各个单词的出现频率。首先，将文章中的每一个单词作为key，初始化时对应的value设置为出现次数（默认为0）。每当读取到一个新的单词时，系统会在二叉搜索树中查找该单词。如果单词尚未出现过（即value为0或者不存在），则将其加入树中，并将其value设置为1（表示首次出现）。如果单词已经存在，则将对应的value（出现次数）增加1。这样，随着文章的逐字读取，二叉搜索树中就会记录下每个单词的出现次数。

key/value代码实现

namespace key_value {// 节点结构定义template<class T, class V>class BSTNode{public:T _key;       // 存储键V _value;     // 存储值BSTNode<T, V>* _left;   // 左子节点指针BSTNode<T, V>* _right;  // 右子节点指针// 构造函数BSTNode(const T& key, const V& value) :_key(key),_value(value),_left(nullptr),_right(nullptr){}};// 树的结构定义template<class T, class V>class BSTree{// 使用别名简化BSTNode类型的书写using Node = BSTNode<T, V>;public:// 默认构造函数BSTree() = default;// 拷贝构造函数BSTree(const BSTree& tmp) {// 深拷贝整棵树_root = _Copy(tmp._root);}// 析构函数~BSTree() {// 释放所有节点占用的内存Destroy(_root);_root = nullptr;}// 拷贝赋值运算符BSTree& operator=(BSTree tmp) {// 使用交换技巧完成浅拷贝到深拷贝的转换swap(_root, tmp._root);return *this;}/* 插入 */// 向树中插入键值对bool insert(const T& key, const V& value) {// 如果树为空，创建新节点作为根节点if (_root == nullptr) {_root = new Node(key, value);return true;}// 使用双指针找到合适的位置插入新节点Node* person = nullptr;Node* cur = _root;while (cur) {if (key >= cur->_key) {person = cur;cur = cur->_right;}else if (key < cur->_key) {person = cur;cur = cur->_left;}else {// 如果键已存在，插入失败return false;}}// 创建新节点，并根据比较结果将其插入到合适的位置cur = new Node(key, value);if (key >= person->_key) {person->_right = cur;}else {person->_left = cur;}return true;}/* 查找 */// 在树中查找指定键对应的节点Node* find(const T& key) {Node* cur = _root;while (cur) {if (key > cur->_key) {cur = cur->_right;}else if (key < cur->_key) {cur = cur->_left;}else {return cur;}}return nullptr;}/* 删除 */// 从树中删除指定键及其对应的节点bool erase(const T& key) {// 使用双指针找到要删除的节点Node* person = nullptr;Node* cur = _root;while (cur) {if (key > cur->_key) {person = cur;cur = cur->_right;}else if (key < cur->_key) {person = cur;cur = cur->_left;}else {// 处理三种情况：叶节点、只有一个子节点、有两个子节点if (cur->_left == nullptr) {if (cur == _root) {_root = cur->_right;}else {if (person->_left == cur) {person->_left = cur->_right;}else {person->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr) {if (cur == _root) {_root = cur->_left;}else {if (person->_left == cur) {person->_left = cur->_left;}else {person->_right = cur->_left;}}delete cur;}else {Node* replacePerson = cur;Node* replace = cur->_right;while (replace->_left) {replacePerson = replace;replace = replace->_left;}cur->_key = replace->_key;if (replacePerson->_left == replace) {replacePerson->_left = replace->_right;}else {replacePerson->_right = replace->_right;}delete replace;}return true;}}return false;}// 类内部调用中序遍历void InOrder() {_InOrder(_root);std::cout << std::endl;}private:// 中序遍历（递归）void _InOrder(Node* _root) {if (_root == nullptr) {return;}_InOrder(_root->_left);std::cout << _root->_key << "-" << _root->_value << " ";_InOrder(_root->_right);}// 释放所有节点占用的内存（后序遍历）void Destroy(Node* _root) {if (_root == nullptr) {return;}Destroy(_root->_left);Destroy(_root->_right);delete _root;}// 深拷贝树（递归）Node* _Copy(Node* _root) {if (_root == nullptr) {return nullptr;}Node* new_node = new Node(_root->_key, _root->_value);new_node->_left = _Copy(_root->_left);new_node->_right = _Copy(_root->_right);return new_node;}private:Node* _root = nullptr; // 根节点指针};
}

下面是对给定代码的一个简明解析：

这段代码定义了一个二叉搜索树(Binary Search Tree, BST)，它是一个数据结构，用于存储键值对。该实现使用了 C++ 的模板类来支持不同类型的键和值。

BSTNode 类

这是用于表示树中的节点的类。每个节点包含：

  • _key：键，用于排序。
  • _value：与键关联的值。
  • _left 和 _right：指向左子节点和右子节点的指针。

BSTree 类

这个类定义了二叉搜索树的行为：

  • 构造函数：默认构造函数和拷贝构造函数。
  • 析构函数：清理树中的所有节点。
  • 拷贝赋值运算符：使用交换技巧来实现深拷贝。
  • 插入操作 (insert)：向树中添加一个新的键值对。如果键已经存在，则插入失败。
  • 查找操作 (find)：在树中查找具有指定键的节点。
  • 删除操作 (erase)：从树中移除具有指定键的节点。
  • 中序遍历 (InOrder)：按升序打印树中的所有键值对。
  • 辅助函数：
    • _InOrder：递归地执行中序遍历。
    • Destroy：释放树中的所有节点。
    • _Copy：递归地复制一棵树。

内部细节

  • 树的根节点 _root 是一个私有成员变量，初始值为 nullptr 表示空树。
  • 插入和删除操作处理了二叉搜索树中常见的几种情况：没有子节点、有一个子节点以及有两个子节点的情况。
  • 拷贝构造函数和拷贝赋值运算符确保了对象的正确复制。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1540247.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

超详细！百分百安装成功pytorch，建议收藏

超详细！百分百安装成功pytorch，建议收藏

文章目录 一、Anaconda安装1.1下载anaconda1.2配置Anaconda环境1.3验证anaconda是否安装成功 二、查看电脑显卡三、更新显卡驱动3.1下载驱动3.2、查看显卡驱动版本 四、cuda安装4.1CUDA下载4.2CUDA环境配置4.3验证CUDA是否安装成功 五、安装pytorch4.1下载pytorch5.2验证pytorc…
阅读更多...
OpenHarmony（鸿蒙南向开发）——小型系统内核（LiteOS-A）【内核通信机制】上

OpenHarmony（鸿蒙南向开发）——小型系统内核（LiteOS-A）【内核通信机制】上

往期知识点记录&#xff1a; 鸿蒙&#xff08;HarmonyOS&#xff09;应用层开发&#xff08;北向&#xff09;知识点汇总 鸿蒙&#xff08;OpenHarmony&#xff09;南向开发保姆级知识点汇总~ 子系统开发内核 轻量系统内核&#xff08;LiteOS-M&#xff09; 轻量系统内核&#…
阅读更多...
力扣 18.四数之和

力扣 18.四数之和

文章目录 题目介绍解法 题目介绍 解法 思路和 15. 三数之和 一样&#xff0c;排序后&#xff0c;枚举 nums[a] 作为第一个数&#xff0c;枚举 nums[b] 作为第二个数&#xff0c;那么问题变成找到另外两个数&#xff0c;使得这四个数的和等于 target&#xff0c;这可以用双指针…
阅读更多...
《线性代数》常用公式定理总结

《线性代数》常用公式定理总结

文章目录 1 行列式1.1 克拉默法则1.2 基本性质1.3 余子式 M i j M_{ij} Mij​1.4 代数余子式 A i j ( − 1 ) i j ⋅ M i j A_{ij} (-1)^{ij} \cdot M_{ij} Aij​(−1)ij⋅Mij​1.5 具体型行列式计算&#xff08;化为基本型&#xff09;1.5.1 主对角线行列式&#xff1a;主…
阅读更多...
git 本地分支误删，怎么恢复？误删本地已提交未推送的分支！

git 本地分支误删，怎么恢复？误删本地已提交未推送的分支！

误删本地已提交未推送的分支&#xff01; 前提&#xff1a; 已提交&#xff01; 重点&#xff1a;未推送&#xff01; 要是推送了&#xff0c;再拉一下代码就行了。你也不会来搜这个帖子了。 如果你删除的分支里有你未提交的代码&#xff0c;不用往下看了&#xff0c;帮不到你…
阅读更多...
树莓派4B+UBUNTU20.04+静态ip+ssh配置

树莓派4B+UBUNTU20.04+静态ip+ssh配置

树莓派4B+UBUNTU20.04+静态ip+ssh配置 1.烧录Ubuntu镜像1.1选择pi 4b1.2选择ubuntu server (服务器版，无桌面)20.041.3选择sd卡1.4 点击右下角 NEXT ，编辑设置，输入密码，wifi选CN, 开启ssh1.5 烧录，依次点击“是”，等待完成2 烧录完成后装入树莓派，上电，等待系统完成配…
阅读更多...
电竞显示器哪个牌子好

电竞显示器哪个牌子好

电竞显示器哪个好&#xff1f;你想成为电竞选手吗&#xff1f;显示器很关键&#xff0c;下面我就列举7款市面流行的电竞显示器给大家看看&#xff0c;总有一款适合你。 1.电竞显示器哪个好 - 蚂蚁电竞 ANT255VF电竞显示器 一、产品概述 蚂蚁电竞 ANT255VF电竞显示器是一款专为…
阅读更多...
鱼哥好书分享活动第31期：如何构建出更好的大模型RAG系统？《大模型RAG实战》

鱼哥好书分享活动第31期：如何构建出更好的大模型RAG系统？《大模型RAG实战》

鱼哥好书分享活动第31期&#xff1a;如何构建出更好的大模型RAG系统&#xff1f;《大模型RAG实战》 S1 初级RAGS2 高级RAG模型测策略测模型微调测 S3 超级RAG购买链接&#xff1a;内容简介&#xff1a;赠书抽奖规则: ChatGPT爆火之后&#xff0c;以ChatPDF为首的产品组合掀起了…
阅读更多...
Node-red 某一时间范围内满足条件的数据只返回一次

Node-red 某一时间范围内满足条件的数据只返回一次

厂子里有个业务需求增加一段逻辑&#xff0c;根据点位数值&#xff0c;判断是否让mes执行之后的逻辑。 网关采集周期5s/次&#xff0c;及数据上报周期5s/次; iot通过网关写入时间为8s左右&#xff1b; 同类设备共用一条规则链&#xff1b; 想当触发条件时修改”完成上传“不…
阅读更多...
简单题67.二进制求和 （java）20240919

简单题67.二进制求和 （java）20240919

题目描述&#xff1a; Java&#xff1a; class Solution {public String addBinary(String a, String b) {StringBuilder result new StringBuilder();int i a.length()-1;int j b.length()-1;int carry 0; //记录进位信息while(i>0 || j>0 || carry!0){int sum ca…
阅读更多...
[Linux#55][网络协议] 序列化与反序列化 | TcpCalculate为例

[Linux#55][网络协议] 序列化与反序列化 | TcpCalculate为例

目录 1. 理解协议 1.1 结构化数据的传输 序列化与反序列化 代码感知&#xff1a; Request 类 1. 构造函数 2. 序列化函数&#xff1a;Serialize() 3. 反序列化函数&#xff1a;DeSerialize() 补充 4. 成员变量 Response 类 1. 构造函数 2. 序列化函数&#xff1a;…
阅读更多...
免费下载PDF | 自然语言处理新范式：基于预训练模型的方法

免费下载PDF | 自然语言处理新范式：基于预训练模型的方法

前言 本次给大家推荐阅读的书籍是——《自然语言处理&#xff1a;基于预训练模型的方法》。近些年来&#xff0c;以GPT、BERT为代表的预训练模型在自然语言处理领域掀起了一股浪潮&#xff0c;打开了“预训练精调”的自然语言处理新范式的大门。 由电子工业出版社出版的《自然…
阅读更多...
动手学深度学习（pytorch土堆）-06损失函数与反向传播、模型训练、GPU训练

动手学深度学习（pytorch土堆）-06损失函数与反向传播、模型训练、GPU训练

模型保存与读取 完整模型训练套路 import torch import torchvision.datasets from torch import nn from torch.nn import Conv2d, MaxPool2d, Flatten, Linear from torch.utils.data import DataLoader from torch.utils.tensorboard import SummaryWriterfrom model impo…
阅读更多...
AV1 Bitstream Decoding Process Specification--[7]： 语法结构语义-3

AV1 Bitstream Decoding Process Specification--[7]： 语法结构语义-3

原文地址&#xff1a;https://aomediacodec.github.io/av1-spec/av1-spec.pdf 没有梯子的下载地址&#xff1a;AV1 Bitstream & Decoding Process Specification摘要&#xff1a;这份文档定义了开放媒体联盟&#xff08;Alliance for Open Media&#xff09;AV1视频编解码…
阅读更多...
分发饼干00

分发饼干00

题目链接 分发饼干 题目描述 注意点 1 < g[i], s[j] < 2^31 - 1目标是满足尽可能多的孩子&#xff0c;并输出这个最大数值 解答思路 可以先将饼干和孩子的胃口都按升序进行排序&#xff0c;随后根据双指针 贪心&#xff0c;将当前满足孩子胃口的最小饼干分配给该孩…
阅读更多...
再次理解UDP协议

再次理解UDP协议

一、再谈端口号 在 TCP / IP 协议中&#xff0c;用 "源 IP", "源端口号", "目的 IP", "目的端口号", "协议号" 这样一个五元组来标识一个通信(可以通过 netstat -n 查看) 我们需要端口号到进程的唯一性&#xff0c;所以一个…
阅读更多...
Obsidian如何粘贴的图片类似于Typora，图片相对当前路径

Obsidian如何粘贴的图片类似于Typora，图片相对当前路径

添加插件 下载插件&#xff1a; Custom Attachment Location 基础设置 同时需要在下面进行设置 示意效果
阅读更多...
大数据多集群数据作业和集群状态监控

大数据多集群数据作业和集群状态监控

目前手里面有四套大数据集群的作业需要维护&#xff0c;分别属于不同的客户&#xff0c;我同岗位的兄弟离职后&#xff0c;所有的数据作业都落到我头上了&#xff0c;公司也不招人了。开发新的数据作业倒没有什么问题&#xff0c;就是客户叫我补数的时候&#xff0c;头比较大&a…
阅读更多...
Linux基础权限

Linux基础权限

Linux基础权限 shell的概念Linux基础权限Linux的两种用户Linux的权限管理权限认知权限设置权限掩码粘滞位 shell的概念 &#xff08;shell&#xff09;命令行解释器 的存在意义&#xff1a; 将用户的命令翻译给操作系统&#xff0c;然后返回OS的结果给用户&#xff1b;保护OS…
阅读更多...
YOLOv5图像识别教程包成功-以识别桥墩缺陷详细步骤分享

YOLOv5图像识别教程包成功-以识别桥墩缺陷详细步骤分享

前置环境资源下载 提示&#xff1a;要开外网才能下载的环境我都放在了网盘里&#xff0c;教程中用到的环境可从这里一并下载&#xff1a; https://pan.quark.cn/s/f0c36aa1ef60 1. 下载YOLOv5源码 官方地址&#xff1a;GitHub - ultralytics/yolov5: YOLOv5 &#x1f680; …
阅读更多...
最新文章

Copyright @ 2022~2023