划分树详解——求解整数区间内第K大的值——python3实现

约定不等于承诺〃 2022-05-22 11:47 105阅读 0赞

本文题目与代码参考来自[程序设计解题策略][Link 1]。

*  题目重述
 *  划分树原理
 *  划分树介绍
 *  划分树实际存储
 *  划分树查找原理
    
     *  实际例子1：递归到左
     *  实际例子2：递归到右
 *  划分树——建树
 *  划分树——查询

# 题目重述 #

题目重述：给定一个数组num = \[1,5,2,3,6,4,7,3,0,0\]，求出在索引\[x,y\]之间第K大的值。  
比如，求\[1,3\]中第2大的值。索引\[1,3\]对应的子数组为\[5,2,3\]，第2大的值，也是将\[5,2,3\]排序，排序后为\[2,3,5\],那么\[2,3,5\]排第二的值为3，所以这里返回3.  
注意：第K大的值，其实是指排序后，第k个值。k为>=1的整数，且k不能超过\[1,3\]的长度，因为超过就没有意义了。

# 划分树原理 #

划分树是一种基于[线段树][Link 2]的数据结构，建议可以先了解一下线段树，便于理解本文。基本思想为：将待查找区间划分为两个子区间。不大于数列中间值的元素被分配到左孩子的子区间，简称左子区间；大于数列中间值的元素被分配到右儿子的子区间，简称右子区间。  
有以下成立：

*  左子区间的数<=右子区间的数
 *  建树时，需保证分到同一子节点的元素之间的相对顺序不变
 *  数列含n个整数，对应划分树为![这里写图片描述][20180623163630191]层

例如，题目的整数序列排序后得到\[ 0 0 1 2 3 4 5 6 7 \]，中间值为3.划分出下一层的左子区间\[ 1 2 3 0 0 \]，中间值为1；下一层的右子区间为\[ 5 6 4 7 3 \]，中间值为5；以此类推，直到划分出的所有子区间含单个整数为止。

查找：通过记录下来进入左子区间的数的个数，确定下一个查找的子区间，直到查找范围缩小到单元素区间为止。此时，\[x,y\]之间第K大的值就被找到了。

# 划分树介绍 #

题目数组为\[1,5,2,3,6,4,7,3,0,0\]，对应划分树结构如下：  
![这里写图片描述][70]  
第一步是建树，过程如下：  
首先是通过对原数列排序找到这个区间的中间位置的值mid（mid=(left+right)/2，mid指索引，而中间值指索引为mid的那个数），不大于中间值的数划入左子区间\[left,mid\]，大于中间值的数划入右子区间\[mid+1,right\]。同时，对于第i个数（i是索引，从0开始哦），记录在\[left,i\]区间内有多少数被划入左子区间。  
然后继续对它的左子区间\[left,mid\]和右子区间\[mid+1,right\]递归建树，直到划分出最后一层的叶子节点为止。

# 划分树实际存储 #

实际划分树是由两个二维数组来存储的。  
tree\[dep\]\[i\]——树中第dep层中第i位置的数  
toleft\[dep\]\[i\]——代表第dep层中，从0位置到i位置有多少个数分入下一层的左子区间。  
说了这么多，你可能还是不知道，到底划分树是怎么用的，看如下例子。  
划分树结构：  
![这里写图片描述][70]  
tree二维数组：  
![这里写图片描述][20180623180408835]  
toleft二维数组：  
![这里写图片描述][20180623180534143]  
根据题目给的num数组，tree和toleft的实际存储如上。具体分析如下：  
1.划分树：  
以第0层为例，带方框的数代表这个数到达第1层是被划分到左子区间，不带方框则划分到右子区间。  
2.tree二维数组：

*  每一行是一个一维数组，而且tree\[0\]代表的就是第0层的数，而且顺序一样
 *  每个一维数组的长度是num的长度
 *  树是0-4层，所以tree也是从tree\[0\]到tree\[4\]
 *  树中最后一层只存了4个数，所以另外6个位置没有用，浪费了，但不得不浪费。False代表该位置没有存数

3.toleft二维数组：

