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

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

news 2024/10/31 20:17:51

二叉搜索树概念

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

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->_right 或 root->_left 也是以引用的方式传入。
    • 如果递归中某一层发现 root == nullptr，则 root = new Node(key); 将会分配一个新节点，并将新节点的指针赋给当前 root。
    • 因为 root 是引用，这样赋值之后，调用函数中的 root->_left 或 root->_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路由配置