15. 【C++】详解搜索二叉树 | KV模型

目录

1.定义

初始化

插入

查找

删除

完整代码

2.运用

K 模型和 KV 模型详解

K 模型

KV 模型

代码解释


为了更好地理解 map 和 set 的特性,和后面讲解查找效率极高的平衡搜索二叉树,和红黑树去实现模拟,所以决定在这里对搜索二叉树进行一个讲解~

1.定义

二叉搜索树(Search Binary Tree)

每一颗子树都满足,左子树上所有节点的值都小于根节点的值,右子树都大于

所以就能得到性质:左子树的值 << 右子树的值

它也称二叉排序树或二叉查找树,最多找高度次 O(N)

二叉搜索树蜕化为单边树(或类似单边),其平均比较次数为:O(N)

搜索二叉树由于控制不了极端情况,与 O(logN) 失之交臂了,但后面讲到的平衡二叉搜索树可以做到。

初始化

template<class K>
struct BSTreeNode
{//全部都共有开放的,就直接定structBSTreeNode<K>* _left;//左结构体指针BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};
//定义一个树
template<class K>
class BATree{typedef BSTreeNode<K> Node;
private:Node* _root = nullptr;    // 这里我们构造函数都没必要写,它自己生成的就够用了
};

插入

思路:

  1. 检查是否有根结点 _root,如果没有我们就 new 一个结点出来作为根结点。
  2. 插入就需要找到插入位置,我们定义一个 cur 变量,从根节点开始,
    根据搜索二叉树 性质,将 cur 结点的 key 与插入的值 key 进行大小比较
  3. 仅仅 new 上一个新结点给 cur 是完成不了插入操作的!需要 cur 跟上一层(cur 的父亲)相链接才行!为了能找到上一层,所以我们还需要额外定义一个 parent 变量来记录 cur 的父结点

在我们更换 cur 结点时记录父结点的位置 parent=cur 即可。

parent 意义:确认位置,实现插入

     4.比较确定 cur 应该链接父亲的左边,还是链接父亲的右边,插入即可

//插入bool Insert(const K& key){//没有根节点就new一个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;}//不断比较,搜索找到了之后}//new了一个新节点,和parent的key比较,确定插入的左右cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}//将新节点插入到二叉树里面啦return true;}

再写一个中序遍历来测试一下插入的效果:

void InOrder(Node* root) {if (root == nullptr) {return;}InOrder(root->_left);            // 左cout << root->_key << " ";       // 值InOrder(root->_right);           // 右
}//测试
void TestBSTree() {BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a) {t.Insert(e);}t.InOrder();  ❌ 没法传根
}

此时会出现一个问题,因为根是私有的,我们没办法把根传过去,我们可以采取 getroot,这里的话,我们将其设为内部函数即可

	void InOrder() {_InOrder(_root);}private:// 改为内部函数void _InOrder(Node* root) {if (root == nullptr) {return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root = nullptr;
};

完整测试代码:

#include <iostream>
using namespace std;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() : _root(nullptr) {}bool Insert(const K& key) {if (_root == nullptr) {_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;//设置结构体形的cur节点,并进行初始化while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else {return false;  // Key already exists}}cur = new Node(key);if (parent->_key < key) {parent->_right = cur;}else {parent->_left = cur;}return true;}void InOrder() {_InOrder(_root);cout << endl;}private:void _InOrder(Node* root) {if (root == nullptr) {return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root;
};// 测试函数
void TestBSTree() {BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a) {t.Insert(e);}t.InOrder();
}int main() {TestBSTree();return 0;
}

打印:

查找

从根开始,如果要查找的值大于 cur 目前的值,则让 cur 往右走,反之往左走。

当查找得值与 cur 的值相等时则说明找到了,返回 true。

当 cur 触及到空(while 循环结束)则说明找不到,返回 false

//查找
bool 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 true;//找到啦}}return false;//为空了还没找到就退出}

删除

搜索二叉树删除的实现是有难度的,删除的实现就需要一些技巧了,断然删除会毁树。

我们可以以下面这棵树为例

分别一次删除 7,14,3,8

7 和 14 属于直接删除的场景

3,8 属于需要替换法进行删除的场景

总结:

没有孩子,或者一个孩子都好删(直接删,托孤即可)

两个孩子以上就要采取替换法(左子树的最大节点,或者右子树的最小节点)

1.该结点无左孩子

  1. 若该结点为 root,直接让 root 等于它的右孩子结点。(一定要先判断)

