type
status
summary
date
slug
tags
category
icon
password
1.搜索二叉树（SearchBinaryTree）
搜索二叉树，常用于map中，搜索二叉树严格遵循左小右大的原则，左儿子永远小于父亲，右儿子永远大于父亲
想要读懂本文章需要有一定的数据结构基础如链表，堆等
2.搜索二叉树的实现
- 插入（insert）
下图是一个简易的搜索二叉树，可以看出来搜索二叉树是严格遵循着左小右大的基本原则的
想要在搜索二叉树中插入元素同样也要遵循这个基本原则
接下来就用C++代码实现一下插入
在搜索二叉树中插入是最为简单的，但是其实也是最为重要的一部分因为当你写完插入过后就能快速的建立起来一个搜索二叉树
这里用到了一个C++中很常用也非常好用的一个语法糖for循环（用迭代器实现）
2.删除（erase）
删除其实是搜索二叉树中最难的部分，因为当你在删除某个节点的时候你需要先查找，然后在选择到底哪一个节点在代替原来的父亲节点
这里有三种情况
- 要删除的节点本身就是叶子节点（没有子节点的节点就叫叶子节点），那么直接删除
- 如果要删除的节点只有一个子节点那么该子节点代替他的父亲节点
- 如果要删除的节点既有左孩子又有右孩子那么使用左树最大节点或者右树最小节点来替换要删除的节点
接下来用c++代码演示一下查找
通过查找函数能更方便的编写后续的删除
整体的实现
这里我有一点想说的就是在二叉树中插入修改和删除难免会出现使用双指针问题，但是在使用C++过后这里就有办法解决了就是在形参注入的时候取引用，这个时候就不用使用双指针就能解决问题如下代码在删除遇到有一个子节点时候，将那个子节点替换为父亲节的时候,正常情况下，不是引用我们拿到的地址不能将父亲left指向下一个元素，但是如果是父亲left引用就能使用root = root→left；还有一点要提的是这里分三种情况来分类设计删除
3.搜索二叉树实际的性能分析
搜索二叉树的性能其实很不稳定，因为如果里面存放的数据是一个连续增大或者连续减少的数组那么他的时间复杂度就是O（N）如果他存放的数据能让他构成一个完全二叉树那么他的时间复杂度就是O（log N）
对比有序数组二分查找与搜索二叉树来说前者插入和删除效率太低后者插入删除查找等功能都非常不错
- Author:PytC
- URL:https://PytC.fun//article/fff49b4c-fd33-8133-9f4f-e52530e2eae6
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!