二叉搜索树倒序O(nlogn)建树
2024-09-05 15:15:27
由于在某些糟糕情况下,二叉查找树会退化成链,故而朴素建树过程其复杂度可能会退化成\(O(n^2)\)。
采用倒序连边建树的方法可以使得二叉查找树建树复杂度稳定在\(O(nlogn)\).
具体思路如下:
把待建树的序列\(a_1,a_2,a_3,a_4..a_n\)\(排序,对于每一个\)\(a_i\)求得其在排序后的序列中的前驱pre和后继suc.
倒序遍历序列\(a_n\),对于\(a_i\),其一定是其前驱与后继之中的某个的儿子,如果前驱在序列\(a_n\)比后继靠后(出现的晚),那么ai是前驱的儿子,反之是后继的儿子。//仔细想想,为什么?
更新对应的前驱或后继,并且删除掉\(a_i\)
对于第二点,可以理解为建树的过程是把区间不断更新成左右子树的过程。那么对于某一个插入,假设点插入了
区间[pre+1,suc-1],那么[pre+1,point-1]为左子树,[point+1,suc-1]为右子树。也就是说区间是谁的子树,要看区间端点谁最后出现。
所以一个二叉查找树一个很重要的性质是:对于每一次插入的结点,其要么是最小的比它大的结点的儿子,要么是最大的比它小的结点的儿子。
根据这个性质,可以通过树状数组同样完成\(O(nlog^2n)\)建树。
我们已经知道对于每次插入,我们只需要知道所要插入的点要落在哪个区间,即落在哪两个点之间。
所以通过树状数组维护前缀和(目的是求插入的点是当前第几大),假设当前的点是第k大,二分查询树状数组
分别查询出第k-1大对应的位置和第k+1大对应的位置,然后比较这两个位置谁晚出现,即可。
最新文章
- CSS如何实现数字分页效果
- 常用oracle查询总结
- oracle命令行操作
- Android图片框架---Glide
- java学习笔记 --- 方法
- 关于JDK和eclipse的安装和汉化
- HBase flush
- Beta项目总结
- MVC 5 Scaffolder + EntityFramework+UnitOfWork Pattern 代码生成工具
- Zookeeper 源码学习(一)环境搭建
- Oralce SQLPlus 以及shell脚本中spool输出到文件时的格式化输出
- Python之logging日志模块
- 快速切题 poj1258
- GEOquery
- python随笔(二)
- 数字签名算法(C#)
- TP3.2实例化复杂模型类
- 4 MySQL--表(增删改查)
- js节点操作实例
- Python基础、条件语句和基本数据类型