Video 9-4: §9.4 Cartesian trees

0:00 Cartesian trees

0:03 okay this next subject subsection we'll look at Cartesian trees which at first seem to have nothing to do with how we use blocking or how we use this sparse table Solution on a smaller reduced instance but it will solve the second part of that problem and so I want to cover that first

0:28 this is about a very cute connection between the arrangement problem and again a tree but a different one not the suffix tree that we had before we already see we already we've seen one connection the Arrangement queries on the LCP array corresponded to lowest common ancestors of leaves in the suffix tree

0:51 um we'll see there's another correspondence and this is more direct and more convenient for us so here's our array um uh in this section I'll I'll look at range Maxima not minimum just because then the drawing is more convenient of course you can always take an array and negate all the numbers and then you turn Min into max or you just flip the meaning of what's what less means so this doesn't change the problem much as long as you just want either Min or Max uh the two are equivalent what Max means is we can draw the values of the array as as Heights of some poles and then you get some some nicer visualizations

1:46 so here I've done that um so again the the warning here we'll look at at Max just because it's convenient to draw if I pick a range in my array graphically speaking what the range maximum is is like uh

2:02 having some some pole covering this a horizontal line covering that range sink down slowly until it hits some tallest pole and then it stops there right so keep that picture in mind some some metal bars sinking down until it uh well it probably would tip over here but let's pretend it's like it's all sticky and there's Super Glue on on top of the poles uh so there um rmq in this on this slide means range Max and as as always it's the index not really the value

2:49 here's again the the pull in nicer drawing the task Remains the Same as before you're given the array and then we want to do faster query time now okay can I I should have put this on slido who has heard of trips it's a portmanteau of of tree and Heap you've seen binary search trees you've seen heaps but you may not have seen the trip if not doesn't matter much it just turns out to be exactly that idea in Disguise so if you have seen it you may say oh cool I recognize that if not uh it's kind of irrelevant to to this module it's just a neat connection the Cartesian tree is a binary tree on this array defined as follows we take such a a bar covering the entire array let it sink down it will hit the highest pole Let's Pretend here that the poles all have different heights and so if we if we need we can make the the ones with equal height the leftmost is a tiny Tad higher or our Graphics so here I picked numbers um where at least the maximum in each range is is equal is unique but there is obviously two of the same height here uh maybe it would have been better to

4:15 put them at all different numbers the Cartesian Tree starts growing as follows you have this pole covering the entire range sink down then it hits the tallest poles say that's unique and that becomes the root of the Cartesian tree and now we split our our metal rods at this position and let it sink down on the left and on the right independently so this will sync down here this will sync down here we'll see that the next thing that this hits on the left is is this one and on the right is this one these are the tallest poles outside of the globally tallest one and these will become the next two nodes in the in the Cartesian tree so that the global maximum divides the array in a left and in the right half and that will build a Cartesian tree recursively on these two segments um and their Roots will become the children of the global root that's what we did here the global root is the the global maximum is the overall route and from the left half this was the tallest so this becomes the next root and here on the right there's just a single note if we keep doing like this so again here we hit the line so we split it we let it

5:38 seeing on the left and on the right independently until we find the next tallest pole there we keep growing like this and we've got a binary tree because we're always split into the left and the right half every node will have at most two children um it can have no child on one side if it's right next to the maximum or on the boundaries and we have leaves when things are a local minimum

5:45 Binary trees

6:10 okay nice construction why why would we care about this this tree it turns out that the arrangement queries range Max queries pardon me the range Max queries are encoded in this tree and the way they are encoded is if you have this range you find the notes that have the in order position of the outermost points so this range goes from position 6 to 14. I've labeled all the vertices in the tree using their in order number so in order again is the traversal of the tree you start at the root you first visit the left subtree when you come back you take the next free number and stick that on yourself and then you recurse on the right so if we do that here recurse recurse recurse recurs recurse we stick the zero on the leftmost Node we come back next free number is one stick that on that vertex and then we continue in the right subtree next free number is stick there because it doesn't have a left child left subtree the way I always draw the binary search trees in unit 2 and so on this is just the left right left to right sweep of the vertices

