划分树(算法总结)_第1页
划分树(算法总结)_第2页
划分树(算法总结)_第3页
划分树(算法总结)_第4页
划分树(算法总结)_第5页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、用来标记和中间值相等的，且分到左孩子的数的个数。动态求解区间最大数的问题揭开它神秘的面纱，探寻真理的奥妙。小志。这偏文章主要总结划分树解决区间第K大数的问题。一些内容并非原创，全部内容只供参考交流！划分树划分树的定义划分树定义为，她的每一个节点保存区间所有元素，元素排列顺序与原数组（输入）相同，但是，两个子树的元素为该节点所有元素排序后-个进入左子树，其余的到右子树，同时维护一个num域，表示t这些点有多少进入了左子树。（摘自某牛人的博客，为了和下面的算法统一，稍有变动）划分树的Sample.如果由下而上看这个图，我们就会发现他和归并排序的（归并树）的过程很类似，或者说正好相反。归并树是由下而

2、上的排序，而她确实由上而下的排序（观察4的运动轨迹，我们可以猜到划分树的排序也是一种稳定的排序方法，这里不是说明的重点，不予证明）。但这正是她可以用来解决第k大元素的理由所在。（具体的理由，写完再补）扌非序后原数组丄6旦4曼2巳冬|空呼0划分树的存储结构（采用层次存储结构（由下而上，由左到右，每层两个孩子，见上图）对原来集合中的元素排序后的值。记录第层当前位置的元素的值记录元素所在区间的当前位置之前进入左孩子的个数记录比当前元素小的元素的和。划分树的建立Build划分树的建立和普通的二叉树的建立过程差不多，仍然采取中序的过程（先根节点，然后左右孩子）。树的建立相对比较简单，我们依据的是已经排好

3、序的位置进行建树，所以先用快排将原集合牌还序。要维护每个节点的num域。LBoy_ 初始时，假定当前区间有个和相等。先踢掉比中间值小的剩下的就是要插入到左边的初始一个子树。初始区间下一个节点。如果大于，肯定进入右孩子，否则，判断是否还有相等的应该进入左孩子的,没有，就直接进入右孩子，否则进入左孩子，同时更新节点的域和域LBoy_ #LBoy_ 划分树的查找在区间上查找第k大的元素,1.2.3.同时返回她的位置和去见里面小于a,b的所有数的和。二，即，进入p的左孩子的个数已经超过k个，那么就往左孩子里Iftt,曲即，进入p的左孩子的个数小于k个，那么就要往右孩子查找如果面查找，同时更新如果第ks（s表示进入左孩子的个数）个元素。同时要更新sun域。详细的过程见代码和注释：在区间上查找第大元素，同时返回区间中小于第大元素的和。LBoy_ #LBoy_ #到达叶子就找到该元素，返回。LBoy_ 记录区间中进入左孩子的元素的个数。记录区间中计入左孩子的元素的个数。记录区间中小于第大元素的值的和。表示中分到右孩子的个数表示中分到右孩子的个数。区间端点点重合的情况不一定为，所以要单独考虑进入左孩子，同时更新区间端点值。划分树的应用pku_2401_K-thNumberhdu_2

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论