搜索二叉树

二叉搜索树

在二叉树的基础之上,

• 左子树的值都比根节点小，右子树都更大。那么他的左右子树也分别叫做二叉搜索树。

• 查找一个节点,最多查找高度次(建立在这个树是比较均衡的).10亿里面找30次就行，log2^30,如果是满二叉树或者完全二叉树.

• 如果是单支的,查找的时候O(N)是最坏情况,所以是不成熟的.进而升级为平衡搜索二叉树即AVLTree,RBTree(红黑树)。

子函数调用中序，避免传参的时候无法调用到私有的root。

模拟实现

Insert

• 搜索树默认是不允许存在重复值，会去重，只留下来一个。所以返回值设置为bool.
• 数值对比寻找位置时,还需要记录父亲节点便于后续节点连接.

InsertR()

最后将4与3连接起来,是因为在最后一次递归中,root恰好是3右孩子指针的别名,所以开创节点之后,就可以直接连接起来.

Erase

搜索二叉树的删除三种情况:

• 删除叶子结点，注意父亲节点的右指针置空，别造成野指针。

• 删除有一个子节点的：子承父业，将儿子交给你爹。

• 前两种可以当成一个,一定要分清楚情况：如果我是父亲的左，让父亲的左指向我的右。

• 删除根节点这种有两个孩子节点的:替换法删除，找一个比左子树大 ,比右子树小的节点，进行交换删除就行。

  • 左子树的最右节点，左子树的最左节点
    • 仍然需要记录父亲节点,因为可能最左节点还有右孩子需要连接

• 如果父亲是空呢？根节点，移动根节点吧！

EraseR

从5开始,要删除8.别名的使用,直接连接就行.

• 删除一个或者没有孩子节点的节点

• 删除两个孩子的节点

  

搜索树的价值

搜索分为key搜索模型+key-value模型

• key搜索模型：简单的判断在还是不在
  比如是门禁系统：搜索树存储学生的学号。

• 给你一篇英语作文，检查一下作文中单词拼写是否都正确？一种方法就是词库中的单词都放在搜索树中，进行判断就行。
  key-value模型通过一个值查找另一个值

  • 中英字典互译

  • 高铁站刷身份证进站：身份证上没有票的信息，通过身份证找到买票信息
    人脸是别再加一层key-value 模型。实现K-V模型只需要将K模型中多添加一个模板参数Value.

  • 统计水果出现次数，统计单词出现的次数。

排序 + 去重：插入俩的一样额就会自动删除一个就是没插入进去.

满二叉搜索树的效率是log2 N.但是在最差的情况下回退化为单边树，效率大大降低O(N)

给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的
二叉搜索树遍历一遍，就可以得到一个有序序列，因此，时间复杂度为O(N).

如果退化成单只树，二叉搜索树的性能就失去了。后续的AVL,和红黑树就可以实现了二号擦搜索树的调整使它的性能达到最优。

实现代码