中国建设网站齐齐哈尔市,网站被黑 禁止js跳转,网络营销与直播电商是什么,wordpress插件 wp audio player#x1f31f;个人主页#xff1a;落叶 #x1f31f;当前专栏: C专栏 目录 ⼆叉搜索树的概念 ⼆叉搜索树的性能分析 ⼆叉搜索树的插⼊
⼆叉搜索树的查找
二叉搜索树中序遍历
⼆叉搜索树的删除
cur的左节点为空的情况
cur的右节点为空的情况
左#xff0c;右节点都不为… 个人主页落叶 当前专栏: C专栏 目录 ⼆叉搜索树的概念 ⼆叉搜索树的性能分析 ⼆叉搜索树的插⼊
⼆叉搜索树的查找
二叉搜索树中序遍历
⼆叉搜索树的删除
cur的左节点为空的情况
cur的右节点为空的情况
左右节点都不为空的情况
二叉搜索树【实现代码】
⼆叉搜索树key和key/value使⽤场景
key/value搜索场景
key/value⼆叉搜索树代码实现 ⼆叉搜索树的概念
⼆叉搜索树⼜称⼆叉排序树它或者是⼀棵空树或者是具有以下性质的⼆叉树: 若它的左⼦树不为空则左⼦树上所有结点的值都⼩于等于根结点的值若它的右⼦树不为空则右⼦树上所有结点的值都⼤于等于根结点的值它的左右⼦树也分别为⼆叉搜索树⼆叉搜索树中可以⽀持插⼊相等的值也可以不⽀持插⼊相等的值具体看使⽤场景定义后续我 们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树其中map/set不⽀持插⼊相等 值multimap/multiset⽀持插⼊相等值 ⼆叉搜索树的性能分析
最优情况下⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)其⾼度为 O(log2 N) 所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为 O(N)
那么这样的效率显然是⽆法满⾜我们需求的我们后续课程需要继续讲解⼆叉搜索树的变形平衡⼆ 叉搜索树AVL树和红⿊树才能适⽤于我们在内存中存储和搜索数据。
另外需要说明的是⼆分查找也可以实现 O(logN) 级别的查找效率但是⼆分查找有两⼤缺陷 需要存储在⽀持下标随机访问的结构中并且有序。插⼊和删除数据效率很低因为存储在下标随机访问的结构中插⼊和删除数据⼀般需要挪动数 据。 这⾥也就体现出了平衡⼆叉搜索树的价值。 ⼆叉搜索树的插⼊
插⼊的具体过程如下 树为空则直接新增结点赋值给root指针树不空按⼆叉搜索树性质插⼊值⽐当前结点⼤往右⾛插⼊值⽐当前结点⼩往左⾛找到空位 置插⼊新结点。如果⽀持插⼊相等的值插⼊值跟当前结点相等的值可以往右⾛也可以往左⾛找到空位置插 ⼊新结点。要注意的是要保持逻辑⼀致性插⼊相等的值不要⼀会往右⾛⼀会往左⾛ int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};
下面我们可以看到要插入一个16节点比8大往右边走比10大往右走比14大往右走走到空了就可以插入16这个节点了。 下面我们要插入3这个节点比8小往左边走 如果和3允许冗余的情况下往后大的走。 当cur循环到空时候就在这个位置插入3这个节点还需要parent记录上一个节点用来和3节点进行连接。 接下来创建节点构造用于申请新节点后初始化 //定义根节点赋值为空 第一步判断根节点是不是空是空把节点给根节点。
第二步循环等于空就停下来key小于当前节点往左边走大于就往右走。
第三步new一块新节点数值是key的key和parent比较parent就是记录上一个节点小于和左边连接大于和右边连接。 //节点
templateclass K
struct BS_Node
{K _key;BS_NodeK* _left;//左BS_NodeK* _right;//右//构造-用于申请新节点后初始化BS_Node(const K key):_key(key),_left(nullptr),_right(nullptr){}
};templateclass K
class BStree
{typedef BS_NodeK Node;
public://插入bool insert(const K key){//根节点为空if (_root nullptr){//当前就给根节点_root new Node(key);}//parent用于记录上一个节点用来和新节点连接Node* parent nullptr;Node* cur _root;//循环到cur为空就停下来while (cur ! nullptr){//key小于当前节点往左边走if (key cur-_key){//记录上一个节点parent cur;cur cur-_left;}//key大于当前节点往右边走else if(key cur-_key){//记录上一个节点parent cur;cur cur-_right;}else{return true;}}//new一块新节点给curcur new Node(key);if (key parent-_key){//小于和左边连接parent-_left cur;}else{//大于和右边连接parent-_right cur;}return false;}private:Node* _root nullptr;
}; ⼆叉搜索树的查找 从根开始⽐较查找xx⽐根的值⼤则往右边⾛查找x⽐根值⼩则往左边⾛查找。最多查找⾼度次⾛到到空还没找到这个值不存在。如果不⽀持插⼊相等的值找到x即可返回如果⽀持插⼊相等的值意味着有多个x存在⼀般要求查找中序的第⼀个x。如下图查找3要 找到1的右孩⼦的那个3返回 当我们要查询4从根节点开始比8小往左边走比3大往右边走比6小往左走,找到4了返回true。 .从根节点开始查询 cur不等于空找到空了就说明没有这个值。
小于当前节点往左边走大于当前节点往右边走等于就返回true。 二叉搜索树中序遍历
中序遍历定义在私有里因为要从根节点开始遍历需要用到根节点中序遍历。
然后在公有定义一个成员函数来调用私有的中序遍历。 把数组的值插入到搜索二叉树中序遍历打印出来。
因为没有9所以查询不到返回false就是0。 ⼆叉搜索树的删除
⾸先查找元素是否在⼆叉搜索树中如果不存在则返回false。
如果查找元素存在则分以下四种情况分别处理假设要删除的结点为N 要删除结点N左右孩⼦均为空要删除的结点N左孩⼦位空右孩⼦结点不为空要删除的结点N右孩⼦位空左孩⼦结点不为空要删除的结点N左右孩⼦结点均不为空 对应以上四种情况的解决⽅案 把N结点的⽗亲对应孩⼦指针指向空直接删除N结点情况1可以当成2或者3处理效果是⼀样 的把N结点的⽗亲对应孩⼦指针指向N的右孩⼦直接删除N结点把N结点的⽗亲对应孩⼦指针指向N的左孩⼦直接删除N结点⽆法直接删除N结点因为N的两个孩⼦⽆处安放只能⽤替换法删除。找N左⼦树的值最⼤结点 R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N因为这两个结点中任意⼀个放到N的 位置都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转⽽变成删除R结 点R结点符合情况2或情况3可以直接删除。 节点的删除我们需要查询对应的节点然后进行删除。 cur的左节点为空的情况
如果cur的左节点为空那么parent这个父节点和cur的右节点进行连接。 如果要删除的节点是根节点那么把_root这个根节点往右走然后释放cur节点。 cur的右节点为空的情况
右节点为空那么parent这个父节点和cur的左节点进行连接。 如果要删除的节点是根节点那么把_root这个根节点往左走然后释放cur节点。 左右节点都不为空的情况
如果要删除3需要右节点的最左的那个节点的数值拿来替换。
mincur是找cur右子树最小的那个节点用来替换。
tab保存上一个节点用来和mincur的右节点连接如果右节点是空那就是连接空节点。
把4的数值赋值给3这个节点然后释放4这个节点。 如果要删除根节点需要右节点的最左的那个节点的数值拿来替换。
我们发现10的左节点已经完成空了那就是用10这个节点来替换了。 下面这个返回true是查询到要删除的节点就返回true.
找不到返回false. 二叉搜索树【实现代码】
Search for a binary tree.h【头文件】
#pragma once
#includeiostream
using namespace std;namespace key
{//节点templateclass Kstruct BS_Node{K _key;BS_NodeK* _left;//左BS_NodeK* _right;//右//构造-用于申请新节点后初始化BS_Node(const K key):_key(key), _left(nullptr), _right(nullptr){}};templateclass Kclass BStree{typedef BS_NodeK Node;public://插入bool insert(const K key){//根节点为空if (_root nullptr){//当前就给根节点_root new Node(key);}//parent用于记录上一个节点用来和新节点连接Node* parent nullptr;Node* cur _root;//循环到cur为空就停下来while (cur ! nullptr){//key小于当前节点往左边走if (key cur-_key){//记录上一个节点parent cur;cur cur-_left;}//key大于当前节点往右边走else if (key cur-_key){//记录上一个节点parent cur;cur cur-_right;}else{return true;}}//new一块新节点给curcur new Node(key);if (key parent-_key){//小于和左边连接parent-_left cur;}else{//大于和右边连接parent-_right cur;}return false;}//查询bool find(const K key){//从根节点开始查询Node* cur _root;while (cur ! nullptr){//小于当前节点往左走if (key cur-_key){cur cur-_left;}//大于当前节点往右走else if (key cur-_key){cur cur-_right;}else{return true;}}return false;}//删除bool Erase(const K key){//查找Node* cur _root;//parent用来记录上一个节点Node* parent nullptr;while (cur ! nullptr){if (key cur-_key){//parent记录上一个节点parent cur;cur cur-_left;}else if (key cur-_key){//parent记录上一个节点parent cur;cur cur-_right;}else//找到了进行删除{//当前节点的左节点为nullif (cur-_left nullptr){//*****************************//要删除的节点等于根节点if (cur _root){//让根节点往右走就行了_root cur-_right;}//*****************************else{//父节点的左节点等于curif (parent-_left cur){//cur节点的左节点为null用cur的右节点和父节点连接parent-_left cur-_right;}else{//cur节点的左节点为null用cur的右节点和父节点连接parent-_right cur-_right;}}delete cur;}//当前节点的右节点为nullelse if (cur-_right nullptr){//*****************************//要删除的节点等于根节点if (cur _root){//让根节点往右走就行了_root cur-_left;}//*****************************else{//父节点的左节点等于curif (parent-_left cur){//cur节点的右节点为null用cur的左节点和父节点连接parent-_left cur-_left;}else{//cur节点的右节点为null用cur的左节点和父节点连接parent-_right cur-_left;}}delete cur;}else//左右都不为空的情况{//找右子树最小的节点最左替代我的位置//保存cur的右节点Node* mincur cur-_right;//这个给cur,解决没有就循环就没有刷新的问题Node* tab cur;while (mincur-_left ! nullptr){//保存上一个节点tab mincur;//一直往左边节点走mincur mincur-_left;}//一直往左边节点走找到最小的那个赋值给curcur-_key mincur-_key;//删除的节点为根节点右节点为mincurif (tab-_right mincur){//tab右节点和mincur右节点进行连接tab-_right mincur-_right;}else //左节点为mincur{//tab的左边和mincur的右边进行连接tab-_left mincur-_right;}delete mincur;}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 ;_InOrder(root-_right);}Node* _root nullptr;};
}test.cpp【测试】
#includeSearch for a binary tree.hint main()
{int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };key::BStreeint t;for (auto i : a){t.insert(i);}t.InOrder();cout t.find(9) endl;for (auto i : a){t.Erase(i);t.InOrder();}} ⼆叉搜索树key和key/value使⽤场景
只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断 key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查但是不⽀持修改修改key破坏搜索树结 构了。
场景1⼩区⽆⼈值守⻋库⼩区⻋库买了⻋位的业主⻋才能进⼩区那么物业会把买了⻋位的业主的 ⻋牌号录⼊后台系统⻋辆进⼊时扫描⻋牌在不在系统中在则抬杆不在则提⽰⾮本⼩区⻋辆⽆ 法进⼊。
场景2检查⼀篇英⽂⽂章单词拼写是否正确将词库中所有单词放⼊⼆叉搜索树读取⽂章中的单 词查找是否在⼆叉搜索树中不在则波浪线标红提⽰。 key/value搜索场景
每⼀个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中(结点)除了需要存 储key还要存储对应的value增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较可以快速查 找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改但是不⽀持修改key修 改key破坏搜索树结构了可以修改value。
场景1简单中英互译字典树的结构中(结点)存储key(英⽂)和vlaue(中⽂)搜索时输⼊英⽂则同时 查找到了英⽂对应的中⽂。
场景2商场⽆⼈值守⻋库⼊⼝进场时扫描⻋牌记录⻋牌和⼊场时间出⼝离场时扫描⻋牌查 找⼊场时间⽤当前时间-⼊场时间计算出停⻋时⻓计算出停⻋费⽤缴费后抬杆⻋辆离场。
场景3统计⼀篇⽂章中单词出现的次数读取⼀个单词查找单词是否存在不存在这个说明第⼀次 出现单词1单词存在则单词对应的次数。 key/value⼆叉搜索树代码实现
Search for a binary tree.h
#pragma once
#includeiostream
using namespace std;namespace key
{//节点templateclass K,class Vstruct BS_Node{K _key;V _val;BS_NodeK,V* _left;//左BS_NodeK,V* _right;//右//构造-用于申请新节点后初始化BS_Node(const K key,const V val):_key(key),_val(val), _left(nullptr), _right(nullptr){}};templateclass K,class Vclass BStree{typedef BS_NodeK,V Node;public://插入bool insert(const K key,const Vval){//根节点为空if (_root nullptr){//当前就给根节点_root new Node(key,val);}//parent用于记录上一个节点用来和新节点连接Node* parent nullptr;Node* cur _root;//循环到cur为空就停下来while (cur ! nullptr){//key小于当前节点往左边走if (key cur-_key){//记录上一个节点parent cur;cur cur-_left;}//key大于当前节点往右边走else if (key cur-_key){//记录上一个节点parent cur;cur cur-_right;}else{return false;}}//new一块新节点给curcur new Node(key,val);if (key parent-_key){//小于和左边连接parent-_left cur;}else{//大于和右边连接parent-_right cur;}return true;}//查询Node* find(const K key){//从根节点开始查询Node* cur _root;while (cur ! nullptr){//小于当前节点往左走if (key cur-_key){cur cur-_left;}//大于当前节点往右走else if (key cur-_key){cur cur-_right;}else{//找到了返回当前节点return cur;}}//找不到返回空return nullptr;}//删除bool Erase(const K key){//查找Node* cur _root;//parent用来记录上一个节点Node* parent nullptr;while (cur ! nullptr){if (key cur-_key){//parent记录上一个节点parent cur;cur cur-_left;}else if (key cur-_key){//parent记录上一个节点parent cur;cur cur-_right;}else//找到了进行删除{//当前节点的左节点为nullif (cur-_left nullptr){//*****************************//要删除的节点等于根节点if (cur _root){//让根节点往右走就行了_root cur-_right;}//*****************************else{//父节点的左节点等于curif (parent-_left cur){//cur节点的左节点为null用cur的右节点和父节点连接parent-_left cur-_right;}else{//cur节点的左节点为null用cur的右节点和父节点连接parent-_right cur-_right;}}delete cur;}//当前节点的右节点为nullelse if (cur-_right nullptr){//*****************************//要删除的节点等于根节点if (cur _root){//让根节点往右走就行了_root cur-_left;}//*****************************else{//父节点的左节点等于curif (parent-_left cur){//cur节点的右节点为null用cur的左节点和父节点连接parent-_left cur-_left;}else{//cur节点的右节点为null用cur的左节点和父节点连接parent-_right cur-_left;}}delete cur;}else//左右都不为空的情况{//找右子树最小的节点最左替代我的位置//保存cur的右节点Node* mincur cur-_right;//这个给cur,解决没有就循环就没有刷新的问题Node* tab cur;while (mincur-_left ! nullptr){//保存上一个节点tab mincur;//一直往左边节点走mincur mincur-_left;}//一直往左边节点走找到最小的那个赋值给curcur-_key mincur-_key;//删除的节点为根节点右节点为mincurif (tab-_right mincur){//tab右节点和mincur右节点进行连接tab-_right mincur-_right;}else //左节点为mincur{//tab的左边和mincur的右边进行连接tab-_left mincur-_right;}delete mincur;}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-_val endl;_InOrder(root-_right);}Node* _root nullptr;};
}test.cpp
int main()
{string arr[] { 苹果,香蕉,香蕉,西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉,香蕉,香蕉 };key::BStreestring, int countTree;for (auto e : arr){//key_value::BSTNodestring, int* ret countTree.Find(e);auto ret countTree.find(e);if (ret nullptr){countTree.insert(e, 1);}else{ret-_val;}}countTree.InOrder();return 0;
}场景1简单中英互译字典树的结构中(结点)存储key(英⽂)和vlaue(中⽂)搜索时输⼊英⽂则同时 查找到了英⽂对应的中⽂。
//int main()
//{
// key::BStreestring, string dict;
// //BSTreestring, string copy dict;
// dict.insert(left, 左边);
// dict.insert(right, 右边);
// dict.insert(insert, 插⼊);
// dict.insert(string, 字符串);
// string str;
// while (cin str)
// {
// auto ret dict.find(str);
// if (ret)
// {
// cout - ret-_val endl;
// }
// else
// {
// cout ⽆此单词请重新输⼊ endl;
// }
// }
// return 0;
//}