画忘了,画成右为空了qwq,大家同理的理解一下

 // 左为空if (cur->_left == nullptr){if (cur == _root){//如果是根节点,parent就变为空了_root = cur->_right;}else
  1. 判断 cur 是在父节点的左还是右支,判断后将其指向parent->right/left = cur->right ,直接将右边连过去,实现重新连接的延续
  2. 最后删除 cur 结点
if (cur->_left == nullptr) {//该结点无左孩子/* 判断要删除的结点是否为根结点 */if (cur == _root) {_root = cur->_right;}else {if (cur == father->_right) {//判断他是上一个节点的左节点还是右节点father->_right = cur->_right;}else {father->_left = cur->_right;}}delete cur;cur = nullptr;
}

左右都不为空--替换法

else
{//查找到左边的最右节点//右边的最左节点//交换//删除// 找替代节点Node* parent = cur;//不能设置为nullptr,循环可能不进去了//之后要对父节点进行处理Node* leftMax = cur->_left;//设置最大节点while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;//即最右节点}//交换keyswap(cur->_key, leftMax->_key);

删除的判断

//将parent置空处理,断联if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}
//删除cur的处理cur = leftMax;
}delete cur;return true;}}return false;

完整代码

#pragma oncetemplate<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():_root(nullptr){}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;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool 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 true;}}return false;}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->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}// 右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}					} // 左右都不为空 else{// 找替代节点Node* parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == NULL){return;}
//递归实现中序遍历的打印_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root;
};

测试:

void TestBSTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}t.InOrder();t.Erase(4);t.InOrder();t.Erase(6);t.InOrder();t.Erase(7);t.InOrder();t.Erase(3);t.InOrder();for (auto e : a){t.Erase(e);//插入}t.InOrder();
}

运行:

2.运用

K 模型和 KV 模型详解

K 模型

K 模型指的是只有 key 作为关键码的结构,在这种结构中只存储 key。K 模型常用于需要搜索具体值的场景,比如拼写检查、数字搜索等。

示例代码:K 模型的二叉搜索树

以下是一个实现 K 模型的二叉搜索树(BST)的完整代码示例:

#include <iostream>
using namespace std;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() : _root(nullptr) {}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;  // Key already exists}}cur = new Node(key);if (parent->_key < key) {parent->_right = cur;}else {parent->_left = cur;}return true;}void InOrder() {_InOrder(_root);cout << endl;}private:void _InOrder(Node* root) {if (root == nullptr) {return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root;
};// 测试函数
void TestBSTree() {BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a) {t.Insert(e);}t.InOrder();
}int main() {TestBSTree();return 0;
}
KV 模型

KV 模型表示每一个关键码 (key) 都有与之对应的值 (value),即 <Key, Value> 的键值对。这种结构常用于字典、映射、统计等场景。

示例代码:KV 模型的二叉搜索树

以下是一个实现 KV 模型的二叉搜索树的完整代码示例:

#include <iostream>
#include <string>
using namespace std;template<class K, class V>
struct BSTreeNode {BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value): _left(nullptr), _right(nullptr), _key(key), _value(value){}
};template<class K, class V>
class BSTree {typedef BSTreeNode<K, V> Node;public:BSTree() : _root(nullptr) {}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 {cur->_value = value;  // Update value if key already existsreturn true;}}cur = new Node(key, value);if (parent->_key < key) {parent->_right = cur;}else {parent->_left = cur;}return true;}bool Find(const K& key, V& value) {Node* cur = _root;while (cur) {if (cur->_key < key) {cur = cur->_right;}else if (cur->_key > key) {cur = cur->_left;}else {value = cur->_value;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 << ", " << root->_value << "> ";_InOrder(root->_right);}Node* _root;
};// 测试函数
void TestKVTree() {BSTree<string, string> dict;dict.Insert("apple", "苹果");dict.Insert("banana", "香蕉");dict.Insert("cherry", "樱桃");string value;if (dict.Find("banana", value)) {cout << "banana: " << value << endl;}dict.InOrder();
}int main() {TestKVTree();return 0;
}

代码解释

  1. 节点结构定义
template<class K, class V>
struct BSTreeNode {BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value): _left(nullptr), _right(nullptr), _key(key), _value(value){}
};
    • 这是一个模板结构,表示二叉搜索树的节点。每个节点包含一个键值对 (key, value) 以及指向左子节点和右子节点的指针。
  1. 二叉搜索树类定义
