数据结构之搜索二叉树

目录

一、什么是搜索二叉树

基本概念

特点

注意事项

二、搜索二叉树的C++实现

2.0 构造与析构

2.1 插入

2.2 查找

2.3 删除

2.3.1 无牵无挂型

2.3.2 独生子女型

2.3.3 儿女双全型

三、搜索二叉树的应用

3.1 key搜索

3.2 key/value搜索

一、什么是搜索二叉树

搜索二叉树，通常称为二叉搜索树（BST，Binary Search Tree），是一种特殊的二叉树数据结构。

基本概念

  • 节点结构：二叉搜索树由一系列节点组成，每个节点包含一个键值（用于比较）和一个与之关联的值。
  • 树结构：每个节点最多有两个子节点，分别称为左子节点和右子节点。

特点

  • 有序性：二叉搜索树的核心特点是有序性。对于树中的任意节点：
    • 所有左子树的节点键值均小于该节点的键值。
    • 所有右子树的节点键值均大于该节点的键值。
  • 查找效率：由于有序性，二叉搜索树可以在对数时间内（树的高度次）完成查找、插入和删除操作，即时间复杂度为O(log n)，其中n是树中节点的数量。
  • 动态性：二叉搜索树支持动态数据集合的操作，允许在运行时添加或删除元素。

注意事项

  • 当二叉搜索树不平衡时，其性能可能会退化到接近线性时间复杂度O(n)，此时可能需要使用平衡二叉搜索树（如AVL树或红黑树）来保证操作的效率。具体请关注博主后续博客

二、搜索二叉树的C++实现

2.0 构造与析构

template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};
~BSTree()
{Destroy(_root);_root = nullptr;
}
//递归删除
void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}
BSTree(const BSTree& t)
{_root = Copy(t._root);
}BSTree& operator=(BSTree tmp)
{swap(_root, tmp._root);return *this;
}
//递归复制
Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;
}

2.1 插入

思路

  • 树为空，则直接新增结点，赋值给root指针
  • 树不空，按⼆叉搜索树性质，插入值比当前结点⼤往右⾛，插入值比当前结点小往左⾛，找到空位置，插⼊新结点。
  • 如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插入新结点。

难点

  • 为提升效率，不采用递归做法，采用循环模拟递归
  • 二叉搜索树的性质决定了必有一个空节点会存放当前key值
  • 为了维持二叉搜索树的性质，需要额外引入parent指针。最后插入的位置需要与parent所指向的值进行比对，决定插入在左子树还是右子树。
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 true;}}node* newnode = new node(key);if (parent->_key > key){parent->_left = newnode;}else{parent->_right = newnode;}return true;
}

2.2 查找

思路

  1. 从根开始⽐较，查找x，⽐根的值⼤则往右边⾛，⽐根值⼩则往左边⾛。
  2. 最多查找⾼度次，⾛到到空，还没找到，这个值不存在。
  3. 本文实现不支持插入冗余值（模拟实现STL库中的set）
  4. 如果要模拟实现STL库中的multiset，STL库中实现的是返回中序遍历的第一个相等的节点
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;
}

2.3 删除

删除有如下三种情况

2.3.1 无牵无挂型

把结点的⽗亲对应孩⼦指针指向空，直接删除N结点

2.3.2 独生子女型

把N结点的⽗亲对应孩⼦指针指向N的右/左孩⼦，直接删除N结点

2.3.3 儿女双全型

采用替代法：

  1. 找左子树的最⼤结点(最右结点)或者右子树的最⼩结点(最左结点)替代N，直接复制值替代即可
  2. 然后转成删除替代节点

bool Erase(const K& key)
{node* parent = nullptr;node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}//删除else{//如果左为空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{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;//最左节点依然可能有最右节点if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;
}

三、搜索二叉树的应用

3.1 key搜索

Key搜索指的是使用“key”（关键字或关键项）作为检索依据来快速查找和检索数据的过程。在二叉搜索树中，通过比较节点的Key与要查找的Key，可以确定搜索方向（向左或向右），直到找到匹配的节点或确定目标不存在。

3.2 key/value搜索

Key/Value搜索是一种基于键值对（Key-Value Pair）的数据检索方式。在这种模式下，数据被组织成一系列的键值对，每个键值对由一个唯一的键（Key）和一个与之相关联的值（Value）组成。搜索时，用户通过提供键来查询对应的值。

Key/Value搜索的实现方式常用的有以下几种

  1. 哈希表：
    • 哈希表是实现Key/Value搜索的一种常见数据结构。通过哈希函数将键映射到表的某个位置，以快速定位到对应的值。
  2. B树及其变种：
    • 在一些需要持久化存储的Key/Value数据库中，可能会使用B树（如B+树）或其变种来存储数据。这些数据结构通过保持数据的有序性来优化搜索和范围查询的性能。
  3. 分布式哈希表：
    • 在分布式系统中，分布式哈希表（DHT）是一种用于实现Key/Value搜索的分布式数据结构。它通过将键分散到多个节点上来实现数据的分布式存储和检索。

