C++ 二叉搜索树

🕗 发布于 2025-01-22 15:49 算法 c++ 数据结构 开发语言

概念

性能分析

二叉搜索树的插入

概念

对于一个二叉搜索树

若它的左子树不为空，则左子树上所有的节点的值都小于等于根节点的值
若它的右子树不为空，则右字数上所有的节点的值都大于等于根节点的值
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景

template<class K,class V>
struct BSTreeNode
{
typedef BSTreeNode<K, V> Node;
BSTreeNode(const K& key,const V& val):_key(key),_value(val){}
K _key;
V _value;
Node* _left = nullptr;
Node* _right = nullptr;
};

性能分析

指出二叉搜索树：

最优情况下，二叉搜索树近似为完全二叉树，高度为 $\log_{2} N$
最差情况下，二叉搜索树退化为类似于单支树，高度为 $N$
最优情况下增删查改为 $O\left ( log_{2}N\right )$
最差情况下增删查改为 $O\left ( {N} \right )$
综合来讲时间复杂度为 $O\left ( N \right )$

指出二分查找：

二分查找需要在允许下标随机访问的结构中
二分查找需要在有序的结构中
二分查找的时间复杂度为 $O\left ( log_{2}N \right )$
二分查找对应的结构一般为数组，它挪动数据的时间复杂

二叉搜索树的插入

树为空，直接增新节点，赋值给root指针
树不为空，按照性质，插入值比当前节点大走右边，反之走左边，插入空位置
如果支持插入相等的值可以插左边或者右边（但是插左边就都插左边，反之相同）

int num[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
else
{
bool right = true;
Node* p = _root;
Node* c = _root;
while (c != nullptr)
{
p = c;
if (key > c->_key)
{
right = true;
c = p->_right;
}
else if(key < c->_key)
{
right = false;
c = p->_left;
}
else
{
return false;
}
}
c = new Node(key, value);
if (right)
{
p->_right = c;
}
else
{
p->_left = c;
}
return true;
}
}

二叉树的查找

从根开始查找，key比节点大就走右，比节点小就走左边
最多查找高度次数，走到空还没找到就不存在
不支持插入相等的值，找到x就返回，反之继续查找直到高度次

Node* Find(const K& key,Node** p = nullptr)
{
Node* ptr = _root;
while (ptr)
{
if (key > ptr->_key)
{
if (p)*p = ptr;
ptr = ptr->_right;
}
else if (key < ptr->_key)
{
if (p)*p = ptr;
ptr = ptr->_left;
}
else
return ptr;
}
return ptr;
}

二叉树的前序遍历

采用递归
打印左边节点
打印中间节点
打印右边节点

void _InOrder(Node* root) 
{
if (root == nullptr) 
return;

_InOrder(root->_left);
cout << root->_key << '{' << root->_value << '}' << ' ';
_InOrder(root->_right);
}

二叉搜索树的删除（重点）

先查找是否存在，不存在返回false
若存在有以下四种情况
删除节点的左右孩子均为空
直接删除然后给空

删除节点的左（右）孩子为空，另一边不为空
把节点的父亲对应的孩子节点的指针指向孩子不为空的一边，然后删除节点

删除节点左右均不为空
找左子树的最大节点（右子树的最小节点）替代删除节点，，然后删除最值节点

bool Erase(const K& key)
{
Node* par = _root;
Node* ptr = Find(key,&par);
if (!ptr)return false;
if (ptr == par)
{
delete ptr;
_root = nullptr;
return true;
}
if(!ptr->_left&&!ptr->_right)
{
if(par->_left == ptr)
par->_left = nullptr;
if(par->_right == ptr)
par->_right = nullptr;

delete ptr;
return true;
}
else if (!ptr->_left && ptr->_right)//左空右不空
{
if (par->_left == ptr)
{
par->_left = ptr->_right;
}
if (par->_right == ptr)
{
par->_right = ptr->_right;
}
delete ptr;
return true;
}
else if(ptr->_left && !ptr->_right)
{
if (par->_left == ptr)
{
par->_left = ptr->_left;
}
if (par->_right == ptr)
{
par->_right = ptr->_left;
}
delete ptr;
return true;
}
else//两边均不为空直接替换操作
{
//找左侧最大节点
Node* Max = ptr->_left;
Node* Maxp = ptr;
while (Max->_right != nullptr)
{
Maxp = Max;
Max = Max->_right;
}
//交换
ptr->_key = Max->_key;
ptr->_value = Max->_value;

//删除MAX的位置
if (Maxp == ptr)
{
ptr->_left = Max->_left;
}
else if (Max->_left)
{
Maxp->_right = Max->_left;
}
else
{
Maxp->_right = Max->_right;
}
//删除Max
delete Max;
return true;
}



return false;
}

完整代码

#pragma once
#include<iostream>
#include<string>
using namespace std;

template<class K,class V>
struct BSTreeNode
{
public:
typedef BSTreeNode<K, V> Node;
BSTreeNode(const K& key,const V& val):_key(key),_value(val){}
K _key;
V _value;
Node* _left = nullptr;
Node* _right = nullptr;
};

