当前位置: 首页 > news >正文

从零实现数据结构:二叉搜索树

二叉搜索树概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

1. 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树

结点结构:

template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;//构造函数BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};

需要注意的是这里我们为了让后面的函数能够访问到结点内容,就直接定义成结构体了,因为结构体在c++语法中struct定义的类默认访问权限是public,所以c++为了兼容c结构体内也是可以定义函数的。注意这里的命名规则,一般默认在前面加上_或者~,这是因为为了减少在构造函数上的歧义,增加可读性。例如这里的_key如果没有_,就和传入的参数key重名了。另外这里运用了c++语法中的初始化列表,也可以简单的在函数里面相等赋值,两者本质上都是一样的。另外还需要注意的是这里我们构造函数传入的是const➕&,const是因为保护key不被意外修改,&是因为减少每次new新结点的时候调用拷贝构造函数,使用引用&可以避免复制对象,特别是当 K 是一个大型对象或复杂类型时。直接传递对象会涉及到额外的拷贝开销。

最后这里我们全程使用模板进行实现,从这篇文章开始后面的数据结构也都会用模板实现,这里给不是很了解的小朋友们解释一下,下面我们总结一下使用模板的好处:

  • 泛型编程

    • 模板允许你编写与类型无关的代码,使得同一段代码可以用于不同的数据类型。你的 BSTreeNode 结构体可以存储任何类型 K 的数据。
  • 代码复用

    • 通过模板,可以避免为每种数据类型重复编写相似的代码。你只需定义一次 BSTreeNode,然后可以用不同的类型实例化它。
    • BSTreeNode<int> intNode(10);        // 用于整数
      BSTreeNode<std::string> strNode("Hello"); // 用于字符串
      
  • 类型安全

    • 模板在编译时确定具体类型,这样可以确保类型安全。如果尝试使用不兼容的类型,编译器会报错,从而减少运行时错误。
  • 性能

    • 模板提供了高效的代码,因为它们在编译时生成特定于类型的代码,而不需要运行时类型检查。

二叉搜索树的循环实现:

插入函数:

bool Insert(const K& key) {//第一种情况如果是空直接new一个新的nodeif (_root == nullptr){_root = new node(key);return true;}//如果不为空则先找到插入位置再进行插入node* parent = nullptr;node* cur = _root;while (cur){//由于我们在最后要从父节点链接所以要记录父节点parent = cur;if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;else//这里键值相等不允许重复插入return false;}cur = new node(key);//最后还需要判断一下链接到左还是右if (parent->_key < key)parent->_right = cur;elseparent->_left = cur;return true;}

插入一个结点,分为两步走,第一步先找到结点的插入位置,这是因为这是二叉搜索树对结点的位置有要求;第二步是进行链接插入,插入的时候需要判断是左子树还是右子树。

第一步肯定还是先判空,如果空则直接new一个新的结点使其成为root结点就行。这里也可以使用原来的malloc和free,我们具体讲解一下其中的差别:不同的是new和delete还会调用构造函数和析构函数,所以针对于自定义类型还是new和delete更加好用一点,针对于常用内置类型没有什么大的区别。new和delete是用户进行动态内存申请和释放的操作符,operator new 和operator delete是系统提供的全局函数,new在底层调用operator new全局函数来进一步调用malloc申请空间,delete在底层通过operator delete全局函数来进一步调用free释放空间。所以从本质上我们也可以看到是一样的,c++在此进行了针对于面向对象的一层封装。

第二步就是找到结点的插入位置,这里的逻辑很简单,就是从根节点根据结点大小比较,往左往右一直往下走找到插入位置。需要特殊注意的是,这里我们是不允许有重复的值插入的,所以这里我们直接返回false。

第三步就是判断结点和插入位置的大小关系,从而相应地插入左右结点,最后返回true即可

查找函数:

bool Find(const K& key) {if (_root == nullptr)return false;node* cur - _root;while (cur){if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;elsereturn true;}return false;}

这里的逻辑和上面插入一样,不做过多赘述。

删除函数:

这里我们先讨论一下删除结点有几种情况,针对每一个情况分类讨论

1.叶子结点,左右孩子结点都为空,直接删除结点即可,让父节点指向空就行,如下图删除结点1:

2.该结点不是叶子结点,其孩子结点有一个为空,要么左为空要么右为空,则让父节点指向不为空的那个就行,具体分两种情况,左为空或者右为空,如下图:

        1)右为空,删除结点2,让结点3的左孩子指向1即可:

        

        12)左为空,删除结点4,让结点3的右孩子指向5即可:

        

