Video 9-4: §9.4 Cartesian trees

0:00 <Untitled Chapter 1>

0:05 in the next section we'll look at cartesian trees which is a different way to look at the arrangement query problem it seems first not to have to do much with sparse tables and these other solutions but we'll bring it back together in in the subsequent section

0:23 RMQ & LCA

0:26 let's look at this problem again and try not to focus too much on how we store it how we solve it first on this on this slide i want to draw this more graphically so each element in the array is shown as a bar and it's a little inconvenient to talk about the minimum bar because i want to have this this metaphor that something sinks down from the top until it hits the first the first column so let's in this in this part look at range maximum queries it's of course the same problem you can just take your array and negate all numbers or invert the comparisons it doesn't change the problem at all it's just to make the pictures a bit more um to make the metaphor work out better so range max in this section okay whenever i say i will probably say arrange min a few times and mean range max so you have to be aware of that it's it's arranged mint review all over the literature which is maybe inconvenient uh as i said drawing it is is uh usually nicer with max conveniently the abbreviation is the same so maybe i should just say rmq and you have to substitute the right thing good so same problem rmq in this section

1:49 means i want i want to find the maximum in the range we'll keep the same conventions we're interested in the position not the value and the leftmost of the positions where the maximum occurs

2:05 so here's another example just for the metaphor you have a range and so you can imagine you take that range you take a a wooden bar a plank of that width and it sinks down until it comes to the rest on the highest of these poles and so the position where it touches the first pole that's that's the range max right

2:33 and the task stays the same we want to pre-process an array that's given and do do faster at query time all right so this is something because we have the time this this year uh let's let's put in um a little question about trips

2:56 okay this is not something autocorrection lets you go through okay i started the question maybe um let me add an option for for that would anyone like to click i've heard the terms somewhere but don't remember exactly

3:47 in case you want that third option it's now available it's one of these things we don't need trips it's not anything that we'll build on it's just that in case a lot of people knew it i would have adjusted the explanation it seems that no one has ever heard of them in case you're curious the words might suggest it's a a mixture it's a chimera of trees and heaps so it's it's a binary search tree that is at the same time a heap order tree but according to different different parts so each key has a value and a priority um it turns out to be the same concept as cartesian trees if you look at it from the right perspective but if you haven't seen trips at all that doesn't help you much and as i said it doesn't it it's not needed for this so let me just explain what a cartesian tree is then we construct a binary tree in the following way we let a line for the entire range sink down from the top it will hit it will make first contact on the range max of the entire range so the overall maximum of the array the leftmost occurrence of those in case there is several in this case that's that's here at

5:15 position 18. let me create a node which will become the root of a binary tree after that we continue this process independently on the left and of the right on the right of this maximum so on the left we'll we'll sink down a pole that's only as wide as up to this point so that will find the next smallest next largest element well the next smallest is right but it's the largest among the ones on the left so in this case this position nine and that will be the left child of the root connected on the right there's just single element but then this is also the maximum so that becomes the right child of the root and you continue like this recursively so after we've done this we take we take a piece of timber and let it sink down that is just below the two things already in the tree so that will hit hit ground here so this becomes the right child of the left child of the root and we do the same on on the left as well is the construction clear so you always you take the notes that you already have in the tree they will leave gaps and you let little wooden poles sink down in the gaps until

6:37 they touch a pole and then that becomes uh the child of the of the lowest node and so you keep going like this um every node you create might have two further children sometimes there's only one child because it's the outermost in its range and eventually you reach single element arrays in the recursion and then you just stop with with the leaf node in the tree all right so again find the maximum put a note there recurs on the two sides continue with the same construction that gives you the cartesian tree and the cartesian tree is is quite nice because it allows you to find a range maxima if you want to find the maximum in a range you go to the notes that are outermost in that range so more formally you take an in-order traversal of the tree where you visit first everything on the left then the root and then the right to the the right subtree and you assign indices to the nodes when you visit them another way to say it is if you draw a node always vertically above its position in the array you immediately get this that this is the left to right ordering right you see the nodes are just zero one two three four you should go sweeping from

8:04 left to right if you've done that you can go to the nodes of label 6 6 and 14 if that is the range you're interested in and you find their lowest common ancestor and that has to be the range max

