【二叉搜索树】K型与KV型二叉搜索树简单实现

2024-09-02 20:52
文章标签 简单 实现 搜索 二叉 kv

本文主要是介绍【二叉搜索树】K型与KV型二叉搜索树简单实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关于我：在这里插入图片描述


睡觉待开机：个人主页

个人专栏: 《优选算法》《C语言》《CPP》
生活的理想，就是为了理想的生活!
作者留言

PDF版免费提供：倘若有需要，想拿我写的博客进行学习和交流，可以私信我将免费提供PDF版。
留下你的建议：倘若你发现本文中的内容和配图有任何错误或改进建议，请直接评论或者私信。
倡导提问与交流：关于本文任何不明之处，请及时评论和私信，看到即回复。

参考目录

  • 1.定位
  • 2.认识
  • 3.分类
  • 4.二叉搜索树的常见操作
    • 4.1插入
    • 4.2中序遍历
    • 4.3查找
    • 4.4删除(重点)
  • 5.K型二叉搜索树的代码
  • 6.KV型二叉搜索树的代码及其应用示例

我们先从宏观上看一看二叉搜索树究竟是个什么东西？？？他究竟是个什么东西。
可能很多人已经了解到他就是一个用来查找的数据结构而已，我想我下面从整体查找上能够让大家更好的对其进行定位，做到心中有数。

1.定位

我们知道，查找是日常生活中应用广泛的一种操作，对应到我们程序中来，就是在一堆数据中查找某个值呗。
那么说到查找，常见的查找有：二分查找、二叉搜索树查找、哈希查找、跳表查找、多叉树查找…(如下图)
在这里插入图片描述
那，二叉搜索树是个什么东西？？？

2.认识

首先，二叉搜索树又称二叉排序树

它满足下面特点，如果不满足那就不是二叉搜索树

  • 空树
  • 是二叉树且左子树所有结点的值比根小、右子树所有结点的值比根大

如果满足上述特点中的一条，那么就属于二叉搜索树。
不过这里需要强调一点的是，一定要看清楚是不是左子树的所有结点的值都比根小，比如下图
在这里插入图片描述

在说完他的特点之后，我们来简单说一说他的优点和缺点。
至于优点嘛，比较适合用来查找东西，效率比较高，一般情况下能够达到O(logN)
缺点也是有的，特殊场景下，他的查找效率会退化为O(N)，这样的话就直接跟遍历查找差不多了。为了说明这个情况，请看下面图例：
在这里插入图片描述

那么这个二叉搜索树能够用来干什么呢？
答案肯定可以用来查找啊，其次他的中序遍历结果就是排序升序，还可以用来查询某个值是否存在于二叉搜索树中、用一个词来查找另一个词(比如常见的中英翻译词典)、再比如说统计一篇文章中各个词出现的次数。

3.分类

从分类上来说，二叉搜索树可以分为两种：
第一种是K型二叉搜索树、另一种是KV型二叉搜索树

K型二叉搜索树：只有一个key值，这个key值要求不能重复存入二叉搜索树中，一般用来快速查找某个值是否存在于二叉搜索树中。
KV型二叉搜索树：有两个值，分别是key值和val值，key值不允许重复，val值不允许重复，一般用来key值来找另外一个val值，当然还可以用来统计一篇文章中出现了各个词出现的次数，在本篇文章中就做出示例代码。

4.二叉搜索树的常见操作

一个数据结构常见的操作就是增删查改，下面我们依次来进行介绍。

4.1插入

在这里插入图片描述
具体实现如下，我们可以这样写代码：