3.左右都不为空,例如删除下面的结点5

由于这种情况很难搞复杂,所以我们就要想能不能转换成前两种情况,类似于堆里面的操作,能不能在不改变节点之间的结构的前提下交换一下。所以很自然的就有了两种方案:

方案一:找到左子树的最大节点进行交换删除

方案二:找到右子树的最小节点进行交换删除

这里可能有小朋友要问了,为什么一定是这两个节点,因为如果不是这两个原树的结构就会被破坏

选择替代节点的原因

  1. 左子树的最大节点:

    • 左子树的最大节点是左子树中最右边的节点。由于它在左子树中,它的值一定小于待删除节点的值。
    • 由于它是左子树的最大值,所有左子树的其他节点的值都小于或等于这个最大节点的值。这确保了替代后树的性质仍然成立。
  2. 右子树的最小节点:

    • 右子树的最小节点是右子树中最左边的节点。它的值一定大于待删除节点的值。
    • 由于它是右子树的最小值,所有右子树的其他节点的值都大于或等于这个最小节点的值。这同样保证了替代后树的性质仍然成立。

所以这里可以找左子树节点3和右子树节点6进行替换删除,如下图:

最后给出实现:

else
{// 1. 找到右子树的最小节点Node* Minright = cur->_right;Node* parent = cur;// 检查右子树的最小节点是否直接是右孩子if (!Minright->_left) {// 如果右孩子本身就是最小节点,直接替换cur->_key = Minright->_key;cur->_right = Minright->_right;  // 更新右子树} else {// 否则,在右子树中继续查找最小节点while (Minright->_left) {parent = Minright;Minright = Minright->_left;}// 替换当前节点的值为右子树最小节点的值cur->_key = Minright->_key;// 更新 parent 的指针parent->_left = Minright->_right;}// 删除最小节点delete Minright;
}

这里唯一需要注意的一点就是,有两种可能性,一种右子树的最小节点就是右孩子如下图:

      8/ \3   10/ \    \1   6    14/ \   /4   7 13

我们删除节点8,右子树最小节点直接就是10了,这是我们的parent指向cur也就是8,也就是说我们的parent的右节点是minright,这时需要拿出来单独讨论,其余情况由于while循环是往左边一直走的 ,所以最小节点一定出现在左边。给出完整的删除实现:

	bool Erase(const K& key) {if (_root == nullptr)return false;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//找到相等,开始执行删除逻辑{//1.左为空if (cur->_left == nullptr){//这里需要单独判断是否为根节点if (cur == _root)_root = cur->_right;else {if (parent->_left == cur)parent->_left = cur->_right;else if (parent->_right == cur)parent->_right = cur->_right;delete cur;}}//2.右为空else if (cur->_right == nullptr){if (cur == _root)_root = cur->_left;else{if (parent->_left == cur){parent->_left = cur->_left;}else if (parent->_right == cur){parent->_right = cur->_left;}delete cur;}}else{// 1. 找到右子树的最小节点Node* Minright = cur->_right;Node* parent = cur;// 检查右子树的最小节点是否直接是右孩子if (!Minright->_left) {// 如果右孩子本身就是最小节点,直接替换cur->_key = Minright->_key;cur->_right = Minright->_right;  // 更新右子树}else {// 否则,在右子树中继续查找最小节点while (Minright->_left) {parent = Minright;Minright = Minright->_left;}// 替换当前节点的值为右子树最小节点的值cur->_key = Minright->_key;// 更新 parent 的指针parent->_left = Minright->_right;}// 删除最小节点delete Minright;}return true;}}return false;}

二叉搜索树的递归实现

递归还是分治的思想,分别递归左子树右子树就可以了。唯一需要注意的是这里我们讲根节点设置成了私有变量,在public里面的函数实现无法获取私有变量。所以这里可以套一层private里面的函数就可以拿到root。其实这里大可以不用这么麻烦,自己练习写的时候可以直接全部共有都行,但是养成好习惯最好。

查找函数:

bool FindR(const K& key){return _FindR(_root, key);}
private:node* _root = nullptr;bool _FindR(node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key)return _FindR(root->_right, key);else if (root->_key > key)return _Findr(root->_left, key);elsereturn true;}