template<class K, class V>
class BSTree {typedef BSTreeNode<K, V> Node;public:BSTree() : _root(nullptr) {}
    • 这是一个模板类,表示二叉搜索树。包含根节点指针 _root 以及插入、查找和中序遍历的方法。
  1. 插入方法
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 {cur->_value = value;  // Update value if key already existsreturn true;}}cur = new Node(key, value);if (parent->_key < key) {parent->_right = cur;}else {parent->_left = cur;}return true;
}
    • 插入方法用于将新的键值对插入到树中。通过比较键值确定新节点应该插入的位置。如果键已存在,则更新其对应的值。
  1. 查找方法
bool Find(const K& key, V& value) {Node* cur = _root;while (cur) {if (cur->_key < key) {cur = cur->_right;}else if (cur->_key > key) {cur = cur->_left;}else {value = cur->_value;return true;}}return false;
}
    • 查找方法用于查找指定键的值。如果找到该键,则返回对应的值。
  1. 中序遍历方法
void InOrder() {_InOrder(_root);cout << endl;
}private:
void _InOrder(Node* root) {if (root == nullptr) {return;}_InOrder(root->_left);cout << "<" << root->_key << ", " << root->_value << "> ";_InOrder(root->_right);
}
    • 中序遍历方法用于遍历树并输出键值对。递归地遍历左子树、访问根节点、然后遍历右子树。
  1. 测试函数
void TestKVTree() {BSTree<string, string> dict;dict.Insert("apple", "苹果");dict.Insert("banana", "香蕉");dict.Insert("cherry", "樱桃");string value;if (dict.Find("banana", value)) {cout << "banana: " << value << endl;}dict.InOrder();
}int main() {TestKVTree();return

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【06】LLaMA-Factory微调大模型——微调模型评估

上文【05】LLaMA-Factory微调大模型——初尝微调模型&#xff0c;对LLama-3与Qwen-2进行了指令微调&#xff0c;本文则介绍如何对微调后的模型进行评估分析。 一、部署微调后的LLama-3模型 激活虚拟环境&#xff0c;打开LLaMA-Factory的webui页面 conda activate GLM cd LLa…

基于STM32的智能加湿器设计

目录 1、设计要求 2、系统功能 3、演示视频和实物 4、系统设计框图 5、软件设计流程图 6、原理图 7、主程序 8、总结 &#x1f91e;大家好&#xff0c;这里是5132单片机毕设设计项目分享&#xff0c;今天给大家分享的题目是&#xff1a;《7、基于STM32的智能加湿器设计…

4 C 语言控制流与循环结构的深入解读

目录 1 复杂表达式的计算过程 2 if-else语句 2.1 基本结构及示例 2.2 if-else if 多分支 2.3 嵌套 if-else 2.4 悬空的 else 2.5 注意事项 2.5.1 if 后面不要加分号 2.5.2 省略 else 2.5.3 省略 {} 2.5.4 注意点 3 while 循环 3.1 一般形式 3.2 流程特点 3.3 注…

查看Windows中监听的端口及其关联的服务

文章目录 I 查看Windows中监听的端口及其关联的服务进程id1.1 列出了所有监听的端口及其关联的服务1.2 查找特定的端口是否开放1.3 查看哪些服务正在监听这些端口II 根据进程id查看进程名称基于cmd窗口,查看程序运行端口状态(关联服务进程id)和关联的服务进程信息 I 查看Win…

LLM大模型实战项目--基于Stable Diffusion的电商平台虚拟试衣

本文详细讲解LLM大模型实战项目&#xff0c;基于Stable Diffusion的电商平台虚拟试衣 一、项目介绍 二、阿里PAI平台介绍 三、阿里云注册及开通PAI 四、PAI_DSW环境搭建 五、SDLORA模型微调 一、项目介绍 AI虚拟试衣是一种创新的技术&#xff0c;利用人工智能和计算机视觉技…

MacBook电脑远程连接Linux系统的服务器方法

一、问题简介 Windows 操作系统的电脑可使用Xshell等功能强大的远程连接软件。通过连接软件&#xff0c;用户可以在一台电脑上访问并控制另一台远程计算机。这对于远程技术支持、远程办公等场景非常有用。但是MacBook电脑的macOS无法使用Xshell。 在Mac上远程连接到Windows服…

Golang | Leetcode Golang题解之第238题除自身以外数组的乘积

题目&#xff1a; 题解&#xff1a; func productExceptSelf(nums []int) []int {length : len(nums)// L 和 R 分别表示左右两侧的乘积列表L, R, answer : make([]int, length), make([]int, length), make([]int, length)// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 …

Java(二十二)---队列

文章目录 前言1.队列(Queue)的概念2.Queue的使用3.队列的模拟实现4.循环队列5.双端队列6.面试题[1. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues/description/)[2. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/de…

django中日志模块logging的配置和使用

一、文件的配置 settings.py文件中添加LOGGING块的配置&#xff0c;配置如下 # 日志记录 LOGGING {"version": 1,"disable_existing_loggers": False, # 用于确定在应用新的日志配置时是否禁用之前配置的日志器# 格式器"formatters": {"v…

自动化测试中如何应对网页弹窗的挑战!

在自动化测试中&#xff0c;网页弹窗的出现常常成为测试流程中的一个难点。无论是警告框、确认框、提示框&#xff0c;还是更复杂的模态对话框&#xff0c;都可能中断测试脚本的正常执行&#xff0c;导致测试结果的不确定性。本文将探讨几种有效的方法来应对网页弹窗的挑战&…

Android 视频亮度图标

源码 import android.content.Context; import android.graphics.Canvas; import android.graphics.Color; import android.graphics.Paint; import android.util.AttributeSet; import android.view.View;import androidx.annotation.Nullable;public class VideoBrightness …

优雅的软件工程师

今天写算法的时候、通过两道题深深意识到了&#xff0c;什么是优雅的代码&#xff08;应该说不按套路出牌的代码&#xff09; 我被折服了 第一个就是141. 环形链表 - 力扣&#xff08;LeetCode&#xff09; 判断换环状链表 我的思路就是用快慢指针判断&#xff0c;非常平平无…

SAP MR21 和 MR22 区别

MR21和MR22用来调整库存金额的话&#xff0c;两者之间有什么区别呢 一个是直接修改金额 一个是在原来的基础上进行加减。 MR21改的是单个物料的价格。 MR22改的是库存总价值。 MR**是不能改标准价格的&#xff0c;即使改了也到PRD去了&#xff0c;只能改移动平均价 MR21 : 商品…

HTTP协议、Wireshark抓包工具、json解析、天气爬虫

HTTP超文本传输协议 HTTP&#xff08;Hyper Text Transfer Protocol&#xff09;&#xff1a; 全称超文本传输协议&#xff0c;是用于从万维网&#xff08;WWW:World Wide Web &#xff09;服务器传输超文本到本地浏览器的传送协议。 HTTP 协议的重要特点&#xff1a; 一发一收…

简过网:备考25年国考的朋友,你的时间规划做好了吗?

备考25年国考的朋友&#xff0c;你的时间规划做好了吗&#xff1f; 根据以往考试时间&#xff0c;我们先预测一下25年的国考时间&#xff1a; 国考报名&#xff1a;24年10月中旬 国考笔试&#xff1a;24年11月底 省考报名&#xff1a;25年1-2月 省考笔试&#xff1a;25年3…

AnalyticsCloud 分析云 任意文件读取漏洞复现

0x01 产品简介 AnalyticsCloud 分析云集成了先进的数据分析技术和工具&#xff0c;能够处理来自各种数据源的数据&#xff0c;包括云数据、本地数据、传统数据和大数据等。它提供了从数据收集、整理、分析到应用的全链路解决方案&#xff0c;帮助企业更好地理解和利用数据&…

处理.git文件夹过大出现臃肿问题

1、问题背景 在软件开发过程中&#xff0c;版本控制是一个至关重要的环节。Git 作为一种流行的分布式版本控制系统&#xff0c;被广泛应用于各种项目中。然而&#xff0c;近期我们发现在进行项目发版时&#xff0c;Git 克隆项目的时间显著增加&#xff0c;严重影响了发版的效率…

深入理解Java并发编程:从synchronized到Lock的演进

目录 引言 一、synchronized关键字基础 二、Lock接口及其实现 三、ReentrantLock实战 1. 原子类&#xff08;Atomic Classes&#xff09; 2. 并发集合&#xff08;Concurrent Collections&#xff09; 3. 线程池&#xff08;ThreadPool&#xff09; 4. 并发工具类&…

四川赤橙宏海商务信息咨询有限公司真实可靠吗?

在当今数字化浪潮中&#xff0c;电商行业正以前所未有的速度蓬勃发展&#xff0c;而抖音作为短视频领域的佼佼者&#xff0c;其电商服务更是异军突起&#xff0c;成为众多商家争相入驻的新蓝海。四川赤橙宏海商务信息咨询有限公司&#xff0c;正是这一领域的佼佼者&#xff0c;…

【Git标签管理】理解标签 | 创建标签 | 查看标签 | 删除标签 | 推送标签

目录 1.理解标签 2.创建标签 3.查看标签 4.删除本地仓库的标签 5.推送标签 6.删除远程仓库的标签 1.理解标签 Git提供一个打标签的功能tag&#xff0c;对某一次事务/提交的表示&#xff08;作用/意义&#xff09;。标签 tag &#xff0c;可以简单的理解为是对某次 comm…