Video 9-5: §9.4 Cartesian trees

0:00 Introduction to RMQ

0:02 in the next sub section i want to talk about cartesian trees these will at first appear to have nothing to do with what which uh with what we want to do but they will then in the next subsection turn out to be the key technique to achieve the ultimate rmq data structure so far we've achieved an n login pre-processing time and space data structure that has constant query time using the sparse table technique and it seems without more sophisticated tricks like this one using the cartesian trees where we're stuck at this super linear pre-processing time so what are cartesian trees uh remember again that um our our arrangement query problem has a relation to trees that we've already established namely when we were looking at the the motivation of the problem we talked about the arrangement query on the longest common prefix array for suffixes and how that corresponded to the lowest common ancestor of two leaves in the suffix tree now that's quite a stretch of topics and suffix trees will not come to our rescue in this case but a much simpler construction actually does and uh i want to illustrate this on an example before we start um suppose we have an array here and for this section i will so this is maybe a a warning i should

1:42 make here i want to switch to range maxima instead of minima uh the reason is only it makes the pictures nicer by allowing me to draw um a bar that is as high or a pole that's as high as the value in the array whereas with minima i would have to negate everything and so this is inconvenient but of course when i can solve range maxima query i can also solve range minima query by just negating all the values or reversing the order relation the two problems are the same they're symmetric it's very similar to when we were talking in unit 2 about the priority queue adt and heaps we also had the observation that the same tricks work for a minimum oriented priority queue or a maximum oriented priority queue as long as you don't mix the two together it's easy to taf either one or the other and the same is true for arrangement queries you can use the same tricks to get range max if that is more convenient for your purposes or the other way around i'll explain what cartesian trees are for the range maximum problem and the same trick applies to the range min problem it just depends on the application which is more natural to define for the longest common extension queries

3:15 you need the minimum that's why i introduced it that way in the first place okay with that warning aside uh here's what i did here's an array of numbers and to make this a bit more graphic i just represented these numbers as the height of a what does that have to do with range maxima well i can

3:42 if i if i have arranged maximum query first of all just on this example um as before so range max is the index of the maximum in that range so what i do is um i start from plus infinity and slide this line down so i'm i'm moving a bar down and i can continue doing doing this until i hit so here i bump into this pole and that pole is the highest obviously so uh the position of that pole um that will be 9 because that's the first pull i hit when i slide down the line just stretching the range that i'm interested in okay that's just a reformulation of of range marks in in geometric terms if you like okay so here's the solution and again the pre this is what we had before um the task in in all of this is pre-process the array so that you can answer range maximum query fast ideally in constant time that's uh what we will be after that's all uh repetition now when things get things get interesting um by uh making the following observation and this will this will appear to come out of nowhere for now but uh let me just define it and then it'll make sense at the end i think

4:33 Defining Cartesian trees

5:08 let's define a binary tree as follows we put a root node at the highest pole so suppose initially we have a a line covering the entire range and you slide this down and the first thing you hit that will be the root of your cartesian tree now after you hit this root you have two lines the one that's on the left and the one that's on the right of this root and you slide them down independently until they they again bump into a pole and that will be the next notes of your cartesian tree so you connect these and make them the children of the root that's what i did here in nicely

5:58 notice that what i put inside of the notes is just the the index in the array that's just to help us um distinguish the notes we will um we will not need these labels at the end but uh for now this is this is what they are at the moment

6:18 okay once you've hit this bar the bar is again split now you have a range between those two notes you have a range left of that and here's there's actually nothing left this is all empty so nothing happens anymore and again these lines slide down individually until they bump into the first poll and then you get the next the next round of notes okay

6:43 i guess it's it's kind of clear how this continues um and that way you can define a binary tree that has one node for every position in the array

6:58 and it in a sense it nicely follows the the structure of these heights just by the way it's defined okay so so far so good let me briefly pause and give you a chance to answer to ask questions about this um is the definition of this cartesian tree clear how it's how it's constructed rephrasing what i just said you can take your array you find the maximum in the in the array and that splits your array into a part left of that maximum and right of that maximum and so independently for these two parts you construct the cartesian tree and attach it as the two children left and right of the root which is sitting at the maximum position that's another way to say what i've just shown you uh on the example um just a more algorithmic