*  每一行是一个一维数组，每个一维数组的长度是num的长度
 *  toleft\[0\]\[i\]代表的是tree\[0\]\[0\]到tree\[0\]\[i\]中，有几个数会被划分到下一层的左子区间
 *  第0层为例，从tree\[0\]\[0\]到tree\[0\]\[0\]有tree\[0\]\[0\]即1这一个数被划分到了左子区间，所以toleft\[0\]\[0\]为1
 *  从tree\[0\]\[0\]到tree\[0\]\[1\]只有tree\[0\]\[0\]即1这一个数被划分到了左子区间，所以toleft\[0\]\[1\]为1
 *  从tree\[0\]\[0\]到tree\[0\]\[2\]有tree\[0\]\[0\]即1、tree\[0\]\[2\]即2这两个数被划分到了左子区间，所以toleft\[0\]\[2\]为2
 *  toleft\[dep\]\[i\]的值是从树中每个节点开始算的，比如看toleft\[1\]是\[1, 1, 1, 2, 3, 1, 1, 2, 2, 3\]，是因为树中，第1层中是两个节点，每个节点各五个数，所以前5个算完，又得从新算有多少个数被划分进左子区间
 *  如果层中有的数已经是叶子节点，那么就不存，即存False来代表没有实际意义
 *  树有5层，但toleft只有4层，因为最后一层全是叶子节点，全存False那还不如不存了

私认为一篇讲解划分树的博客，如果不给出tree和toleft二维数组的实际存储，那都是在耍流氓==。

# 划分树查找原理 #

L=0，R=len(num)-1。即为最小和最大索引。  
给定L<=left，right<=R，考虑一般情况，即left和right不在最小最大索引（为了方便理解分析），那么现在整个区间被分了三个区间：  
\[L,left-1\],\[left,right\],\[right+1,R\]。分别称为靠左区间，查询区间，靠右区间。这三个区间合起来就是第0层，以\[某区间\].left代表分到左子区间的数的序列，\[某区间\].right代表分到右子区间的数的序列。  
那么第1层的左子区间肯定是由\[L,left-1\].left \[left,right\].left \[right+1,R\].left依次组成的。  
第1层的右子区间肯定是由\[L,left-1\].right \[left,right\].right \[right+1,R\].right依次组成的。  
理解上面这几段话非常重要！  
分析：

*  \[L,R\].left=\[L,left-1\].left + \[left,right\].left + \[right+1,R\].left
 *  \[L,R\]分到左子区间的数，肯定是\[L,R\]拆分成的小区间分到左子区间的数合起来
 *  因为划分树保证了从区间划分到子区间时，保持子区间内相对顺序不变，所以上面说是依次组成  
    ![这里写图片描述][70]

## 实际例子1：递归到左 ##

L=0，R=9，left=1，right=3，k=2  
寻找\[1,3\]区间中，大小排序第2的数？该区间为\[5,2,3\]，第2大的数为3，这里我们最终就会找到3。  
首先分析第一层，\[0,9\]被\[1,3\]分成了三个小区间，\[0,0\] \[1,3\] \[4,9\]，靠左区间分到左子区间的数的个数为1，查询区间分到左子区间的数的个数为2，靠右区间这里不用分析。  
既然查询区间分到左子区间的数的个数cnt为2，k为2（k即想找到的第几个数），有k<=cnt，那么这第k个数肯定被分到左子区间了，实际情况也为如此，\[1,3\]区间代表的\[5,2,3\]中的\[2,3\]被分到左子区间，而\[5\]被分到右子区间。  
接下来要分析到第二层（递归到左），但之前要提供新的L，R，left，right（新的left，right即为\[1,3\].left的最小最大索引）。  
因为到左子区间，L不变，R=(L+R)/2 。  
因为左子区间是由\[0,0\].left \[1,3\].left \[4,9\].left依次组成的，已经知道\[0,0\].left的长度为1（上上段已说），且它们三是依次组成，所以新的left是新的L+1即0+1=1。  
而新的\[left,right\]的长度即为cnt，因为想找的数不是在\[1,3\].left就是在\[1,3\].right里，现已知这个数分到左子区间的一部分\[1,3\].left里，那就分析这一部分就行了，\[1,3\].left的长度为2，那么想找的数肯定就在这两个数里。所以新的right是新的left+cnt-1即1+2-1=2。  
所以，新的L，R，left，right分别为0，4，1，2。实际情况也为如此，到了第1层的左子区间，只需要分析\[1,2\]区间即\[2,3\]就可以在之后找到想找的数。之后以此类推。递归调用参数表如下：

