【C++】二叉搜索树BST

news/2025/2/22 0:24:06/

目录

  • 1.二叉搜索树的性质
  • 2.二叉搜索树功能的实现
    • 1.二叉搜索树的框架
    • 2.插入
    • 3.查找
    • 4.删除（难点）
      • 解析
  • 3.二叉搜索树功能的递归实现
    • 1.查找递归实现
    • 2.插入递归实现
      • 递归形式中新建节点的链接问题
    • 3.删除的递归实现
  • 4.二叉搜索树部分默认成员函数实现
    • 1.构造函数
    • 2.拷贝构造函数
    • 3.析构函数
    • 4.赋值运算符重载
  • 5.二叉搜索树实现集合
  • 5.二叉搜索树增删查改的时间复杂度
  • 6.二叉搜索树的应用
    • K模型(key)
    • KV模型(key-value)

1.二叉搜索树的性质

二叉搜索树又称二叉排序树，具有以下性质:

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

搜索二叉树不允许数据冗余，也就是说其中没有重复的数据。

2.二叉搜索树功能的实现

1.二叉搜索树的框架

template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://功能：插入...private:Node* _root = nullptr;
}

2.插入

插入的过程：

  1. 树为空，则直接新增节点，赋值给root指针（所以插入的第一个值就是根）
  2. 树不空，按二叉搜索树性质查找插入位置，插入新节点

注意：二叉搜索树不允许数据冗余，插入相同的数据返回false，用返回值用bool即可。

//插入
bool insert(const K& key)
{//空树情况if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;//记录父节点，插入后用以链接插入的数据//找到应该插入的叶子结点位置,//cur为空时就是该位置的下一个位置（应该插入的位置）while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}//开辟空间初始化要插入的对象cur = new Node(key);//链接插入的子节点if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

3.查找

//查找
bool Find(const K& 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;}
}

4.删除（难点）

删除分为三种情况：

  1. 删除节点为叶子结点
    在这里插入图片描述
  1. 删除节点的左子树为空或右子树为空
    在这里插入图片描述
  1. 删除节点的左右子树都不为空
    在这里插入图片描述

因为左子树的最大节点与右子树的最小节点都可以满足二叉搜索树的性质：

  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值

代码实现：

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){//查找要删除的节点if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else//key == cur->_key找到了 ==> 删除{//0.要删除的节点左右子树都为空if (cur->_left == nullptr && cur->_right == nullptr){parent->_left = nullptr;parent->_right = nullptr;delete cur;}//1.要删除的节点只有右子树，没有左子树else if (cur->_left == nullptr){//如果要删除的是根，没有父节点，直接更新_root即可if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left == cur->_right;}else//parent->_right == cur{parent->_right == cur->_right;}}delete cur;}//2.要删除的节点只有左子树，没有右子树else if (cur->_right == nullptr){//如果要删除的是根，没有父节点，直接更新_root即可if (cur == _root){_root = cur->_lift;}else{if (parent->_left == cur){parent->_left == cur->_left;}else//parent->_right == cur{parent->_right == cur->_left;}}delete cur;}//3.要删除节点的左右子树都不为空else{//查找 a 或 b ：//a.右子树的最小节点-->右子树的最左节点//b.左子树的最大节点-->左子树的最右节点//查找右子树的最左节点Node* Pmin_Right = cur;Node* min_Right = cur->_right;while (min_Right->_left){Pmin_Right = min_Right;min_Right = min_Right->_left;}//将min_Right的值给cur，等于删除了cur，之后释放min_Right即可cur->_key = min_Right->_key;if (Pmin_Right->_left == min_Right){Pmin_Right->_left = min_Right->_right;}else{Pmin_Right->_right = min_Right->_right;}delete min_Right;}}}
}

解析

注意删除节点的时候，都需要记录一下删除节点的父节点，因为需要清除父节点的指针或者需要修改父节点的子树！

1.在树中查找要删除的节点：
在这里插入图片描述

2.删除要分三种情况：
a.要删除的节点为叶子结点，左右子树都为空：
直接删除即可。
在这里插入图片描述

b.要删除的节点只有一个子树：
删除后要托孤，将子树给删除节点的父节点。
注意：删除的节点如果是根节点，父节点为nullptr，要特殊处理，要不然会报错！！
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