7:58 formulation maybe but otherwise it's really the same okay if that's if that's clear then let's move on and here i need the full screen how does this how does that connect in any way to arrangement queries it does through the following observation if you have a range max sorry i'm saying rangeman but i mean range maximum query in this in this subsection if you have a range maximum query like this 6 and 14 the one that is shown here in red let's suppose we don't really look at the array but we look at the tree only we can find that there there are two nodes this one 6 and 14 which are the uh which corresponds to the arguments in the range max query and they're also the outermost nodes in that range by the index so two ways of saying the same thing you can find the two nodes that correspond to these indices i and j the range well the the outermost nodes in that range and then the range max query is simply the lowest common ancestor of those two nodes in this case you have to walk up up to root to this node nine before the paths to the root meet and that means that is the rangemax query okay

8:14 RMQ and tree traversal

9:41 now um the cool thing about this is why this is really helpful is that it also works if i take away the array we need now is only the tree and we find those common ancestors i didn't really look at the array to find that nine was the lowest common ancestor of these two nodes i just kept walking upwards and then at some point they chain uh they they join their paths join and uh the first the first note in where they where they meet that is what i return that's the lowest common ancestor now um there's still a little trick we can play uh so this first of all is just drawing the tree differently here it was drawn where the height of the notes still encodes um the entry in the array but we don't really have the array in mind what we have is just the tree so this is um ignoring the the previous heights this is just the topology of the tree of course that doesn't change the relation between children and parents so we can still find lowest common ancestors in the same way and finally we also don't have to store those numbers 6 14 and 9 because these are just the in order numbers so we can find those by

11:06 doing an inorder traversal which means we start at the root then we always do um first the left the left subtree then we visit the root and put its number in and then we go into the right subtree so we do an in order traversal

11:35 and number notes as we visit them so we start at the root first going to the left subtree that is the left subtree we have another route we first go into there's another node going to the left sub tree that's the left subtree and i keep repeating this until there is no left subtree and so this node gets assigned zero the first index in the left in the traversal so if you want we walk on the outer side of this tree down until we have to turn around and then we put in the number so here again we have to turn around so we have finished with the left subtree then comes the root of this tree put in a one and then continue again here we have to turn around no subtrees so after one comes two and then we walk back up at this point we have finished processing the entire left subtree of that node so that gets the next number and i'll do a few more but then i think you you get the picture so we finished the left subtree so we put now a four the next number into this note before we continue into the right subtree here we walk further down there is a left subtree we move we

12:50 visit that first now we have to turn around so the next number goes into here we move up we finish the left subtrees the next number goes here and so on and so forth so you continue to walk around the tree like this something we've seen before

13:11 and that way you can assign you can compute these numbers that i wrote into the notes on the fly you can reconstruct them you don't really have to store them it's enough to just store how the tree looks like which means which nodes have left and right children that is enough to answer the range minimum queries in an in a sense of encoding if you wanted to to tell someone what is the arrangement the range max what is the range maximum of 6 and 14 in this array you could send that person an encoding of this tree and that would be enough then you just tell that person do a inorder traversal annotate all the nodes with their inorder rank and then go to the nodes that have rank 6 and 14 respectively find their lowest common ancestor and that's your that's your range max good

14:14 that's a cartesian tree and let's see if you're are if you're following on this one uh so here's a little um a little task for you to practice this uh here's a little our cartesian tree and your task is to

14:15 Cartesian tree exercise

14:37 answer this range min query on this little tree so you suppose you're actually in this in this situation now someone sent you just a description of this tree and the two numbers one and five and uh you're supposed to tell me now what is the the range max query so this is max right range max of one and five

15:04 i'll give you a minute to think about this and try it out you might want to do it on a piece of paper the example might be a tiny tad too big to do it in your head but maybe you can actually do it um yeah i drew the tree in a in a convenient form so if you notice that structure it's actually easy to do

15:42 i'll give you a minute to think about it and then um i'll show you for those of you who didn't see how to do it i'll show it in a second

16:00 i see some answers coming in that's great we had 16 votes initially for the programming possible so maybe we can get something closer to 10 at least uh maybe if you're if you're entirely lost and you don't you don't feel you have any clue what i'm asking maybe just let me know because then your vote counts and we can move on and i can show you what how it works

16:33 but if you want to figure it out um i'm we're not in a rush it's it's fine to take your time i'll leave the tree up for all of those who are trying to do this i'll wait till we have 10 votes and then i'd move on

17:33 in case this is relevant remember we start counting in arrays from zero and the same for the in order ranks okay we have eight votes now maybe we can get two more and even if that is two more i don't know that's fine

18:27 we're stuck at eight maybe we can get two more i guess the good news is that you might actually be still thinking about this there are more people tuned into the live stream so i suppose some of you are still working on this but then the eight people have already voted our board so maybe i'll give you uh one more minute but then you should move on can we get 10 votes

