Video 9-4: §9.4 Cartesian trees

0:02 in the next subsection we'll look at cartisian trees as a alternative look at the range minimum query problem that will ultimately help us uh to find a better solution than the N login entries uh of a sparse table um but let me first uh just just show what it is before we motivate it much from an algorithmic point of view um now let me let me point out here to make the picture or make the the picture analogy the metaphor work well here rmq is the range

0:54 maximum you could have done it with minimum and then uh draw the picture the other way around um but we're computer scientists our trees have a single route and it's at the top let's stick with that very s sens sensical notion so um imagine you have an array of numbers and you want to solve the range maximum C problem so for every range you want to know what the maximum in that range is and uh to visualize it let me draw a bar or pole uh instead of the numbers that has as height the the value of that number the overall maximum is then obvious from just visual inspection it's it's this one right but if you want uh a range Max you can do the same you you can strain the array or the picture to a certain certain vertical slab and then within that it's the the pole that sticks up the most so as a human it's obvious in the small example what the maximum would be and where it is okay okay so as before that's just the definition and I'll point out again for for this picture I'll flip the notion of Min and Max just to make it nicer to draw okay here it

2:16 is for uh the overall task we'll pre-process the the answer to um the array to get a faster answer now the cartisian tree um results as follows you have a root note at the overall maximum that's this position in in in our example and then that basically splits the problem into two halves maybe everything to the left and everything to the right in this case the to the right part is tiny but um in general it's it's two parts and then you compute recursively the same cartisian Tree on these two sub problems and make them so there's some sub problem tree coming here and okay let's make this a bit nicer uh there's some sub problem sube coming from this coming from this and you append those as the left and right child of this root node okay again in nice if I take everything to the left of that node the next large is this element so that becomes the root of another cartisian tree a sub tree and it it becomes the left child of the overall maximum and similar on the right well there's just a single element so it's a just a single Noe but it becomes the right child of the root now we further split up things so there's the range between those two and

3:55 there's the range left of this guy so in general we will always have ranges that are from some previous node to some other so between two poles and on those we recurse so here again if I let this largest element between those two is this so that becomes the next node largest element in this range is that one so that becomes the next node one more time largest element to the left of that node is that largest element between those two is this one between those two is this one I guess you you get the picture now so you recursively refine the range and always the maximum becomes the next node that you connect to what you've already constructed okay awkward definition why do we do this okay uh that's just take an an array of numbers and Define a binary tree somehow but was why is that any good the reason is that there's a connection between this and finding the range maximum and so that connection is if I have a range I can find the notes in the tree that correspond to the leftmost and rightmost entry in that range um I didn't comment on this earlier in this in this tree I've not I've labeled every note with its in order rank or with its its position from

5:28 left to right right so we have zero one two three four five six seven so I'm just sliding a line left to right over this over this picture and assigning consecutive numbers this happens to be the same as the index of the array element that the pole represents so if I want the range from six to 14 I just find the notes labeled six and 14 in my picture now the range maximum always is is the lowest common ancestor of those two nodes in the tree and why is that well uh from each of these nodes we have to have a path to the overall maximum if the overall maximum is within that range then it surely is the maximum in the range the other option is it's outside of the range but then because this is a binary tree there must be some note where we split the path where one part of the path continues to go to six and the other continues to go to 14 so there must be some note in the range between those two where the path split and that note when that was generated it was to the left or to the right of the overall rout or recursively was between two large things that are outside of the

6:58 range and then this was the first element in the range that was uh assigned assigned a node or the other the other way to say it um the pass of these two nodes they split at the earliest thing that is well they split at the the highest pole that's between those two because afterwards they will never be in the same sub problem so if you have if you have this range uh at any point in time contained in a larger range for example this one then either six and 14 stay on the same side of the large Pole or they're separated now and for

7:51 good so that connection uh is acute is a acute observation um and it goes a little further so you don't actually need the the poles anymore all you need is the mapping from the array indices to these to these nodes so you can find what are the nodes that correspond to the leftmost rightmost position and then you can find the lowest common ancestor from those and that even works if you rearrange how well the y-coordinate of the nodes in this case it was still reflecting the values in the array but all we're doing is looking at the in order index of a node and finding lowest common ancestors none of that uses the y-coordinate so it also works if you just draw the tree in a in a standard way here like a the y-coordinate is just the depth in the tree so all that's all that's needed to answer range minimum queries is this binary tree we don't need any values in the array

9:11 uh let's see if that if that is clear enough uh so here's a little um cartisian tree and I haven't shown you the array that goes that could go along with

9:27 it and are we one based or zerob based it's always zerob based right for so there's several steps now um maybe one good in between thing would be how do I get these numbers uh here I still have them how do I get if I just have the tree as the usual pointer structure and so on how do I get these numbers inside the nodes I can do that with an inorder traversal which looks as follows I start at the root and then um at each note I first process the left sub tree then I assign the value of the root of the current node and then I process the other way around process the right subtree first left then myself then right that's in order

10:59 traversal so well say left self right and what does self mean self means I'm assigning myself the next free number let's do this um on here so I walk from the rout I first go left okay I arrive at a new node I first go left okay first go left first go left I always walk down left doing nothing now at this point there's no left so I come back from the empty left and now I assign the first number to this node okay so this gets the zero because I'm in the self part of treating this node then I go to the right sub tree that's empty2 so nothing happens and I then I return and now I walk back up now I've done for that note I've done the entire left sub tree so now is this guy's turn and it gets the number

12:11 one I'm done with the self part of that note so I go down to the right sub tree that again I go to the left empty come back now I assign the next free number which is

