网站建设的基本步骤,广州花都网站建设,在网站上显示备案信息,浅谈网站页面框架设计文章目录二叉搜索树模拟实现InsertInsertR()EraseEraseR搜索树的价值实现代码二叉搜索树
在二叉树的基础之上, 左子树的值都比根节点小#xff0c;右子树都更大。那么他的左右子树也分别叫做二叉搜索树。 查找一个节点,最多查找高度次(建立在这个树是比较均衡的).10亿里面找…
文章目录二叉搜索树模拟实现InsertInsertR()EraseEraseR搜索树的价值实现代码二叉搜索树
在二叉树的基础之上, 左子树的值都比根节点小右子树都更大。那么他的左右子树也分别叫做二叉搜索树。 查找一个节点,最多查找高度次(建立在这个树是比较均衡的).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,和红黑树就可以实现了二号擦搜索树的调整使它的性能达到最优。
实现代码