<table> 
 <thead> 
  <tr> 
   <th align="right">dep</th> 
   <th align="center">L</th> 
   <th align="center">R</th> 
   <th align="center">left</th> 
   <th align="center">right</th> 
   <th align="right">k</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="right">0</td> 
   <td align="center">0</td> 
   <td align="center">9</td> 
   <td align="center">1</td> 
   <td align="center">3</td> 
   <td align="right">2</td> 
  </tr> 
  <tr> 
   <td align="right">1</td> 
   <td align="center">0</td> 
   <td align="center">4</td> 
   <td align="center">1</td> 
   <td align="center">2</td> 
   <td align="right">2</td> 
  </tr> 
  <tr> 
   <td align="right">2</td> 
   <td align="center">3</td> 
   <td align="center">4</td> 
   <td align="center">3</td> 
   <td align="center">4</td> 
   <td align="right">2</td> 
  </tr> 
  <tr> 
   <td align="right">3</td> 
   <td align="center">4</td> 
   <td align="center">4</td> 
   <td align="center">4</td> 
   <td align="center">4</td> 
   <td align="right">1</td> 
  </tr> 
 </tbody> 
</table>

递归到left==right时，找到第k大的值tree\[dep\]\[left\]

## 实际例子2：递归到右 ##

L=0，R=9，left=3，right=5，k=2  
寻找\[3,5\]区间中，大小排序第2的数？该区间为\[3,6,4\]，第2大的数为4，这里我们最终就会找到4。  
递归到右，还得提供新的k。

*  首先分析第0层，\[0,9\]被\[3,5\]分成了三个小区间，\[0,2\] \[3,5\] \[6,9\]，靠左区间分到左子区间的数的个数为2，查询区间分到左子区间的数的个数cnt为1，靠右区间这里不用分析。
 *  有k>cnt，那么这第k个数肯定被分到右子区间了。
 *  右子区间是由\[0,2\].right \[3,5\].right \[6,9\].right依次组成。
 *  要分析到第1层，需提供新的L，R，left，right.
 *  因为分到右子区间，所以R不变，L=(L+R)/2 。  
    新的left和right即为\[3,5\].right的最小最大索引。
 *  查询区间分到右子区间的数的个数cnt为2，靠右区间分到右子区间的数的个数cnt为2。
 *  那么从右边排除掉靠右区间分到右子区间的数的个数ant，便是新的right=新的R-ant。（注意ant指的是本段中的ant）
 *  查询区间分到右子区间的数的个数cnt为2，即要分析的数就在这2个数里，所以新的left=新的right-cnt+1。（注意ant指的是本段中的ant）之后以此类推。
 *  总之，\[3,5\]中有(5-3+1)-cnt个数被划分到了右子区间，cnt指\[3,5\]分到左子区间的数的个数（即查询区间.left），cnt为1，本来是要找第2大的数，但是已经有了cnt个即1个数分到左子区间，这分过去的数肯定是\[3,5\]中较小的数，所以想要找的数的排名就提前了cnt即1，所以新的k为k-cnt

递归调用参数表如下：

<table> 
 <thead> 
  <tr> 
   <th align="right">dep</th> 
   <th align="center">L</th> 
   <th align="center">R</th> 
   <th align="center">left</th> 
   <th align="center">right</th> 
   <th align="right">k</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="right">0</td> 
   <td align="center">0</td> 
   <td align="center">9</td> 
   <td align="center">3</td> 
   <td align="center">5</td> 
   <td align="right">2</td> 
  </tr> 
  <tr> 
   <td align="right">1</td> 
   <td align="center">5</td> 
   <td align="center">9</td> 
   <td align="center">6</td> 
   <td align="center">7</td> 
   <td align="right">1</td> 
  </tr> 
  <tr> 
   <td align="right">2</td> 
   <td align="center">5</td> 
   <td align="center">7</td> 
   <td align="center">6</td> 
   <td align="center">6</td> 
   <td align="right">1</td> 
  </tr> 
 </tbody> 
</table>

递归到left==right时，找到第k大的值tree\[dep\]\[left\]  
重要规律：递归调用参数表中，tree树中的dep层中的\[left,right\]就是我们要分析的范围，发现这个范围在递归的过程中，要么范围不变，要么范围变小，直到变小到\[left,right\]的长度为1时，便到达递归终点，tree\[dep\]\[left\]即为想找的第k大值。

# 划分树——建树 #

建树的代码，实际上就是根据num数组，返回tree二维数组和toleft二维数组。程序是递归的过程，过程和划分树结构图片一样。

*  tree\[dep\]\[i\]——树中第dep层中第i位置的数
 *  sort\_mid——中间变量，代表当前递归参数left，right为\[left,right\]时，将\[left,right\]区间内的数排序后的中间位置的值
 *  toleft\[dep\]\[i\]——代表第dep层中，从0位置到i位置有多少个数分入下一层的左子区间。
 *  lpos和rpos——下一层左子区间和右子区间的开始指针（最小索引）
 *  same——因为等于sort\_mid的数可能有多个，但可能是左边分到左子区间，右边的分到右子区间，这里是记录左边分到左子区间的个数
 *  count——记录当前节点下，位置left到位置i中有多少分到左子区间