19:26 okay i declare time's over and uh let's uh let's move on despite the fact that we didn't get the the 10 votes full um but at least according to my watch uh the minute has passed ah last minute in great okay so let's lock this one out i i don't have to show the votes you see it on the right but um

19:51 maybe just for the sake of showing it on the video oh you don't see the votes that's a good point and uh we can change that so here are uh the answers and there seems to be consensus about three um and that's that looks good so uh let me briefly go through this um without spending a lot of time on this little example but um

20:20 okay so we uh the first step is to annotate the tree with inorder numbers so we go all the way left right we walk around this tree so that gets zero then one then two three four five six seven if you paid attention on the last slide it was actually uh the the way i i drew this tree conveniently is so that the numbers here one zero one two three four five six seven etcetera uh they're just um in left to right order if you slide a line a horizontal line from the left to the right you encountered the notes in order uh in order in order and that's that's what's also happening here then um we mark node one and five so these are here and then we find their lowest common ancestor and obviously if i walk to the root from these two i would meet in this note so that is the answer number three

21:31 good uh another way to show this would be to reveal that um so let me go back and forth on this a couple of times there is an underlying array for this there are many underlying arrays that give rise to the same tree but here is one and so just to convince you you get this tree from this ray for example and then the arrangement in this range

22:06 from one to five has oh range max of course the maximum in that range is at position three so hence three is the right answer okay good i hope this little example uh woke you up and showed you another time how cartesian trees encode the rangemax queries and equivalently arrange minimum queries but only one of them and in a way that doesn't even talk about numbers anymore it's only talking about trees and lowest common ancestors and in order numbers but that's intrinsic in the trees so we don't have to store them

22:53 Visualizing tree structures

22:56 if you want to see a slightly larger example of a cartesian tree here's an array so these are these are the values and then i first drew the notes at that height so you see the maximum here is the root because 30 turned out to be the largest number in this in this array and then you get a nice graphical correspondence

23:20 assuming is always a bit finicky in this one so uh you get a nice picture where here i i drew the lines that are sliding down you start with the large horizontal line until it bumps into this pole the the highest is for 30. and then that gives you a vertical split all the way down and then this line continues sliding down independently from the other one and it bumps into the 27 on that side whereas the other half bumps into the 29 here so you see how this is um this is grouped and how you move down and it probably also the vertical line just visually helps um to see what's going on

24:08 well to be totally honest with you i drew these pictures because i'm i did research on on this topic and so i had them available anyways i wrote programs to do these so i included them i don't have much else to say i just wanted to show a bigger example to show off a bit so here's here's one cartesian tree for this array if you draw draw the same tree in a more typical way how we would draw trees you would essentially push the the y axis the the y direction a bit together so it's the same tree but now whenever you go to a child you go one step down in y direction that's the only difference between those two and if you want to see the tree a little clearer you might want to remove these separating lines and so here's here's this tree again but that's that's really all on this

25:13 slide all right so now we've seen and understood what cartesian tree or what a cartesian tree is uh you might still wonder how that helps for an efficient algorithm because so far it looks like you would have to first annotate this tree with all the inorgan numbers and that takes linear time then you have to somehow find a smart way to find lowest common ancestors in fact at the time in unit 6 we said we can reduce the lce problem longest common extensions two lowest common ancestors in suffix trees and at that time we said here's a fat black box a magic solution that does lowest common ancestors in constant time after preprocessing and now we've reduced our arrangement query problem to lowest common ancestors but somehow that's the that's the wrong direction uh arrangement queries look if anything easier to solve than lowest common ancestors uh and that's that's totally true uh in fact usually people use rangeman queries to solve lowest common ancestors not the other way around now so it looks like this cartesian tree is a nice theoretical construction but might not help you algorithmically too much at this point i agree i will disagree later on but we'll only get there after the break there's one thing we can do with

26:43 cartesian trees though immediately and that is counting the number of different solutions and for that they are really really instrumental the key observation that i hope you took from the examples that we went through is if you fix the cartesian tree you can answer all arrangement queries interestingly the same is also true in reverse if you have an array and you know all the answers to all the arrangement queries all the range max queries one of them

26:44 Encoding binary trees

