【C++从0到王者】第二十八站:二叉搜索树的应用

news/2025/3/16 21:04:07/

文章目录

  • 前言
  • 一、Key模型
  • 二、Key/Value模型
  • 总结

前言

二叉搜索树的在现实世界的应用很广泛,比如Key模型,Key-Value模型就是常见的两种的模型

一、Key模型

K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。即就是判断key在不在就可以了。

比如:门禁系统,小区车辆出入系统等等

给一个单词word,判断该单词是否拼写正确,具体方式如下:
以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。

我们前面文章中所完成的二叉搜索树就是key模型的二叉搜身树

二、Key/Value模型

Key/Value每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:比如商场的车辆出入系统(计时付费),高铁实名制车票系统等
比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文<word, chinese>就构成一种键值对;
再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出现次数就是<word, count>就构成一种键值对

现在就让我们来实现一个key-value模型的二叉搜索树。

#pragma oncetemplate<class K, class V>
struct BSTreeNode
{BSTreeNode(const K& key = K(), const V& val = V()):_key(key),_val(val),_left(nullptr),_right(nullptr){}K _key;V _val;BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K,V> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K,V>& t){_root = Copy(t._root);}~BSTree(){_Destory(_root);}BSTree<K,V>& operator=(BSTree<K,V> t){std::swap(_root, t._root);return *this;}bool Insert(const K& key,const V& val){if (_root == nullptr){_root = new Node(key,val);return true;}else{Node* parent = _root;Node* cur = _root;while (cur != nullptr){if (cur->_key == key){return false;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}cur = new Node(key,val);if (parent->_key > key){parent->_left = cur;}else if (parent->_key < key){parent->_right = cur;}return true;}}void InOrder(){_InOrder(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key == key){return cur;}else if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}}return nullptr;}bool Erase1(const K& key){Node* cur = _root;Node* 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 (parent == nullptr){if (cur->_left == nullptr){_root = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){_root = cur->_left;delete cur;return true;}else{Node* leftMaxParent = cur;Node* leftMax = cur->_left;if (leftMax->_right == nullptr){leftMax->_right = cur->_right;delete cur;_root = leftMax;return true;}while (leftMax->_right){leftMaxParent = leftMax;leftMax = leftMax->_right;}std::swap(leftMax->_key, cur->_key);std::swap(leftMax->_val, cur->_val);leftMaxParent->_right = leftMax->_left;delete leftMax;leftMax = nullptr;return true;}}if (parent->_left == cur){if (cur->_left == nullptr){parent->_left = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){parent->_left = cur->_left;delete cur;return true;}else {Node* leftMaxParent = cur;Node* leftMax = cur->_left;if (leftMax->_right == nullptr){leftMax->_right = cur->_right;delete cur;parent->_left = leftMax;return true;}while (leftMax->_right){leftMaxParent = leftMax;leftMax = leftMax->_right;}std::swap(leftMax->_key, cur->_key);std::swap(leftMax->_val, cur->_val);leftMaxParent->_right = leftMax->_left;delete leftMax;leftMax = nullptr;return true;}}else{if (cur->_left == nullptr){parent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){parent->_right = cur->_left;delete cur;return true;}else{Node* leftMaxParent = cur;Node* leftMax = cur->_left;if (leftMax->_right == nullptr){leftMax->_right = cur->_right;delete cur;parent->_right = leftMax;return true;}while (leftMax->_right){leftMaxParent = leftMax;leftMax = leftMax->_right;}std::swap(leftMax->_key, cur->_key);std::swap(leftMax->_val, cur->_val);leftMaxParent->_right = leftMax->_left;delete leftMax;leftMax = nullptr;return true;}}}}return false;}bool Erase2(const K& key){Node* cur = _root;Node* 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){_root = cur->_right;}else if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right == cur){parent->_right = cur->_right;}}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else if (parent->_left == cur){parent->_left = cur->_left;}else if (parent->_right = cur){parent->_right = cur->_left;}}else{Node* leftMax = cur->_left;Node* leftMaxParent = cur;while (leftMax->_right){leftMaxParent = leftMax;leftMax = leftMax->_right;}std::swap(cur->_key, leftMax->_key);std::swap(cur->_val, leftMax->_val);if (leftMaxParent->_left == leftMax){leftMaxParent->_left = leftMax->_left;}else{leftMaxParent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}}Node* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key,const V& val){return _InsertR(_root, key, val);}bool EraseR(const K& key){return _EraseR(_root, key);}
private:Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* Copyroot = new Node(root->_key, root->val);Copyroot->_left = Copy(root->_left);Copyroot->_right = Copy(root->_right);return Copyroot;}void _Destory(Node*& root){if (root == nullptr){return;}_Destory(root->_left);_Destory(root->_right);delete root;root == nullptr;}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{Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}std::swap(leftMax->_key, root->_key);std::swap(leftMax->_val, root->_val);return _EraseR(root->_left, key);}delete del;return true;}}bool _InsertR(Node*& root, const K& key, const V& val){if (root == nullptr){root = new Node(key, val);return true;}if (root->_key < key){return _InsertR(root->_right, key, val);}else if (root->_key > key){return _InsertR(root->_left, key, val);}else{return false;}}Node* _FindR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key == key){return root;}else if (root->_key > key){return _FindR(root->_left, key);}else{return  _FindR(root->_right, key);}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " :" << root->_val << endl;_InOrder(root->_right);}
private:Node* _root;
};

