随笔-8  评论-5  文章-0  trackbacks-0

    我是从zoj的promlem classification里面找到这个题目的,开始时想不到什么好方法,企图从零开始一步一步建树。最后还是没想到建树的算法。
   后来查zoj forum,有人提到cartesian tree,于是google到了这方面的算法和数据结构。cartesian tree又叫randomized binary search tree,它是节点带权的二叉树,在插入新节点时,并非像平衡树那样做rebalance,而是维持父节点和子节点之间的权的大小关系(heap order),即要么父节点的权总是大于子节点的权,要么反之。NIST的网站还介绍了cartesian tree节点的插入和删除算法。大致如下:
    插入:

InsertNode(Node * newNode, Node * tree)
{
     
if (newNode->key < tree->key)
     
{
           tree
->left = InsertNode(newNode, tree->left);
           
if (tree->left->priority > tree->priority)    // 假定父节点的权大
                tree = TurnRight(tree);
      }

      
else 
      
{
          
// omited      

      }



}


    删除:

DeleteNode(Key key, Node * tree)
{
      
if(key < tree->key)
      
{
           tree
->left = delete(key, tree) 
       }

      
//omited  
}

     然而直接的建立cartesian tree会导致超时,假设最终的树的所有节点都只有右孩子,并且插入时,总是插入最右节点,那复制度将会是O(n!)。

--------------------------------------------------------------------------------

    后来又经过查阅资料,发现可以用qsort+RMQ的方法。首先,对所有的节点,以key值排序,这样得到的结果为最终cartesian tree的中序遍历。再根据priority值,从上到下找到根节点,以及根节点的左右子树的根节点。。。
    其中时间的消耗是:排序时间+找所有子树的根的时间。快速排序的平均复杂度为O(nlog2(n)),而利用RMQ可以在O(nlog2(n))内建立RMQ的矩阵,并在O(1)时间内查找任意范围内的最大priority节点对应的索引。
    RMQ算法主要分两部分:(1)建立RMQ的matrix,(2)查找
    (1)需要计算matrix[i][j]其中1<=i<=n, 0<=j<=[log2(n)](上去整)
    matrix[i][j]的含义为从i开始的宽度为2^j的范围内,priority最大的节点的位置
                      {  matrix[i][j-1]              priority(matrix[i][j-1]) > priority(matrix[i+2^(j-1)][j-1])
    matrix[i][j] ={
                      { matrix[i+2^(j-1)][j-1]   否则
    (2)查找RMQ(i, j),RMQ(i, j)的含义为从i开始到j为止的范围内,priority最大的节点的位置
    计算k=max{r|2^r < j-i+1}
                      {  matrix[i][r]                priority(matirx[i][r]) > priority(matrix[j-2^r+1][r]
    RMQ(i, j) =   {
                      { matrix[j-2^r+1][r]       否则

--------------------------------------------------------------------------------

  此问题还有一种最快的方法。考虑到对所有的输入节点做针对key的排序后,得到的数组为cartesian tree的中序遍历。

  1.  现在我们从左到右,一边顺序遍历数组,一边建立cartesian tree。
  2. 假设我们已经遍历到数组的第i个元素,并相应建立了有i个节点组成的cartesian tree,那么第i+1个节点必定在由i+1个节点组成的cartesian tree的最右路径的最右端点。
  3. 我们原i几点的cartesian tree的最右路径的最右端点出发往上查找第一个priority比i+1节点大的节点,如果找到了,就把i+1节点的左子树设为那个节点的右子树,把那个节点的右子树设为i+1节点。如果找不到,则把i+1节点的左子树设为原树的根,并把i+1节点设为新根。
  4. 需要主意的是,必须从下到上搜索最右路径,而不是从上到下。因为从上到下会出现O(n!)的复杂度,而从下到上的过程中,没个几点最多被走过一次,因为被走过的节点必被设为某个点的左子树,不再可能出现在最右路径中,所有有O(n)的复杂度。


--------------------------------------------------------------------------------


 最后给一下结果:第一种方法超时,RMQ为0.95秒,最后一种方法为0.51秒.

posted on 2005-08-03 00:20 pumpkin 阅读(1536) 评论(4)  编辑 收藏 引用

评论:
# 谢谢你的资料,,, 2005-10-01 17:27 | sophia_philem
~~~~  回复  更多评论
  
# 谢谢你的资料,,, 2005-10-01 17:27 | sophia_philem
~~~~  回复  更多评论
  
# re: zoj-2234-Binary Search Heap Construction 2005-10-11 20:29 | ybfqing
哈哈,谢谢!多亏了你呀,不然肯定超时死了!  回复  更多评论
  
# re: zoj-2234-Binary Search Heap Construction 2008-08-11 11:01 | 谢谢
谢谢了,很有启发  回复  更多评论
  
只有注册用户登录后才能发表评论。