27:20 that is enough to construct the cartesian tree it's maybe not so surprising because you take the entire range that gives you the root and then you just recursively construct the roots of the subtrees but that's that's beside the point uh not not really what i want to go into here what i want to use this this fact for is to count the number of different instances for range map for the range max problem because we can instead just count the number of cartesian trees and cartesian trees are simply binary trees and that's that's all and binary trees are well studied so people have counted them in particular if you have n nodes in your binary tree it turns out that this is exactly the number of different binary trees you can construct from n nodes so for example if n is three how many binary trees can you construct with three nodes there's this one there's the opposite one there's the more balanced one where you have the middle one in the root and then there's the two zigzag ones uh this one okay let me maybe move over here and let's make this so that we can fit them both in here and the mirror image of that one these are the five

28:53 these are the five binary trees made from three nodes and you can work out that this formula correctly predicts that i don't want to do that now i also don't want to discuss why this is correct um i think this is something worth knowing as a computer scientist the catalan numbers count the number of binary trees of n vertices and nodes what i want to show instead is that we can encode a tree easily with two n bits so there's at most two to the two n binary trees and that means if i want to encode them i have to take the binary logarithm so if i wanted to specify one of these five trees i could try to do this in a smart way but i can also just take 2 times 3 so 6 bits might be a bit wasteful because 5 is less than 8 so for small numbers here you could you could specify one of the trees using just three bits um i actually allow you to take twice that but as n gets bigger these two things get um very close so the the waste in this simple code that i want to present to you becomes less and less relevant as n gets bigger

30:17 so let's see how we can encode a binary tree in 2n bits what i'll do for that is let's take this one as an example first uh maybe this one is slightly more interesting okay let's let's do them all maybe that's uh that's better

30:43 so the code goes like this in two bits whether or not it has a left and right child so we have zeros has no left child the one here says but a right child okay and pre-order traversal is important that means we walk down the tree and uh we visit the root first so the code for this tree would we start here then this gets rank zero then we walk down the tree this gets one we walk down this gets two we walk down this gets three then we return and walk down again that gets four walk up return return go to the next subtree that gets a five six and then we walk all the way back up we have seen everything in the left subtree now so we continue in the right sub tree only then and that gets a 7. and to encode this tree up here what i would do is i concatenate all these two bits for all the vertices of all the nodes so 0 has a left and the right child so it's represented by one one the next node is again binary it has both children so we have another one one the uh hold on this the two is also binary has both children so another

32:42 two ones okay and then the three has no children at all so it gets two zeros so you can always take two bits together specify one node and this is one zero one two three and so on let's briefly finish this off just to be have a complete example four five has no left but a right chance so that's zero one six has nothing and seven has nothing

33:16 okay so that's that's easy enough um now you might wonder if you can decode this uh and the answer is yes you can by uh doing a pre-order traversal and constructing the tree uh while we're while we're doing this so suppose we didn't know we didn't see this uh it's it's hidden and we can actually do that so we only have this code and let's construct the tree step by step first of all we create a node and we attach two portals two little uh beginnings of an edge because uh one one says it has both children and then we keep constructing in a pre-order traversal the next node so first of all the next node is again one that has both um and the left the the next slot in a pre-order traversal of our tree is this one so we take that one and put it here okay then we create the next node it's again a binary one so we create one with two slots and we put it in the leftmost position that's free in the tree you see how this goes the next one is a a leaf that has no slots so maybe we mark this as finished so there's nothing or maybe uh even put like these little null pointers here

34:47 so these are to mark the fact that there's nothing happening and again put it in the leftmost slot that's free the the first slot you encounter in a pre-order traversal now we've gone through all these we have two more leaves this one more leaf that goes here the next slot so we move up the next slot here corresponds to the zero one so it doesn't have a left child but it has a right one then we have two more leaves we add them here and here and here and here and

35:28 there is our same tree again so we can encode and decode uh two in bits are enough to specify a binary tree and this is a simple encoding that one can use for that so far so good

35:46 let's see if you were following and uh this one i'll only leave it open for a shorter time because i want to get to the last topic today as well so let's briefly see if if you were following on this one

36:09 here's a smaller tree and i'm asking you to encode it in using the same code i just used on the bigger example and you only have to encode it we don't do the decoding here so the code again do a pre-order traversal and store for each node the the two bits does it have a left child doesn't have a right child

36:37 uh yep that first answer looks good maybe we can get a few more um just for the fun of it and maybe yeah while you're still typing i'll prepare the solution so we walk around the tree like this we first see this node then this node then this node then this node and we have to concatenate all their types

37:07 so 0 one two three and clearly zero has both children so that's one one node one has a left but no right child so that's one zero two has nothing 3 has nothing and that is it