FOo_bar_2's blog

Cartesian Tree of a Tree
By FOo_bar_2, 4 years ago, In English

Note : By tree I mean a weighted tree where each node has a weight.

Is there anyway to build the Cartesian Tree of a Tree efficiently (less than $$$O(n^2)$$$) ?

By Cartesian tree of a tree I mean the following:

Find the node with minimum weight in the Tree. Make it the root.

Recursively do this for each of the subtrees formed and attach their roots to the Earlier root.

I chose to call it Cartesian Tree because it is very similar to this.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Take a link cut tree where each disjoint tree holds a pointer to the cartesian tree parent(ctp). Initialize it with the whole tree fully connected. Assumming all nodes distinct, sort the nodes in increasing order by value and add the nodes one by one. Find the ctp of the tree the node is currently in, attach the current node to it, then delete all links to it and make the new disjoint trees each have their ctp equal to the current node.

I think there is also decremental dsu that would work just as well and is easier to code? Surely there is an easier sol with centroid decomp though, or maybe even easier. Would love to hear it!

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't fully understand Link Cut Trees. I will try to parse this after I learn them.Btw do you know the solution using Centroid Decomposition ? Also what do you mean by a decremental dsu ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      No I don't know centroid decomp sol, that's why I want to know it too, if it exists. Decremental dsu is just what it sounds like. dsu except delete edges instead of add.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe the following may work.

Take the tree and find its pre-order traversal. If you remove a vertex, the tree splits into several subtrees. All but one of these subtrees is an interval in the tree, one might be composed of two intervals. In principle, you could now construct the tree by recursively splitting these intervals, using a segment tree to find nodes of minimum weight.

However this can get slow: because you have these subtrees that consist of multiple intervals and they can get arbitrarily complex. Here's how you get around it. When you split a subtree $$$G$$$ that consists of $$$k$$$ intervals, one of the subtrees $$$H$$$ it creates might consist of $$$k + 1$$$ intervals, the others have only 1 interval. We can speed up taking the minimum of $$$H$$$ by keeping a cache of the minimums of the $$$k$$$ intervals $$$G$$$ consists of, and passing that on to $$$H$$$. Only one of the $$$k$$$ intervals has been removed and replaced with two intervals, the rest of the intervals of $$$H$$$ are the same, so we only need to take 2 minimums to split $$$H$$$.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

I believe a simple union find(DSU) will do. Sort the nodes by their weight descendingly. Now start adding them one by one. When you are adding a node look at the adjacent nodes which have been added. Connect all of those into one component and mark the root of the whole new component the newly added node. The children of that node in the CTT(Cartesian tree tree) are the previous roots of the components you connected.

This often appears in problems although I haven't seen anyone call it a Cartesian tree. Imagine this problem, the weight of a path is the minimum weight of a node on it. Calculate the sum of weights of all paths.

→ Reply