template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value) 
{
if (_root == nullptr) 
{
_root = new Node(key, value);
return true;
}
else 
{
bool right = true;
Node* p = _root;
Node* c = _root;
while (c != nullptr) 
{
p = c;
if (key > c->_key) 
{
right = true;
c = p->_right;
}
else if (key < c->_key)
{
right = false;
c = p->_left;
}
else
{
return false;
}
}
c = new Node(key, value);
if (right)
{
p->_right = c;
}
else
{
p->_left = c;
}
return true;
}
}
Node* Find(const K& key,Node** p = nullptr)
{
Node* ptr = _root;
while (ptr)
{
if (key > ptr->_key)
{
if (p)*p = ptr;
ptr = ptr->_right;
}
else if (key < ptr->_key)
{
if (p)*p = ptr;
ptr = ptr->_left;
}
else
return ptr;
}
return ptr;
}
bool Erase(const K& key)
{
Node* par = _root;
Node* ptr = Find(key,&par);
if (!ptr)return false;
if (ptr == par)
{
delete ptr;
_root = nullptr;
return true;
}
if(!ptr->_left&&!ptr->_right)
{
if(par->_left == ptr)
par->_left = nullptr;
if(par->_right == ptr)
par->_right = nullptr;

delete ptr;
return true;
}
else if (!ptr->_left && ptr->_right)//左空右不空
{
if (par->_left == ptr)
{
par->_left = ptr->_right;
}
if (par->_right == ptr)
{
par->_right = ptr->_right;
}
delete ptr;
return true;
}
else if(ptr->_left && !ptr->_right)
{
if (par->_left == ptr)
{
par->_left = ptr->_left;
}
if (par->_right == ptr)
{
par->_right = ptr->_left;
}
delete ptr;
return true;
}
else//两边均不为空直接替换操作
{
//找左侧最大节点
Node* Max = ptr->_left;
Node* Maxp = ptr;
while (Max->_right != nullptr)
{
Maxp = Max;
Max = Max->_right;
}
//交换
ptr->_key = Max->_key;
ptr->_value = Max->_value;

//删除MAX的位置
if (Maxp == ptr)
{
ptr->_left = Max->_left;
}
else if (Max->_left)
{
Maxp->_right = Max->_left;
}
else
{
Maxp->_right = Max->_right;
}
//删除Max
delete Max;
return true;
}



return false;
}
void InOrder(){_InOrder(_root);}
private:
void _InOrder(Node* root) 
{
if (root == nullptr) 
return;

_InOrder(root->_left);
cout << root->_key << '{' << root->_value << '}' << ' ';
_InOrder(root->_right);
}
Node* _root = nullptr;
};

key与value的使用

void TestBSTree()
{
BSTree<string, string> dict;
dict.Insert("insert", "插入");
dict.Insert("erase", "删除");
dict.Insert("left", "左边");
dict.Insert("string", "字符串");

string str;
while (cin >> str)
{
auto ret = dict.Find(str);
if (ret)
{
cout << str << ":" << ret->_value << endl;
}
else
{
cout << "单词拼写错误" << endl;
}
}

//string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
 统计水果出现的次
//BSTree<string, int> countTree;
//for (auto str : strs)
//{
//auto ret = countTree.Find(str);
//if (ret == NULL)
//{
//countTree.Insert(str, 1);
//}
//else
//{
//ret->_value++;
//}
//}
//countTree.InOrder();
}

原文地址：https://blog.csdn.net/forccct/article/details/145269768

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：个人学习 - 什么是Vim?
下一篇：数据结构与算法之递归: LeetCode 79. 单词搜索 (Ts 版)

docker部署的gitlab迁移
生活中总是充满了各种选择，点餐纠结，出行选择，聚餐座位，团队投票结果不明，随机抽签一锤定音等等！为了解决这个问题，我开发了一款【随机选择决定转盘工具】无论是随机抽选还是投硬币，都能轻松搞定。现在通过微
阅读更多2025-01-22
网络流量测量
网络测量对于网络运营、拥塞控制、负载均衡和异常检测等至关重要。其中，大流检测是网络测量的关键任务之一，它记录流的大小和ID（通常由5元组或源/目的IP地址组成）。
阅读更多2025-01-22
自动化标注平台开源，基于 yolov8标注平台可本地部署
一款开源的数据标注工具，具有以下特点：支持多种数据类型：支持文本、图像、音频、视频等多种数据类型的标注，适用于自然语言处理、图像识别、语音识别等多种应用场景。灵活易用：用户可以根据项目需求自定义标注界
阅读更多2025-01-22
Linux：进程地址空间、进程控制（一.进程创建、进程终止、进程等待）
1. 字符串常量字符串常量通常存储在高地址，其地址是固定的，不可更改。字符串的下标从0到n一直在增加，即字符串中的每个字符在内存中是连续存储的。2. main函数地址main函数地址通常是程序中最底部
阅读更多2025-01-22
【优选算法】Binary-Blade：二分查找的算法刃（下）
本篇接上一篇二分查找，主要通过部分题目熟悉二分查找的进阶使用，重点强调二段性，找到两个区间不同的地方在哪，多画图划分界限
阅读更多2025-01-22
最新D音滑块JS纯算法还原（含完整源码）
通过JS逆向分析对JS算法进行还原的方式通过滑块验证码
阅读更多2025-01-22
数据结构(全)
线性结构, 树形结构, 图结构, 排序, 查找, 数据结构, 算法
阅读更多2025-01-22
【初阶数据结构与算法】八大排序算法之交换排序（冒泡排序，快速排序---hoare、挖坑法、lomuto双指针3种版本）
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序
阅读更多2025-01-22
Java-数据结构-时间和空间复杂度
在了解时间复杂度和空间复杂度之前，我们先要知道为何有这两者的概念首先我们要先了解"算法"，在之前我们学习过关于"一维前缀和与差分""二维前缀和与差分&
阅读更多2025-01-22
通俗理解正交匹配追踪（OMP）算法及MATLAB代码实现
【OTFS数学知识补充1】通俗理解正交匹配追踪（OMP）算法及MATLAB代码实现
阅读更多2025-01-22

C++ 二叉搜索树

概念

性能分析

二叉搜索树的插入

二叉树的查找

二叉树的前序遍历

二叉搜索树的删除（重点）

完整代码

key与value的使用

相关文章