Massive Algorithms: Cartesian tree

Cartesian tree - Wikipedia, the free encyclopedia
a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence.

Cartesian trees have also been used in the definition of the treap andrandomized binary search tree data structures for binary search problems. The Cartesian tree for a sequence may be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in a sequence.

http://codeforces.com/blog/entry/3767

A data structure that stores a pair (X,Y) in the form of a binary search tree with respect to X and a heap with respect to Y.

Assuming that al X and Y are different, for an element (X0,Y0):

- All the elements in the left subtree are such that X < X0

- All the elements in the right substree are such that X > X0

- All the elements in the left or right subtrees are such that Y < Y0

笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。

从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。

无相同元素的数列构造出的笛卡尔树具有下列性质：

结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素
中序遍历（in-order traverse）笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小，右子树结点所对应数列元素下标比该结点所对应元素下标大。
树结构存在堆序性质，即任意树结点所对应数值大／小于其左、右子树内任意结点对应数值

http://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html

笛卡尔树是一棵二叉树，树的每个节点有两个值，一个为key，一个为value。光看key的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的key都比它小，右子树都比它大；光看value的话，笛卡尔树有点类似堆，根节点的value是最小（或者最大）的，每个节点的value都比它的子树要大。

构造笛卡尔树的过程：

使用数据结构栈，栈中保存的始终是右链，即根结点、根结点的右儿子、根结点的右儿子的右儿子……组成的链
并且栈中从栈顶到栈底key依次减小

如果按照从后到前的顺序判断一个元素是否大于A[i]，则每次插入的时间复杂度为O(k+1)
k为本次插入中移除的右链元素个数。因为每个元素最多进出右链各一次，所以整个过程的时间复杂度为O(N)。

从前往后遍历A[i]，
1.对于每一个A[i]，从栈中找出（从栈顶往栈底遍历，或者从数组后往前遍历）第一个小于等于A[i]的元素
2.如果找到，i.parent为sta[k],同时sta[k].r=i，即i为sta[k]的右子树,
3.如果栈中存在比A[i]大的元素这些元素肯定是出栈了，这个问题最后的代码统一表示。
同时，sta[k+1].parent=i; i.l=sta[k+1] 即sta[K+1]为i的左子树
4.最后i入栈，比i大的A[i]都自动出栈了。

例子如下。
0 1 2 3 4 5 6 7 8 9 .....key
3 2 4 5 6 8 1 9 10 7 .....A,value

stack
0 1 2 3 4 5 6 7 8 ...num
0
1 2 3 4 5
6 7 8
6 9
最后sta[0].parent=-1; 为根节点即 6 为根节点。

这里给出的是索引从0开始的[0,n-1]
如果题目给出的是[1,n]，可以减一回到[0,n-1]上

http://www.sanfoundry.com/java-program-implement-cartesian-tree/

```
class CTNode
```
```
 {    
```
```
     CTNode left, right;
```
```
     int value;
```
```
 
```
```
     /* Constructor */
```
```
     public CTNode()
```
```
     {
```
```
         left = null;
```
```
         right = null;
```
```
         value = 0;         
```
```
     }     
```
```
 }
```
```
 
```
```
 /* Class CartesianTree */
```
```
 class CartesianTree
```
```
 {
```
```
     private CTNode root;
```
```
 
```
```
     /* Constructor */
```
```
     public CartesianTree(int[] data)
```
```
     {
```
```
         root = build(data);
```
```
     }
```

     /* Function to build Cartesian Tree from array */

```
     public CTNode build(int[] data) 
```
```
     {
```

        if (data == null || data.length == 0)

```
            return null;
```

        return build(data, 0, data.length - 1);

```
     }
```

     /* Function to build Cartesian Tree from array */

     private CTNode build(int[] data, int start, int end)

```
     {
```
```
         if (end < start) 
```
```
             return null;
```
```
         int min = Integer.MAX_VALUE;
```
```
         int minIndex = -1;        
```

         for (int i = start; i <= end; i++)

```
         {
```
```
             if (data[i] < min) 
```
```
             {
```
```
                 min = data[i];
```
```
                 minIndex = i;
```
```
             }
```
```
         }        
```
```
         CTNode node = new CTNode();
```
```
         node.value = min;        
```

         node.left = build(data, start, minIndex - 1);

         node.right = build(data, minIndex + 1, end);

```
         return node;
```
```
     }      
```

     /* Function to check if tree is empty */

```
     public boolean isEmpty()
```
```
     {
```
```
         return root == null;
```
```
     }
```

     /* Functions to count number of nodes */

```
     public int countNodes()
```
```
     {
```
```
         return countNodes(root);
```
```
     }
```
```
     private int countNodes(CTNode r)
```
```
     {
```
```
         if (r == null)
```
```
             return 0;
```
```
         else
```
```
         {
```
```
             int l = 1;
```
```
             l += countNodes(r.left);
```
```
             l += countNodes(r.right);
```
```
             return l;
```
```
         }
```
```
     }
```

     /* Function for inorder traversal */

```
     public void inorder()
```
```
     {
```
```
         inorder(root);
```
```
     }
```
```
     private void inorder(CTNode r)
```
```
     {
```
```
         if (r != null)
```
```
         {
```
```
             inorder(r.left);
```

             System.out.print(r.value +" ");

```
             inorder(r.right);
```
```
         }
```
```
     }
```

     /* Function for preorder traversal */

```
     public void preorder()
```
```
     {
```
```
         preorder(root);
```
```
     }        
```
```
 }
```

http://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html

6 int a[maxnum];
 7 struct node
 8 {
 9     int key;
10     int parent;
11     int l;
12     int r;
13 }tree[maxnum];
23 int Build_Tree()
24 {
25     int i,top,k;
26     int stack[maxnum];
27     top=-1;
28     for(i=0;i<maxnum;i++)
29     {
30         k=top;
31         while(k>=0 && a[stack[k]]>a[i])  //栈中比当前元素大的都出栈
32             k--;
33 
34         if(k!=-1)  //find it，栈中元素没有完全出栈，当前元素为栈顶元素的右孩子
35         {
36             tree[i].parent=stack[k];
37             tree[stack[k]].r=i;
38         }
39         if(k<top)    //出栈的元素为当前元素的左孩子
40         {
41             tree[stack[k+1]].parent=i;
42             tree[i].l=stack[k+1];
43         }
44 
45         stack[++k]=i;//当前元素入栈
46         top=k;//top指向栈顶元素
47     }
48     tree[stack[0]].parent=-1;//遍历完成后的栈顶元素就是根
49     return stack[0];
50 }

Read full article from Cartesian tree - Wikipedia, the free encyclopedia

Cartesian tree

Labels

Popular Posts