7:35 um so that's that's easy to do in this in this visual representation but I want to stress that the information is contained in the tree you don't need this nice layout you can reconstruct it from just the tree so you find the two vertices corresponding to the endpoints of the range and then their lowest common ancestor is the range maximum okay

8:07 and in a way the the reason why that is the case if you walk up from this from this vertex you eventually have to reach the root and whenever you walk up you go to a a position with a higher number a taller Pole

8:25 at some point we have to to end up in the root so the paths join eventually always and the last time they are are separated that's the highest note in this poll because if there was another one um the two would be would be separated so um I don't know do we have a nice example for that situation

9:26 yeah it's just the nature of the problem and when the paths the lowest common ancestors is always a node where the two paths go one goes left and one goes right and so uh these two paths then from there on have to go jointly to the root so they they can't can't visit this range again

9:51 so we've translated the problem for finding range Maxima or range Minima to something on a tree now it turned out again to be lowest common ancestor but it's on a different tree it's not a suffix tree it's the Cartesian tree of the array no strings involved no strings attached uh just the definition from from the array

10:11 Cartesian tree

10:15 and of course this works even if I take the array away all I need is the the tree and I don't have to draw it in this particular way with notes at the heights of the pole all the information is just contained in the topology of the tree what are the left and right children of each node so you can reconstruct the in order labeling you can find the two vertices that correspond to the range endpoints and you can find their lowest common ancestor

10:43 and that nodes in order index is the answer to range Max all you need is contained in the tree that's the that's the point of the Cartesian tree all right so see if that uh good follow that part uh it's restarting so here's a little example where you just are given the tree and you're asked to

10:53 Example

11:16 work out what the the range maximum is as soon as slider lets me log in again I can start the question keeps redirecting to the login page and I know what the problems

14:51 and remember we start with zero so one is second from the left 10 we had 22 earlier but 15 for the example so I don't know shall we try to aim at 15 again

16:04 15 people or end of my patience whatever comes first okay let me let me show the the answers um various votes and for two but also three and so on so let me let me go through this slowly first of all we have to reconstruct the in order indices so we start at the root the current next free

16:59 um the current X3 number is zero but we first visit the left subtree same thing 0 is the next number but we have a left sub three to go to First and again in this node we don't have a left subtree so we return and still zero is the next number which we stick into this node

17:21 that's label zero and then we visit Its Right sub tree but that's empty so I return and go back to the parent the next free number now I returned from my left child now is my turn so I put the one in this node and continue with the right Subs right sub tree here again left is empty so I'm I'm labeling this note now next three is two and then the right subtree is empty so again I go up now I have covered the left subtree of this node and now it's this guy's turn so the next three numbers three and so on if you do this for this tree you see that it's nicely left to right because I was kind enough to align the tree that way again then we can find the two nodes that correspond to the range endpoints these are nodes one

18:22 and range Min now corresponds to the lowest common ancestor so we walk up the tree from there until we hit the root and the point where these paths meet that's the lowest common ancestor and so the return value for rmq is the index of that node which is three

18:47 a way to say to show the same thing closer to what we've had on the previous slide is to reveal what the array was that this comes from even though it's not necessarily needed and then here I've done the same thing um so that's that's how it it connects to These Bars in a way whenever you're given such a a tree you can invent an array that produces this tree and you can can work from there but there are many different options to choose the heights of the poles here's one

19:29 I've generated a few larger larger examples just to see the uh what these look like so here is the array in in very small print and then you see the largest the maximum in the entire array is somewhere here so that gives a vertical dividing line to left and right and that's the the bar sinking down so that becomes the root and then we independently treat the left and the right and so on so if you want to practice the construction you can take that bigger example and then you can draw the tree but compressing it basically pushing it pushing it together um you can push the left and the right half the right sub trees independently together so it's the same tree the same correspondence between nodes and their children but drawn to use a little less space