num = [1,5,2,3,6,4,7,3,0,0]#条件
    
    tree = []#二维列表，作为返回值
    sort = []#中间变量，是每一个节点的内的元素的排序
    
    toleft = []#二维列表，作为返回值
    
    def build(left,right,dep):
        if(left==right):#递归终点
            return
        if(dep==0):#第一次递归
            tree.append(num)
            toleft.append([False]*len(num))
        else:#不是第一次，当前层的tree不用建了，但toleft得建
            if(len(toleft)==(dep)):
                toleft.append([False]*len(num))        
    
        sort = tree[dep][left:right+1]
        sort.sort()#此处可能还能优化
        temp_mid = (len(sort)-1)//2
        sort_mid = sort[temp_mid]
    
        mid = (left+right)//2
        same = mid-left+1#现在是左子区间的长度
        for i in range(left,right+1):
            if(tree[dep][i] < sort_mid):
                same-=1#执行完此循环，便得到左子区间中，sort[mid]的个数
        lpos = left
        rpos = mid+1
        count = 0
        #接下来要为下一层建树，但tree[dep+1]这个list还没有建立，需要每次建立
        if(len(tree)==(dep+1)):
            tree.append([False]*len(num))
    
        for i in range(left,right+1):#tree的i，索引从0开始
            if(tree[dep][i] < sort_mid):
                tree[dep+1][lpos]=tree[dep][i]
                lpos+=1
                count+=1
            elif( (tree[dep][i] == sort_mid) and (same > 0) ):
                tree[dep+1][lpos]=tree[dep][i]
                lpos+=1
                same-=1
                count+=1
            else:
                tree[dep+1][rpos]=tree[dep][i]
                rpos+=1
            #上面每次把一个数加入到子区间内 
            toleft[dep][i] = count
    
        build(left,mid,dep+1)
        build(mid+1,right,dep+1)
    
    build(0,len(num)-1,0)
    
    for i in tree:
        print(i)
    print()
    for i in toleft:
        print(i)

# 划分树——查询 #

def get_ant(toleft,L,R,left,right):
        #L>=left right<=R，这是已经成立的
        interval_left = 0#在[L,left-1]中进入到左子区间的数的个数
        interval_current = 0
    
        if(L<left):#此时在[left,right]的左边，会有一个左边区间
            interval_left = toleft[left-1]                       
        elif(L==left):#此时在[left,right]的左边，根本没有左边区间
            interval_left = 0
        interval_current = toleft[right]
        return (interval_current - interval_left,interval_left)
        #返回元祖，0元素为查询区间分到左子区间的数的个数
        #1元素为靠左区间分到左子区间的数的个数
        #第二个值，当接下来递归到左子区间时，能用上
    
    
    
    def query(L,R,left,right,dep,k):
        if(left==right):
            print( dep,L,R,left,right)
            return tree[dep][left]
        print( dep,L,R,left,right)
        mid = (L+R)//2
        cnt = get_ant(toleft[dep],L,R,left,right)
        #newl,newr是接下来要分析的left,right
        if(cnt[0]>=k):
            newl=L+cnt[1]
            newr=newl+cnt[0]-1
            return query(L,mid,newl,newr,dep+1,k)
        else:
            offset = (R-right) - (toleft[dep][R] - toleft[dep][right])
            newr = R - offset
            temp = (right-left+1)-cnt[0]
            newl = newr - temp + 1
            return query(mid+1,R,newl,newr,dep+1,k-cnt[0])
    
    #print(query(0,len(num)-1,1,3,0,2))
    #print(query(0,len(num)-1,3,5,0,2))
    #print(query(0,len(num)-1,1,5,0,2))
    #print(query(0,len(num)-1,4,7,0,2))
    #print(query(0,len(num)-1,0,9,0,2))
    #print(query(0,len(num)-1,0,4,0,2))
    print(query(0,len(num)-1,3,5,0,2))

测试用例可能不全，请读者自行新增测试用例。

[Link 1]: https://book.douban.com/subject/27026114/
[Link 2]: https://blog.csdn.net/anlian523/article/details/80766794
[20180623163630191]: /images/20220522/3653585ebbd0474d9f0fb3b7c14e2a48.png
[70]: /images/20220522/4e76ac59e0104ffdaafc3cdfdc9c8210.png
[20180623180408835]: /images/20220522/20aeab27351b42b6adf34bff5f30c890.png
[20180623180534143]: /images/20220522/00aab071610242fcad1e7675ba8b2607.png