8:24 all right so again finding the range maximum in a range means take the two outermost notes vertices in the tree and find their lowest common ancestor next step is if we have this tree we don't need the array anymore we can do the same without looking at the array at all in fact all i needed was the in order index of nodes and i can i can assign these just knowing the tree i don't need to draw the tree in any way or i don't need to act to access the array to do that i just do this recursive procedure visit the root uh well i mean start at the root visit the left subtree then visit the root and assign it its number and then go to the right subtree so if you do this recursively you would start labeling this one with zero then you come back from the left subtree you assign this the label one that's in order traversal and you assign indices as you visit nodes you can do this without the array just the tree so you can assign nodes these indices so you can find the nodes that have the indices delimiting your range and you can find the lowest common ancestor in return it's it's label you

9:56 don't need the array for that because i don't have the array i should really draw my tree like you would normally for a binary tree this still reflected the relative heights but this is uh just my way of drawing it right so this is really what's in what's given in the tree so same same thing uh just now any connection to the array is lost but we don't need that

10:29 let's see if you uh if you got this part um here's a little example of a cartesian tree and an array remember we start at zero right this i just tried to convince you that the tree is everything you need to answer range max queries there you go answer the range max query on the slide and uh see if not if that works out

11:19 and while you're working i'll just draw some helpful lines so that you're not lost in the counting at least but yeah it's a looks promising okay with 25 that was roughly about everyone i think

12:27 there's a cluster for three which is good um a cluster for certain smileys which is also good let's briefly do this um the range we're interested in is one to five so the first thing to know is that this is including the end points the cool thing about this one is i don't even have to tell you numbers in the array uh so there's no way to figure this out because i haven't really pinned down any specific array we'll do what we'll do is we'll trace the one up to its node and the five that gives us the range and then we find the lowest common ancestor of those two guys so we walk up until they meet and then we follow down again to get the answer so 3 is is the right answer that's where the the maximum in this array must be if this is the cartesian tree for it

13:33 and here's a a concrete example that i generated this from but again you don't know you don't need this and so yeah so cartesian trees look like they're really interesting because they take the essence of the problem and do away with the unnecessary detail if you give me an array you can always find a different array that has the same answers for all range max queries or arranged min queries for that matter but the arrays are different they have different values right and even if you say we've done a similar trick in sorting we said oh the values don't really matter so i can as well assume that these the things i sort are just the numbers one up to n i could do the same for for arrangement queries but then still two different arrays that are permutations of the numbers one up to n they could still have the same answers to all arrangement queries without being the same permutation so in a sense the problem is more lossy it ignores more information than sorting and the cartesian trees seem to be a slick way to get exactly at the amount of information contained in these queries they preserve all the arrangement queries and as we'll see actually nothing else

13:50 Cartesian Tree - Larger Example

15:05 now here's a bigger example you'll probably have to zoom in to see it properly so that's if you draw the array and then poles of the appropriate heights and that's how you would normally draw a tree where the depth in the tree is the y-coordinate

15:29 and you can do away with this scaffolding so you get the tree like this and you can still answer all the arrangement queries all right so why do we care about these range main queries we already know a slick way to get fast answers for range max arrangement using the sparse tables the only problem was that the space wasn't optimal but now i told you oh instead of looking at this easy range min query problem let's look at lowest common ancestors in trees but isn't that where we started we started with the suffix array or suffix trees we started with suffix trees and we wanted to find the lowest common ancestor of two leaves and after a long and winded road i told you huh the solution is to look at the lowest common ancestor into of two nodes in a binary tree so why all this journey uh this problem doesn't look any more fundamental or easier to solve than finding the lowest common answers to two leaves in the suffix tree and in a way it isn't we'll use it for something else

15:35 Counting binary trees

16:50 i made this comment before if i give you the cartesian tree all the answers to all possible arrangement queries are determined all the information needed for that is contained in this tree

17:05 and i left out the um the labels of the notes on purpose because they're they're all implicit if you know this is the root and has left and right child and so on that's all you need okay

17:20 so we can count how many different inputs are there for arrangement query problem of a certain length so i tell you the the array has length n then how many possible answers are there for all those arrangement queries there's a quadratic number of them and every output is an index so a naive bound would be something like n squared times n different answers that would be a quadratic but