插入函数:

bool _InsertR(node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key)return _InsertR(root->_right, key);else if (root->_key > key)return _InsertR(root->_left, _key);elsereturn false;}

这里需要注意的是如果不传入root的引用是无法链接的,只能完成new的部分但是缺少链接。

  • Node*& root 是一个引用:

    • Node*& root 表示 root 是一个指向 Node 指针的引用。
    • 因为它是引用,所以对 root 的任何修改(包括 root = new Node(key);)都会反映到调用函数中的原始指针上。
  • 递归插入新节点:

    • 当我们递归调用 _InsertR(root->_right, key)_InsertR(root->_left, key) 时,传入的 root->_rightroot->_left 也是以引用的方式传入。
    • 如果递归中某一层发现 root == nullptr,则 root = new Node(key); 将会分配一个新节点,并将新节点的指针赋给当前 root
    • 因为 root 是引用,这样赋值之后,调用函数中的 root->_leftroot->_right 指针会自动指向这个新节点,实现了节点的链接

如果不使用这种方法,则需要手动的再用一个parent保存父节点,那就又回到了循环的实现方式。

删除函数:

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* cur = root;//左为空if (root->_left == nullptr){root = root->_right;}//右为空else if (root->_right == nullptr){root = root->_left;}//左右都不为空else{Node* Minright = root->_right;while (Minright->_left){Minright = Minright->_left;}swap(root->_key, Minright->_key);return _EraseR(root->_right, key);}delete cur;return true;}}

至此两种实现方式都完成了,接下来就是avl树和红黑树了!


http://www.mrgr.cn/news/62702.html

相关文章:

  • LINUX总线-设备-驱动匹配
  • 基于物联网设计的地下煤矿安全监测与预警
  • clickhouse运维篇(二):多机器手动部署ck集群
  • git入门教程16:git简明教程,一篇够了
  • SQL 高级技巧
  • 建站的流程解析分享
  • 【HTML5标准】深度解析HTML5:前端开发的基石
  • 【深度学习】VITS语音合成原理解析
  • 向量库Milvus异常挂了,重新启动
  • 有没有优质的公司可以提供高质量大模型数据?
  • Vue.js(2) 基础:指令与功能概览
  • C++对象模型:Function 语意学
  • 九泰智库 | 医械周刊- Vol.65 | 广州发布首批创新药械产品目录
  • 【产品经理】工业互联网企业上市之路
  • 【2024.10.31练习】123
  • 二分查找题目:搜索插入位置
  • 沈阳工业大学《2021年+2020年827自动控制原理真题》 (完整版)
  • Java - 手写识别; 如何用spring ai和大模型做手写识别教程
  • 监控pod日志
  • 集成学习(2)
  • Ethernet 系列(5)-- 物理层测试::PMA Test::MDI
  • 江协科技STM32学习- P28 USART串口数据包
  • 《暗河传》 顺利杀青,苏棋演绎“千面鬼”慕婴引期待
  • 微软办公三件套入局,苹果接力功能再升级!如何进一步提高跨平台协作效率?
  • 【C++】C++17结构化绑定、std::optional、std::variant、std::any
  • Vue全栈开发旅游网项目(3)-Vue路由配置