c.要删除的节点有两个子树：
删除该节点后，无法托孤给父节点，因为一个节点只能链接两个子节点。
所以要特殊处理：
从该节点的左子树或者右子树中查找一个满足二叉搜索树规则的节点来替换该节点，不就等于删除了该节点吗？
——满足条件的节点：1.左子树的最大节点；2.右子树的最小节点；
那么为什么这两个节点满足条件呢？
——因为这两个节点满足二叉搜索树的规则：左子树的所有节点都小于该节点，右子树的所有节点都大于该节点。
那么这两个节点应该如何找到呢？
——左子树的最小节点：左子树的最靠右一个节点；右子树的最大节点：右子树的最靠左一个节点；

1.这里以右子树的最左节点为例：
（记录其父节点Pmin_Right）
在这里插入图片描述
2.找到对应的节点以后，对其与要删除的节点进行替换：
注意这里要分两种情况：
注意：min_Right已经是右子树的最左节点了，所以它不可能有左子树，也就是只可能存在min_Right->right。

情况一：
这种情况下，Pmin_Right->left == min_Right，可以直接将min_Right->right赋值给Pmin_Right->left。（因为是最左节点，所以只可能是赋值给父节点的左子树）
在这里插入图片描述

情况二：
这种情况下Pmin_Right->left != min_Right，Pmin_Right->right == min_Right，则要将min_Right->right赋值给Pmin_Right->right。（min_Right不可能有左子树，因为它是最左节点）在这里插入图片描述
实现：
在这里插入图片描述

3.二叉搜索树功能的递归实现

1.查找递归实现

//查找递归实现
bool FindR(const K& key)
{return _FindR(_root, key);
}bool _FindR(Node* root, const K& key)
{if(root == nullptr){return false;}if(root->_key == key){return true;}if(root->_key < key){return _FindR(root->_right, key);}else{return _FindR(root->_left, key);}
}

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 (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else//root->_key == key{return false;}
}

递归形式中新建节点的链接问题

解析：递归形式中链接的问题
在插入递归实现的时候，需要新建立节点然后再链接节点，在传root参数的时候，使用传引用传参，就可以做到自动链接新建的节点。
当我们在当前函数栈帧root = new Node(key)创建新的节点时，因为用了引用，其实这里的root就是上一个函数栈帧中的root->right，所以在创建节点完成，返回的时候就等同于完成了链接，其本质就等同于：root->_right = new Node(key);
在这里插入图片描述

3.删除的递归实现

//删除递归实现
bool EraseR(const K& key)
{return _EraseR(_root, key);
}bool _EraseR(Node*& root, const K& key)
{if(root == nullptr){return false;}if(root->_key < key){return _EraserR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else//key == _key{//找到了，开始删除Node* del = root;if(root->_left == nullptr){root = root->_right;}else if(root->_right == nullptr){root = root->_left;}else{//左右子树都在，找左子树的最大节点/右子树最小节点Node* maxleft = root->_left;while(maxfile->_right){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _EraseR(root->_left, key);}delete del;return true;}
}

解析：
递归删除与普通删除的实现原理相同：
1.要删除的节点为叶子结点，左右子树都为空；
2.要删除的节点只有一个子树；
3.要删除的节点有两个子树；
三种方式删除后都需要delete释放该节点，所以需要用一个del变量来记录要删除的root指针。（删除后root指针置空找不到了）

1.其中1和2两种方式可以用同一种方式解决：
两种情况可以通过下面一段代码完成：
在这里插入图片描述

要删除的节点为叶子结点：
因为root->_left == nullptr，则root = root->_right = nullptr，最后delete del后，即删除完成该节点。
在这里插入图片描述
要删除的节点只有一个子树：
root->_right == nullptr，root = root->_left，直接用其子节点覆盖该节点，最后释放del该节点即可。
在这里插入图片描述

2.要删除的节点有两个子树：
思路与非递归实现删除的思路相同，寻找左子树的最大节点或右子树的最小节点后进行替换然后删除即可。
进而引入递归的思路：
找到左子树的最大节点（右子树的最小节点）后，将其与要删除的节点进行swap交换key，将删除有两个子树节点的问题转化为删除没有子树节点的问题或只有一个子树节点的问题。
交换完成后再次递归进入左子树重新查找key，找到后直接删除即可（问题3转化为1、2情况来删除）。
在这里插入图片描述
在这里插入图片描述

4.二叉搜索树部分默认成员函数实现

1.构造函数

//强制生成默认构造，root声明时候给了缺省值nullptr
BSTree() = default;

解析：
C++11的新特性：default
在函数声明后加=default，将该函数声明为 default 函数，编译器将为显式声明的default函数自动生成函数体。

defaulted函数特性仅适用于类的特殊成员函数，且该特殊成员函数没有默认参数。
defaulted函数既可以在类体里（inline）定义，也可以在类体外定义。

2.拷贝构造函数

//拷贝构造
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;
}