18:01 sorry that's bogus you would have to take n different outcomes and raise that to the power of the number of them so naive a trivial bound would be something like n to the n squared which is an absurd number it's really big so if you would take the space of that you would take the log but then it would still be

18:52 and squared log n as the space bound and we've already seen how to beat that right very easily we've seen a solution that uses n log n space but there's a catch the sparse table solution still needs access to the array remember if we answer queries we need to look at the array to decide which of the if the blue or if the green region gives the minimum

19:21 what we use the cartesian trees for is to count the different numbers of rmq instances on a cleaner object namely binary trees and one way to do it is to just look it up the the catalan numbers counts exactly the number of binary trees on on endnotes and it can be written as this there's many interesting combinatorial proofs but we're not a combinatorics class so i'll spare you there's an easy way to show an upper bound by encoding the tree in a unique way so this is a if you want it's a compression method we can we're given a binary tree we produce a sequence of bits and from that sequence of bits you can reconstruct you can decode the tree again

20:12 there are different ways but i'll show you a particularly simple one um you visit all nodes in pre-order pre-order means i started the route and i first visit the root i'll tell you in a second what visit means we'll do something after you've done after you've dealt with with the root you go to the left sub-tree and recurse there and once you come back from the left subtree you go to the right sub-tree and do the same okay that's pre-order the important part is you do the root first

21:13 namely whether or not it has a left child whether or not it has a right child okay so again you visit all the nodes in pre-order whenever you visit a node you output two bits you append two bits to the encoded string

21:36 um let me briefly peek yeah we'll practice that on the next slide maybe we'll do the decoding just on on the next slide so for now um i want to bring this point first so by counting the number of trees we can count the number of equivalence classes of arrays if you only care about rmq and we'll see how to exploit that in the next section i don't want to practice this encoding a bit because i think it's it's kind of neat and useful to see that this really works so again um remember we go in pre-order through the tree and emit two bits when we visit a node whether or not it has a left or right child so let's do this on this on this smaller example

22:45 so it's four notes two bits each i'm expecting answers with eight bits right do you want me to show the last slide with the code well by the magic of digital let's just copy it

23:23 Clicker Question

24:35 okay i want to finish on time so um i'll start showing the example but you can still vote if you want uh let's first figure out in which order we visit the nodes we start at the root and we first visit so this is the first one that we look at and then we go left first go to the left we visit the root first so that becomes number two then we go to the left subtree we visit the root now we go to this is this guy's left subtree but there's nothing we go to this guy's right sub tree which is also nothing then we're done with this node so we return we've done all the left subtree of this guys now of this guy so we go to the right subtree but there's nothing so we're done go back up and well there was only one node left i guess so that's the order in which we visit the nodes and once we figured that out the rest is just writing down whether or not they have um a child of the appropriate direction one has two children so it must be one one two has just left so it's one zero and three and four are leaves so they are both zero zero

25:47 all right i think i've seen that a few times a few other suggestions too how did you get these vertical bars like uh this one okay can you send uh like um line breaks or is this just yeah uh and you guys coordinated on the same emojis even whose birthday is it

26:20 uh yeah i think that's a good point to leave it i do want to show how to decode the tree but i'm a bit out of time let's let me just show it on this example very rapidly so let's pretend we don't see the tree okay i just see this bit string and i'll start drawing oh you can't see thanks

26:50 i zoomed in so i don't see the tree i pretend i've forgotten it we start with the first two bits so we know this is from the root so we have to draw a node with two child ports two slots for children and now we do a pre-order traversal so we know we always go from the left most onwards so this is the first slot that we look at and now we pick the next note which is one of this type so i add a note it has a left child but it has no right child so i can add this little little box just to indicate this is a null pointer there's nothing missing here then again even if i forgot where i was i can always take the leftmost um free slot and now i have to put a new node here and it's a zero zero type so it doesn't have any children so leave but i'm done with this part and the next note i walk along walk along the tree until i find the first missing note slot and so here i go is the only one left and as a sanity check at the end i should have a complete tree with no dangling child slots left when i'm

28:04 done reading the the bit string all right so that's how you decode and so that should convince you that it's an encoding for the tree you can encode it and you can get the tree back why this all makes sense but have we talked about trees so much and counted them that you will see on thursday