本文介绍用二叉搜索树实现key/value搜索

#pragma once
#include<iostream>
using namespace std;namespace key_value
{template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{typedef BSTNode<K> Node;public:// 强制生成构造BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}~BSTree(){Destroy(_root);_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{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* 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 cur;}}return nullptr;}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->_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{Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_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 << ":" << root->_value << endl;_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* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

数值计算 --- 平方根倒数快速算法(中)

数值计算 --- 平方根倒数快速算法(中)

平方根倒数快速算法(中) --- 向Greg Walsh致敬&#xff01; 在前面的介绍中&#xff0c;我们已经知道了这段代码的作者Greg Walsh在函数的最后使用了NR-iteration&#xff0c;且只用了一次NR-iteration就能达到比较理想的精度。这样一来&#xff0c;选择正确的初值就显得尤为重…
阅读更多...
云原生｜浅谈云原生中的对象存储之MinIO 的使用

云原生｜浅谈云原生中的对象存储之MinIO 的使用

一、什么是对象储存 对象存储&#xff08;Object Storage&#xff09;以对象的形式存储和管理数据&#xff0c;这些对象可以是任何类型的数据&#xff0c;例如 PDF&#xff0c;视频&#xff0c;音频&#xff0c;文本或其他文件类型。对象存储使用分布式存储架构&#xff0c;数据…
阅读更多...
C语言贪吃蛇小游戏演示和说明

C语言贪吃蛇小游戏演示和说明

C语言贪吃蛇小游戏演示和说明 设计贪吃蛇游戏的主要目的是让大家夯实C语言基础&#xff0c;训练编程思维&#xff0c;培养解决问题的思路&#xff0c;领略多姿多彩的C语言。 游戏开始后&#xff0c;会在中间位置出现一条只有三个节点的贪吃蛇&#xff0c;并随机出现一个食物&am…
阅读更多...
数据结构练习题————(二叉树)——考前必备合集！

数据结构练习题————(二叉树)——考前必备合集！

今天在牛客网和力扣上带来了数据结构中二叉树的进阶练习题 1.二叉搜索树与双向链表———二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com) 2.二叉树遍历————二叉树遍历_牛客题霸_牛客网 (nowcoder.com) 3.二叉树的层序遍历————102. 二叉树的层序遍历 - 力扣&am…
阅读更多...
寿司检测系统源码分享

寿司检测系统源码分享

寿司检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vision …
阅读更多...
一文了解高速工业相机

一文了解高速工业相机

超高速相机是工业相机的一种&#xff0c;一般高速相机指的是数字工业相机&#xff0c;其一般安装在机器流水线上代替人眼来做测量和判断&#xff0c;通过数字图像摄取目标转换成图像信号&#xff0c;传送给专用的图像处理系统。 超高速工业相机的采集速率> 50Gb/s&#xff…
阅读更多...
window系统DockerDesktop 部署windows容器

window系统DockerDesktop 部署windows容器

目录 参考文献1、安装Docker Desktop1.1 下载安装包1.2 安装教程1.3 异常解决 2、安装windows容器2.1 先启动DockerDesktop 软件界面2.2 检查docker版本2.3 拉取windows镜像2.4 网盘下载windows镜像 参考文献 windows容器docker中文官网 Docker: windows下跑windows镜像 1、安…
阅读更多...
软件测试标准流程（思维导图版）

软件测试标准流程（思维导图版）

一套标准的流程在实际工作落地并执行起来&#xff0c;针对管理可起到很好的作用。 针对效率可在工作中不断的执行&#xff0c;执行后不断的进行优化&#xff0c;再次执行&#xff0c;在不断的工作实践中慢慢完善最终适用于整个团队。 这就是标准流程的作用与实际的好处&#…
阅读更多...
华为申请鸿蒙甄选、鸿蒙优选商标，加词的注意！

华为申请鸿蒙甄选、鸿蒙优选商标，加词的注意！

近日华为在35类广告销售上申请鸿蒙智选、鸿蒙优选、鸿蒙精品&#xff0c;鸿蒙甄选等商标&#xff0c;后面所加的词智选、优选、精品、甄选等基本上是属于通用词。 这样在35类拿到鸿蒙通用词商标&#xff0c;需要先拿到“鸿蒙“商标&#xff0c;经普推知产商标老杨检索发现&…
阅读更多...
【Linux】yum、vim、gcc使用(超详细)

【Linux】yum、vim、gcc使用(超详细)

目录 yum 安装软件 卸载软件 查看安装包 安装一下好玩的命令 vim vim基本操作 模式切换 命令集 vim批量注释 vim配置 gcc 函数库 小知识点&#xff1a; Linux中常见的软件安装方式 --------- 下载&&安装 a、yum/apt b、rpm安装包安装 c、源码安装 y…
阅读更多...
周家庄智慧旅游小程序

周家庄智慧旅游小程序

项目概述 周家庄智慧旅游小程序将通过数字化手段提升游客的旅游体验&#xff0c;依托周家庄的自然与文化资源&#xff0c;打造智慧旅游新模式。该小程序将结合虚拟现实&#xff08;VR&#xff09;、增强现实&#xff08;AR&#xff09;和人工智能等技术&#xff0c;提供丰富的…
阅读更多...
vue嵌套路由刷新页面空白问题

vue嵌套路由刷新页面空白问题

问题描述 在vue项目开发中遇到这样一个问题&#xff0c;在history模式下通过页面点击路由跳转可以打开页面&#xff0c;但是在当前页面刷新就空白了&#xff0c;如下&#xff1a; 点击路由跳转页面是有的 刷新页面就空白 代码 {path: "/home",name: "home&qu…
阅读更多...
SQL常用数据过滤 - EXISTS运算符

SQL常用数据过滤 - EXISTS运算符

SQL查询中的EXISTS运算符用于检查查询子句是否存在满足特定条件的记录&#xff0c;如果有一条或者多条记录存在&#xff0c;则返回True&#xff0c;否则返回False。 语法结构 SELECT column_name(s)FROM table_nameWHERE EXISTS(SELECT column_name FROM table_name WHERE co…
阅读更多...
React学习笔记（2.0）

React学习笔记（2.0）

React事件绑定 语法&#xff1a;在对应标签上书写on事件&#xff08;比如onClick,onChange&#xff09;&#xff0c;注意和原生的事件区分&#xff0c;React的事件首字母要大写。 const handleChange(e:any)>{console.log(e);console.log(change事件触发);// e不是原生事件…
阅读更多...
Acwing 最小生成树

Acwing 最小生成树

最小生成树 最小生成树:由n个节点&#xff0c;和n-1条边构成的无向图被称为G的一棵生成树&#xff0c;在G的所有生成树中&#xff0c;边的权值之和最小的生成树&#xff0c;被称为G的最小生成树。&#xff08;换句话说就是用最小的代价把n个点都连起来&#xff09; Prim 算法…
阅读更多...
初识Jenkins持续集成系统

初识Jenkins持续集成系统

随着软件开发复杂度的不断提高&#xff0c;团队成员之间如何更好地协同工作以确保软件开发的质量&#xff0c;已经慢慢成为开发过程中不可回避的问题。Jenkins 自动化部署可以解决集成、测试、部署等重复性的工作&#xff0c;工具集成的效率明显高于人工操作;并且持续集成可以更…
阅读更多...
Java线程池详解

Java线程池详解

目录 前言 线程池概述 线程池的实现 线程池的构造 拒绝策略 任务队列 线程池的工作原理 线程池的监控 Executors线程池工厂 自定义线程池 使用线程池的好处 应用场景 总结 本文详细探讨了线程池在并发编程领域的应用&#xff0c;介绍了ThreadPoolExecutor的核心组…
阅读更多...
MySQL的登录、访问、退出

MySQL的登录、访问、退出

一、登录&#xff1a; 访问MySQL服务器对应的命令&#xff1a;mysql.exe ,位置&#xff1a;C:\Program Files\MySQL\MySQL Server 8.0\bin &#xff08;mysql.exe需要带参数执行&#xff0c;所以直接在图形界面下执行该命令会自动结束&#xff09; 执行mysql.exe命令的时候出…
阅读更多...
2024年9月26日历史上的今天大事件早读

2024年9月26日历史上的今天大事件早读

1620年9月26日 大明皇帝朱常洛驾崩 1815年9月26日 俄、普、奥三国在巴黎发表缔结“神圣同盟” 1841年9月26日 清代思想家、诗人龚自珍逝世 1849年9月26日 “生理学之父”巴甫洛夫诞生 1909年9月26日 云南陆军讲武堂创办 1953年9月26日 画家徐悲鸿逝世 1980年9月26日 国际…
阅读更多...
VulnHub-Narak靶机笔记

VulnHub-Narak靶机笔记

Narak靶机笔记 概述 Narak是一台Vulnhub的靶机&#xff0c;其中有简单的tftp和webdav的利用&#xff0c;以及motd文件的一些知识 靶机地址&#xff1a; https://pan.baidu.com/s/1PbPrGJQHxsvGYrAN1k1New?pwda7kv 提取码: a7kv 当然你也可以去Vulnhub官网下载 一、nmap扫…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023