12:25 two and so on and so forth so here right is again empty so I come back right is done so I'm finished here now I come back for this note all the left sub tree has been dealt with so now it's the self part so I'm assigning this node the next free number

12:45 three now I go to the right sub tree but that's empty so I come back immediately go back up I've done with the whole left sub tree of that node so guess what's coming next it gets its number which is

12:59 four now I'm going to the right side sub tree okay I arrive at a new node again first thing we do is go left so we go left there's no left here so that one is treated next it gets the next free number number five okay so you keep keep going like

13:20 this if we do the same in this picture walk down walk down the dash line walk down walk down walk down until you can no longer then you return from the left so this guy gets the first index one a zero nothing in the right so we come come back up to this

13:53 uh let me finish drawing this path around the tree and then we'll just follow it so we're we're at this point we're dealt with the left done with the left sub tree so this gets assigned a number we go to the right sub tree there's nothing on the left now is the self part two nothing on the right so we come back up this has all the left dealt with so the next is assigned to three then we go to the right and if you keep assigning the indices with this you get these labels for the noes so that also means you can project this down to the array entries

14:30 so there's 0 1 2 3 four five 6 7 okay what do we get for rmq 15 in this case um that's maybe the point where we can show the

14:57 answers there's various votes for various numbers and first step we have to do is we find one and five in the array that's the range that we're looking at the trouble is we don't have the numbers in the array so we cannot just use that information instead we have to use the tree so we go to the noes that have one and five

15:35 and we find the lowest common ancestor which is three that's where they split and so three is the answer because at position three there must have been the maximum here okay so this is the maximum if that's the cartisian tree even without knowing what the real numbers are and here's one concrete I mean I generated the example using using these numbers there's others that would have given the same tree if you look at the the range 15 then seven is the largest here and you can double check that you get the tree if you apply the construction from before with the poles and letting lines sink

16:22 down so there's that in nice again okay that was step one that's the cartisian tree uh all this means so far is if I have the tree I know for all the rmq queries I know what the answer is it's not necessarily fast to find it because I would still need to find lowest common ancestors and now we're running a little bit in circles in Unit 8 I told you ah you can you can do longest common Extensions by doing lowest common ancestors in the suffix stre but now you see you need low common ancestors to do rmq so it doesn't seem to go anywhere uh but bear with me for a bit here's a larger example if you just uh generate some random numbers uh but it's just a binary tree

17:22 really the second important ingredient is the following we can count how many different binary trees there are and we'll find that indeed many different arrays will lead to the same cartisian tree so if you just have your rmq GL rmq glasses on all from an array that everything you see from an array are the answers it gives to rmq queries then many arrays are equivalent they give the same answers to all rmq queries um because there's not enough cartisian trees to give different answers and given the cartisian tree all rmq answers are predetermined because all that you ever do is find lowest common

18:12 ancestors okay um so let's first count the number of binary trees if I have uh an an array of length n I'll have n nodes in this tree how many different binary tree shapes are there well you can uh you can look at small numbers for example for two notes a binary tree can look like this or it can look like this that's the only two options how many do we have with uh with three

18:53 nodes well there's the balanced one we have this this Cherry shape uh and then there's very various ways of unbalanced trees where it's essentially a straight line but it can be straight in different

19:10 directions and so it's overall five different options these are these are all possible options there's no other options so people have have studied this and it turns out you can precisely calculate how many trees you can get with n numbers that's the catalon numbers but this is not a combinatorics class so uh I won't go into this at all what's easy to see is an upper bound and that comes back to the compression unit what we can do is we can encode every binary tree with a certain number of bits and because there's only so and so many bit strings with a certain number of bits we get an upper Bound for the number of different trees that there could be because the encoding will be such that I can reconstruct the tree from it so more precise L

20:11 um we can encode a tree with two n Bits And then two to the 2 N is the number of different bit strings of length 2 N and uh each of those gives at most one tree so there's um at most so many different binary trees and what is the encoding look like is actually very simple uh you do a traversal of your tree similar as before so we do this kind of walk around the tree and uh whenever I visit a node first I store whether it has a left and whether it has a right child with two bits right so I'm I'm using two bits per note so for each note I store whether it has um a left and a right child but just using one bit each so this note would be uh and I'm following this so this one note would be be one one because it has both a left and a right child this next node would be another one one because it has both children and this one too but this one would be a z0 because it's a leaf and this one's also a

21:27 z0 and then this one is more interesting it has has no left child so zero but a right child 01 that's a 0 0 again and 0 0 and I would encode these in the order I find them following the orange line so it would be one one one one one one 0 0 0 0 0 1 0 0 0 0 the question now becomes how can I decode the tree again that sounds sounds tricky but it's it's always possible and

22:07 uh stay where you are to uh to convince you let me go to new page and you can rely on my poor memory that I can't memorize what the tree looks like and I won't cheat so you start at the beginning you have two bits and they say there's a root and it has both children because this one one that means the Orange Line continues to the left and there's another node okay also has both children so the Orange Line continues further here again we have one one so I'm I'm here now now I'm seeing two zeros so the next thing I'm doing has no no children it's a leaf but then the Orange Line knows this is the next one we decode that's another Z 0 so there's no no children then the orange line continues back up here to the next dangling Edge and that's a 01 so it's a node with no edge here but an edge here that means Orange Line continues down here and the left two thing last two things is again append two more leaves okay and so if you check that's that's essentially the same tree it's just drawn slightly uh slightly deformed but the same parent child relations so we can encode a binary tree with two end

23:30 bits amazing but how does that help