3.析构函数

//析构（递归）
~BSTree()
{Destory(_root);
}void Destory(Node*& root)
{if (root == nullptr){return;}//左-右-根Destory(root->_left);Destory(root->_right);delete root;root = nullptr;
}

4.赋值运算符重载

//赋值运算符重载
BSTree<K>& operator=(BSTree<K> t)
{swap(_root, t._root);return *this;
}

5.二叉搜索树实现集合

namespace key
{template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public://强制生成默认构造，下面给了缺省值BSTree() = default;//拷贝构造BSTree(const BSTree<K>& t){_root = copy(t._root);}//赋值运算符重载BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}//析构（递归）~BSTree(){Destory(_root);}//插入bool insert(const K& key){//空树情况if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;//记录父节点，插入后用以链接插入的数据//找到应该插入的叶子结点位置,//cur为空时就是该位置的下一个位置（应该插入的位置）while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else//二叉搜索树不能有相同的节点{return false;}}//开辟空间初始化要插入的对象cur = new Node(key);//链接插入的子节点if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}//查找bool Find(const K& 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 K& key){Node* parent = nullptr;Node* cur = _root;while (cur){//查找要删除的节点if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else//key == cur->_key找到了 ==> 删除{//0.要删除的节点左右子树都为空if (cur->_left == nullptr && cur->_right == nullptr){parent->_left = nullptr;parent->_right = nullptr;delete cur;}//1.要删除的节点只有右子树，没有左子树else if (cur->_left == nullptr){//如果要删除的是根，没有父节点，直接更新_root即可if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left == cur->_right;}else//parent->_right == cur{parent->_right == cur->_right;}}delete cur;}//2.要删除的节点只有左子树，没有右子树else if (cur->_right == nullptr){//如果要删除的是根，没有父节点，直接更新_root即可if (cur == _root){_root = cur->_lift;}else{if (parent->_left == cur){parent->_left == cur->_left;}else//parent->_right == cur{parent->_right == cur->_left;}}delete cur;}//3.要删除节点的左右子树都不为空else{//查找 a 或 b ：//a.右子树的最小节点-->右子树的最左节点//b.左子树的最大节点-->左子树的最右节点//查找右子树的最左节点Node* Pmin_Right = cur;Node* min_Right = cur->_right;while (min_Right->_left){Pmin_Right = min_Right;min_Right = min_Right->_left;}//将min_Right的值给cur，等于删除了cur，之后释放min_Right即可cur->_key = min_Right->_key;if (Pmin_Right->_left == min_Right){Pmin_Right->_left = min_Right->_right;}else{Pmin_Right->_right = min_Right->_right;}delete min_Right;}}}}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//查找递归实现bool FindR(const K& key){return _FindR(_root, key);}//插入递归实现bool InsertR(const K& key){return _InsertR(_root, key);}//删除递归实现bool EraseR(const K& key){return _EraseR(_root, key);}protected://拷贝构造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;}//析构void Destory(Node*& root){if (root == nullptr){return;}//左-右-根Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}//中序遍历void _InOrder(Node* root)//1.缺省值必须是全局变量或者常量2.访问root需要this指针，this指针也是另一个参数，这里不一定能用{if (root == nullptr){return;}//左->根->右_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//查找递归实现bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (root->_key == key){return true;}if (root->_key < key){return _FindR(root->_right, key);}else{return _FindR(root->_left, key);}}//插入递归实现bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else//root->_key == key{return false;}}//删除递归实现bool _EraseR(Node*& root, const K key){if (root == nullptr){return false;}if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else//key == _key{//开始删除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(root->_key, maxleft->_key);return _EraseR(root->_left, key);}delete del;return true;}}private:Node* _root = nullptr;};
}

5.二叉搜索树增删查改的时间复杂度

时间复杂度为：
O(logN)~O(N)
最优情况下，接近或就是完全二叉树，时间复杂度为O(logN)。
最坏情况下二叉搜索树可能会出现单支树，此时为O(N)。
对二叉搜索树进行优化，控制左右子树的平衡就有了：AVL树和红黑树。
（AVL树与红黑树后续学习）

6.二叉搜索树的应用

K模型(key)

应用于搜索场景：在不在的问题。

结构体中只存在关键码key，关键码就是所需要查找的值。

比如：检查单词是否拼写正确，将词库中的每个单词都作为key构建二叉搜索树，进而检索单词查看是否拼写正确。

KV模型(key-value)