20:31 and of course you don't need these lines you can just draw the tree uh one little bit and then you deserve your break uh what what we'll need is not just this correspondence range main queries our lowest common ancestors in the Cartesian tree uh one one key Point why this is so helpful is that we've removed the array entirely there are no values anymore it's just one tree and so while there are many many different arrays with all the different values you could put in there's a much smaller number of binary trees

21:12 we've seen I I tried to convince you by example if you're given the Cartesian tree of an array all the arrangement queries are answered or the information is all there because for every pair of notice of nodes in that tree there's the lowest common ancestor is well defined and that's the arrangement

21:37 so the question of um how many different things can happen with Arrangement queries if you're given an array it's the same as asking how many different Cartesian trees are there and um every every binary tree is possible as a Cartesian tree that's what I said earlier if you're given a tree you can generate an array that produces that and so you can just use look up the number of binary trees and endnodes is a known thing it's counted by the Catalan numbers which are well known in combinatorics they're counting all sorts of objects that have intimate relations to trees if you look at it from the right perspective but the formula is a bit uh unwieldy what we'll use is just a simple upper Bound for that namely that the number of trees of of endnodes is that most two to the two times n

22:37 and um I want to prove that quickly because it's it's very nice and a constructive proof what we'll have to do for that is construct a binary encoding of a binary tree

23:06 so that if the tree has n nodes the binary code uses two n Bits and why is that the case well the number of such um you know the the coach should be um unambiguous you have to be able to decode the tree again from this code so there's uh at most as many trees as there are binary strings of that length and the number of those binary strings is two to the 2N how can we do this well you can for example for each vertex

23:53 you can have two bits which tell you whether or not it has a left child and a right child so every node has potentially a left child and a right child and you store a one if it has a left child and zero otherwise and you store a one if it has a right child and zero otherwise so we do a pre-order traversal of the tree

24:54 Let's do an example with you um and you're supposed to do the encoding I just described so I should maybe copy that over we may reach the point where I'm losing you so let me let me do it on this on this tree first so what is a pre-order traversal it's similar to the in order to reversal we had before but now you visit the root first and then you go left and right sub tree so in a pre-order traversal means you walk around the the outer side of the tree like this and whenever you see a note for the first time you output its value so you visit this one first then this then this then this then this then this then this then this and if we output the the bits for these nodes in that order the the first one has both children so it gets a one one

27:16 the second has both children so it gets one one this one has both children one one three is a leaf so it doesn't have any children that's a zero zero let me jump to node four which is also a leaf zero zero and we jump to node five that has no left child but it does have a right child so it's zero one and then node six again is a leaf and we jump to node seven which is another leaf so from this from this bit string you don't necessarily see anymore uh that this was a tree but you can reconstruct it

27:55 you start reading the first two bits which means you get a note and because they're both ones you know there's something coming here and then again you follow the same the next thing that you're looking at is this node so you decode the next two bit I have a node and it has two children so again I'm following down here decode one more another with two children all right and so you always know which node you're decoding next and you know whether it has the children or not so you can reconstruct the tree that way

28:40 um I don't want to drag it into longer than necessary so let me just show your answers the the pre-order traversal starts with this node then moves left this is the first time we hit this we walk around the outside of the tree so we have to encode it in this order and then by the same means as before this one has both so it gets a zero one one this one has only a left child so it gets a one zero and then the rest the the rest two remaining to our leaves so they get two zeros each all right I think it's a kind of a nice little addition to our compression unit even though we didn't need it there but you can you can represent the shape of a tree with two end bits and it's relatively easy to encode and decode all we need this for here is is really to get this statement the number of binary trees on endnotes is at most two to the 2N