//插入
bool Insert(const K& key)
{//1.空树if (_root == nullptr){_root = new Node(key);}//2.一般情况//2.a 寻找该插入的位置Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < key)//比较大往右走{parent = cur;cur = cur->_right;}else if (cur->_val > key)//比较小往左走{parent = cur;cur = cur->_left;}else//相等，返回false{return false;//一般情况下，K型二叉搜索树不允许数据冗余}}

在这里我需要强调几点：
首先，在树中没有值的时候要进行特殊处理。
其次，要注意结点之间的链接问题，要做好链接工作。
之后 ，我们需要强调在一般的二叉搜索树中，key值不允许重复。

为了能够方便的打印这棵树，我们再写一个中序遍历。因为二叉搜索树的中序遍历恰好就是有序嘛，可以方便验证我们写的程序是否正确。

4.2中序遍历

private:void _InOrder(Node* pcur){if (pcur == nullptr){return;}_InOrder(pcur->left);cout << pcur->_val << " ";_InOrder(pcur->right);}public:void InOrder()//嵌套子函数，可以拿到_root使用{_InOrder(_root);}

这个地方我需要说明一点至于为什么要嵌套一层函数去调用中序遍历的原因。
这是因为要拿到私有_root成员，这样写比较方便。
当然也还有其他方法，
比如说你可以把调用中序遍历的函数设置为该类的友元函数，当然这种方法比较挫，因为本身调用函数和该类关系不大，算是一种弱关联。
还有可以学习Java一样，提供一个GetRoot函数，当然，这样也可以不失为一种好方法，只不过CPP不太习惯这种写法罢了。
再之后，把root作为缺省参数是不行的，因为访问root需要用到this作为跳板，但是this指针和缺省都属于函数参数，语法上是不支持的。
之后，就是用我这种函数嵌套的方法去处理，这种方法在CPP中是很常见的，CPP比较习惯用这种方法进行处理。

我们继续再写一个查找接口。

4.3查找

怎么实现查找接口呢？
在这里插入图片描述

bool Find(const K& key)
{Node* pcur = _root;while (pcur){if (pcur->_val < key){pcur = pcur->right;}else if (pcur->_val > key){pcur = pcur->left;}else{return true;//此时找到了，返回true}}return false;//此时没有找到返回false
}

接下来是重头戏，删除接口。
删除接口的情况比较多，因此算是本节中重点了。

4.4删除(重点)

在这里插入图片描述
对于第一种情况，
● 找到删除的结点和其父节点
● 弄明白删除结点还有左孩子还是右孩子
● 弄明白要删除结点对于其父节点来说是左孩子还是右孩子

对于第二种情况，
● 先找到要删除的结点及其父结点
● 再找到要替换的结点(一般而言左子树的最大值或者右子树的最小值就符合条件)及其父结点
● 两者交换
● 做好链接工作并删除

但是其中有个特殊情况，就是删除的结点恰好是根，所以需要对应进行特殊处理：
对于第一种情况，
ⅰ. 把根指向下一个结点
ⅱ. 修正parent，此时parent为空，不修正会对parent进行解引用操作
在这里插入图片描述

对于第二种情况，
ⅰ. 修正parent=cur
ⅱ. 要再次判断rightMin是其父亲的左孩子还是右孩子
在这里插入图片描述
所以实现是下面这样的：

//Erase
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < key)//比较大往右走{parent = cur;cur = cur->_right;}else if (cur->_val > key)//比较小往左走{parent = cur;cur = cur->_left;}else//相等，找到了就开始准备删除{//1.只有一个孩子/没有孩子的情况//左为空，父亲指向我的右if (cur->_left == nullptr){if (cur == _root)//删除的是根的情况{_root = cur->_right;}else//删除的不是根{//具体父亲的左孩子指向我的右还是右孩子指向我的右呢？if (parent->_left == cur)//如果我是父亲的左孩子，那么父亲的左孩子就去继承我的右{parent->_left = cur->_right;}else//如果我是父亲的右孩子，那么父亲的右孩子就去继承我的右{parent->_right = cur->_right;}}delete cur;}else if(cur->_right == nullptr)//右为空，父亲指向我的左{//具体父亲的左孩子指向我的左还是右孩子指向我的左呢？if (cur == _root)//删除的是根的情况{_root = cur->_left;}else//删除的不是根{if (parent->_left == cur)//如果我是父亲的左孩子，那么父亲的左孩子就去继承我的左{parent->_left = cur->_left;}else//如果我是父亲的右孩子，那么父亲的右孩子就去继承我的左{parent->_right = cur->_left;}}delete cur;}else//2.我有两个孩子的情况{//此时替换法删除Node* rightMin = cur->_right;Node* rightMinParent = cur;//坑，如果下面while循环没进去，写空的话就会被解引用了while (rightMin->_left)//找合适的替换值{rightMinParent = rightMin;rightMin = rightMin->_left;}//交换swap(cur->_val, rightMin->_val);//删除前做好链接工作if (rightMinParent->_left == rightMin){rightMinParent->_left = rightMin->_right;}else{rightMinParent->_right = rightMin->_right;}//删除结点delete rightMin;}//end of two childrenreturn true;}//end of cur->_val == key}return false;
}

5.K型二叉搜索树的代码

//K型二叉搜索树
namespace Key
{//结点template<class K>struct BinarySearchNode{struct BinarySearchNode* _left;struct BinarySearchNode* _right;K _val;BinarySearchNode(const K& key):_left(nullptr),_right(nullptr),_val(key){}};//二叉搜索树template<class K>class BSTree{typedef struct BinarySearchNode<K> Node;private:Node* _root = nullptr;public://插入bool Insert(const K& key){//1.空树if (_root == nullptr){_root = new Node(key);}//2.一般情况//2.a 寻找该插入的位置Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < key)//比较大往右走{parent = cur;cur = cur->_right;}else if (cur->_val > key)//比较小往左走{parent = cur;cur = cur->_left;}else//相等，返回false{return false;//一般情况下，K型二叉搜索树不允许数据冗余}}//既不是空树，也不是相同的数字//2.b链接Node* newnode = new Node(key);if (parent->_val > key){parent->_left = newnode;}else{parent->_right = newnode;}cur = parent = newnode = nullptr;return true;}// end of Insert//中序遍历对外调用接口void InOrder(){_InOrder(_root);}//end of InOrder//查找bool Find(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < key)//比较大往右走{parent = cur;cur = cur->_right;}else if (cur->_val > key)//比较小往左走{parent = cur;cur = cur->_left;}else//相等，找到了返回true{return true;}}return false;}//Modify//注：二叉搜索树不允许去修改，后面KV型可以修改V值//Erasebool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < key)//比较大往右走{parent = cur;cur = cur->_right;}else if (cur->_val > key)//比较小往左走{parent = cur;cur = cur->_left;}else//相等，找到了就开始准备删除{//1.只有一个孩子/没有孩子的情况//左为空，父亲指向我的右if (cur->_left == nullptr){if (cur == _root)//删除的是根的情况{_root = cur->_right;}else//删除的不是根{//具体父亲的左孩子指向我的右还是右孩子指向我的右呢？if (parent->_left == cur)//如果我是父亲的左孩子，那么父亲的左孩子就去继承我的右{parent->_left = cur->_right;}else//如果我是父亲的右孩子，那么父亲的右孩子就去继承我的右{parent->_right = cur->_right;}}delete cur;}else if(cur->_right == nullptr)//右为空，父亲指向我的左{//具体父亲的左孩子指向我的左还是右孩子指向我的左呢？if (cur == _root)//删除的是根的情况{_root = cur->_left;}else//删除的不是根{if (parent->_left == cur)//如果我是父亲的左孩子，那么父亲的左孩子就去继承我的左{parent->_left = cur->_left;}else//如果我是父亲的右孩子，那么父亲的右孩子就去继承我的左{parent->_right = cur->_left;}}delete cur;}else//2.我有两个孩子的情况{//此时替换法删除Node* rightMin = cur->_right;Node* rightMinParent = cur;//坑，如果下面while循环没进去，写空的话就会被解引用了while (rightMin->_left)//找合适的替换值{rightMinParent = rightMin;rightMin = rightMin->_left;}//交换swap(cur->_val, rightMin->_val);//删除前做好链接工作if (rightMinParent->_left == rightMin){rightMinParent->_left = rightMin->_right;}else{rightMinParent->_right = rightMin->_right;}//删除结点delete rightMin;}//end of two childrenreturn true;}//end of cur->_val == key}return false;}private://中序遍历的主要逻辑，这里为了封闭性考虑，不把中序遍历的核心接口暴露出去//中序遍历void _InOrder(const Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << (*root)._val << " ";_InOrder(root->_right);}//end of _InOrder}; //end of class BSTree//BSTree专用的测试接口void BSTreeTest(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> tree;for (const auto& e : a){tree.Insert(e);}tree.InOrder();cout << endl << endl;cout << tree.Find(1) << endl;cout << tree.Find(100) << endl;for (const auto& e : a){tree.Erase(e);tree.InOrder();cout << endl;}}//end of BSTreeTest
}//end of namespace Key

6.KV型二叉搜索树的代码及其应用示例

namespace KV
{//结点template<class K, class V>struct BinarySearchTreeNode{struct BinarySearchTreeNode<K, V>* _left;struct BinarySearchTreeNode<K, V>* _right;K _key;V _val;BinarySearchTreeNode(const K& key, const V& val):_left(nullptr), _right(nullptr), _key(key), _val(val){}};//树template <class K, class V>class BinarySearchTree{typedef struct BinarySearchTreeNode<K, V> Node;private:Node* _root = nullptr;public:bool Insert(const K& key, const V& val){//空树情况if (_root == nullptr){Node* newnode = new Node(key, val);_root = newnode;newnode = nullptr;return true;}//一般情况//找出要插入位置的父结点Node* parent = nullptr, *cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else//相等情况返回false{cout << key << "：该种情况被终止" << endl;return false;}}//链接Node* newnode = new Node(key, val);if (parent->_key > key){parent->_left = newnode;}else{parent->_right = newnode;}newnode = cur = parent = nullptr;return true;}//end of Insertvoid InOrder(){_InOrder(_root);}private:void _InOrder(const Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " " << root->_val << " ";_InOrder(root->_right);}//end of _InOrderpublic:bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}//end of Findbool Erase(const K& key){Node* cur = _root, * parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//找到了相同的值，准备删除if (cur->_left == nullptr)//要删除的左子树为空，那么父亲结点接过他的右子树就行{if (parent == nullptr){parent = cur;_root = cur->_right;}if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}else if (cur->_right == nullptr)//要删除的右子树为空，那么父亲结点接过他的左子树就行{if (parent == nullptr){parent = cur;_root = cur->_left;}if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}else{//这种情况下需要替换法删除Node* leftMax = cur->_left;Node* leftMaxParent = cur;while (leftMax->_right){leftMaxParent = leftMax;leftMax = leftMax->_right;}//交换swap(leftMax->_key, cur->_key);swap(leftMax->_val, cur->_val);//链接并删除if (leftMaxParent->_left == leftMax){leftMaxParent->_left = leftMax->_left;}else{leftMaxParent->_right = leftMax->_left;}delete leftMax;}return true;}}//end of whilereturn false;}//end of Erase};//end of class BinarySearchTreevoid Test(){BinarySearchTree<int, string> tree;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };string str[] = { "8", "3", "1", "10", "6", "4", "7", "14", "13" };for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++){tree.Insert(a[i], str[i]);tree.InOrder();cout << endl;}cout << tree.Find(1) << endl;cout << tree.Find(100) << endl;cout << tree.Find(109) << endl;cout << "-------------------------------" << endl;for (auto e : a){tree.Erase(e);cout << endl;tree.InOrder();}}
}//end of namespace KV

然后他的一个应用是用一个词搜索对应的另一个词，还有就是统计一篇文章中各个词出现了多少次。

void TestBSTree3()
{
// 输入单词，查找单词对应的中文翻译
BSTree<string, string> dict;
dict.Insert("string", "字符串");
dict.Insert("tree", "树");
dict.Insert("left", "左边、剩余");
dict.Insert("right", "右边");
dict.Insert("sort", "排序");
// 插入词库中所有单词
string str;
while (cin>>str)
{
BSTreeNode<string, string>* ret = dict.Find(str);
if (ret == nullptr)
{
cout << "单词拼写错误，词库中没有这个单词:" <<str <<endl;
}
else
{
cout << str << "中文翻译:" << ret->_value << endl;
}
}
}
void TestBSTree4()
{
// 统计水果出现的次数
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
BSTree<string, int> countTree;
for (const auto& str : arr)
{
// 先查找水果在不在搜索树中
// 1、不在，说明水果第一次出现，则插入<水果, 1>
// 2、在，则查找到的节点中水果对应的次数++
//BSTreeNode<string, int>* ret = countTree.Find(str);
auto ret = countTree.Find(str);
if (ret == NULL)
{
countTree.Insert(str, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
}


好的，如果本篇文章对你有帮助，不妨点个赞~谢谢。
在这里插入图片描述

EOF

这篇关于【二叉搜索树】K型与KV型二叉搜索树简单实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1131043。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu2289（简单二分）

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了  题意：已知圆台的体积，求高度 首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2