应用于搜索场景：通过一个值查找另一个值的问题。

**每个关键码key，都有与之对应的值value，结构中存在<key, value>的键值对。**通过key来查找value。

比如：中英互译的字典<english, chinese>，就是一对键值对；
或者可以统计单词出现的次数<word, count>，也是一对键值对；

（我们上面实现的是key模型的二叉搜索树）


http://www.ppmy.cn/news/49884.html

相关文章

【大数据之Hadoop】十七、MapReduce之数据清洗ETL

【大数据之Hadoop】十七、MapReduce之数据清洗ETL

ETL是将业务系统的数据经过抽取、清洗转换之后加载到数据仓库的过程&#xff0c;目的是将分散、零乱、标准不统一的数据整合到一起&#xff0c;为决策提供分析依据。 ETL的设计分三部分&#xff1a;数据抽取、数据的清洗转换、数据的加载。 1 ETL体系结构 ETL主要是用来实现…
阅读更多...
【wireshark】Ubuntu 安装 wireshark 以及 wireshark 过滤器的使用

【wireshark】Ubuntu 安装 wireshark 以及 wireshark 过滤器的使用

目录 1、安装wireshark 2、wireshark 过滤器比较符号 3、wireshark 过滤方式 (1) 根据 IP 地址过滤 (2) 根据端口号过滤 (3) 根据报文长度过滤 (4) HTTP协议过滤 参考文章链接&#xff1a;Wireshark 过滤器使用 1、安装wireshark 在命令行输入如下命令安装 wireshark …
阅读更多...
【安全与风险】互联网协议漏洞

【安全与风险】互联网协议漏洞

互联网协议漏洞 互联网基础设施TCP协议栈因特网协议&#xff08;IP&#xff09;IP路由IP协议功能(概述)问题:没有src IP认证用户数据报协议&#xff08;UDP&#xff09;传输控制协议 (TCP)TCP报头TCP(三向)握手基本安全问题数据包嗅听TCP连接欺骗随机初始TCP SNs 路由的漏洞Arp…
阅读更多...
【人工智能与深度学习】判别性循环稀疏自编码器和群体稀疏性

【人工智能与深度学习】判别性循环稀疏自编码器和群体稀疏性

【人工智能与深度学习】判别性循环稀疏自编码器和群体稀疏性 判别类循环稀疏自编码器 (DrSAE)组稀疏组稀疏自编码器的问与答图像级别训练，无权重分享(weight sharing)的局域过滤器 (local filters)判别类循环稀疏自编码器 (DrSAE) DrSAE的设计结合了稀疏编码（稀疏自编码器）…
阅读更多...
IJKPLAYER源码分析-主要队列

IJKPLAYER源码分析-主要队列

前言 对IJKPLAYER播放器内核几个关键的队列的理解&#xff0c;将有助于掌控全局。因此&#xff0c;这里简要介绍所涉及到的几个关键队列实现&#xff1a; PacketQueue&#xff1a;压缩数据队列&#xff0c;是一个带有首尾指针和回收单链表头指针的单链表结构&#xff0c;用来实…
阅读更多...
解决vue pointerevent事件无法更改cursor问题 抓取图标(grab/grabbing)

解决vue pointerevent事件无法更改cursor问题 抓取图标(grab/grabbing)

vue pointerevent事件无法更改cursor问题 告诉你一个扎心的事情,CtrlF5就好了… 另外开F12调试工具且在双屏的副屏上也会出现这个bug… 故障重现 我想要实现一个抓取拖放的功能,鼠标按下修改指针为gragbbing状态,抬起恢复到grab 于是我大概和你一样,尝试在pointdown事件里写…
阅读更多...
TypeScript（十二）模块

TypeScript（十二）模块

目录 引言 d.ts声明文件 declare关键字 全局声明 全局声明方式 全局声明一般用作 函数声明 在.ts中使用declare 外部模块&#xff08;文件模块&#xff09; 模块关键字module 声明模块 模块声明方式 模块通配符 模块导出 模块嵌套 模块的作用域 模块别名 内部…
阅读更多...
C++ STL之string容器的模拟实现

C++ STL之string容器的模拟实现

目录 一、经典的string类问题 1.出现的问题 2.浅拷贝 3.深拷贝 二、string类的模拟实现 1.传统版的string类 2.现代版的string类&#xff08;采用移动语义&#xff09; 3.相关习题* 习题一 习题二 4.写时拷贝 5.完整版string类的模拟实现[注意重定义] MyString.h…
阅读更多...
最新文章

Copyright @ 2022~2023