如上就是我们的KV模型的二叉搜索树。我们可以使用如下的两个模型,就是我们的这棵树的应用

void test1()
{BSTree<string, string> dic;dic.Insert("review", "复习");dic.Insert("product", "产品,产物");dic.Insert("education", "教育");dic.Insert("interfere", "干涉");cout << "请输入单词" << endl;string str;while (cin >> str){BSTreeNode<string, string>* ret = dic.Find(str);if (ret){cout << ret->_val << endl;}else{cout << "无此单词" << endl;cout << "请你添加单词的意思:" << endl;string str_val;cin >> str_val;dic.Insert(str, str_val);}cout << "请输入单词" << endl;}
}

如上就是一个查找单词的模型,可以帮我们快速找出单词的意思,如果没有,可以自行添加意思

image-20230908132917937

如下所示是一个水果计数的应用

void test2()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> FruitCount;for (auto& e : arr){BSTreeNode<string, int>* ret = FruitCount.Find(e);if (ret == nullptr){FruitCount.Insert(e, 1);}else{ret->_val++;}}FruitCount.InOrder();}

image-20230908133012844


总结

本节主要讨论了二叉搜索树的两种应用。希望能对大家带来帮助


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

相关文章

小程序分销机制介绍,小程序二级分销功能有哪些?

为什么有越来越多的用户选择使用小程序&#xff1f;跟“高大上”的APP相比&#xff0c;小程序不仅可以减少下载安装的复杂流程&#xff0c;还具备操作便捷、沉淀私域数据的优势。蚓链分销小程序具备裂变二维码、实时分佣、分销身份升级、层级分佣、商品个性化佣金设定等功能&am…

(其他) 剑指 Offer 61. 扑克牌中的顺子 ——【Leetcode每日一题】

❓剑指 Offer 61. 扑克牌中的顺子 难度&#xff1a;简单 从若干副扑克牌中随机抽 5 张牌&#xff0c;判断是不是一个顺子&#xff0c;即这5张牌是不是连续的。2&#xff5e;10为数字本身&#xff0c;A为1&#xff0c;J为11&#xff0c;Q为12&#xff0c;K为13&#xff0c;而大…

草莓CDMS独创的内容分销系统 微信小说平台系统v1.0

草莓CDMS是一个采用thinkphp5.1Easywechat4.0swooleredis开发的原创内容分销系统&#xff0c;其特点包括简单操作、灵活后台设置、两种对接模式以及五种用户角色等。系统集成了微信开放平台扫码授权和微信公众平台手动对接的功能&#xff0c;并支持多种经营模式&#xff0c;如平…

在 Arweave 中轻松管理文件:借助 4EVERLAND 完成 Web3 前端Path Manifests的终极指南

为什么使用Path Manifests&#xff1f; 当在 IPFS 上发布 NFT 时&#xff0c;图片和元数据会被上传到 IPFS 网络以获得一个根 CID&#xff0c;其形式如下&#xff1a; ipfs://bafybeic36ik6cngu37xbzmpytuvyo7z3lyeen44clkkxq5d263zj4nkzr4 通过使用这个根 CID&#xff0c;每…

站在自动装配角度浅析Spring和SpringBoot的区别

Spring的自动装配实现步骤可以理解为两步&#xff1a;加载类&#xff0c;注入类。首先Spring容器启动的时候会扫描Spring配置文件&#xff0c;基于类加载器机制通过配置文件指定的扫包路径批量递归加载类&#xff0c;把加载的类注册成Bean组件放入Spring上下文容器ApplicationC…

vscode 画流程图

文章目录 1、安装插件 draw2、新建文件3、开始画图4、另存为图片 vscode可以画流程图了&#xff0c;只需要安装插件就可以了。 1、安装插件 draw 2、新建文件 3、开始画图 4、另存为图片

企业faq系统搭建平台Baklib,企业自定义管理平台

FAQ是当前网络上提供在线帮助的主要手段&#xff0c;通过事先组织好一些可能的常见问题的问答&#xff0c;发布在网页上为用户提供咨询服务。许多的Web用户都更加偏向于可信赖的FAQ页面&#xff0c;以此作为快速查找更多信息的方法。因为用户时间的紧缺&#xff0c;并且想知道产…

2023年9月制造业NPDP产品经理国际认证报名来这错不了

产品经理国际资格认证NPDP是新产品开发方面的认证&#xff0c;集理论、方法与实践为一体的全方位的知识体系&#xff0c;为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会&#xff08;PDMA&#xff09;成立于1979年&#xff0c;是…