Video 6-8: Succinct Trees

0:05 we continue our high level high alitude overview of some more succinct data structures. Uh there's two more I want to briefly discuss and um these are for trees. Uh where again this is on the one hand using things we've seen before as you'll see in a second and again will be a building block for other things to build. And specifically what we'll look at is the types of trees. They're known as ordinal trees. So for example, let's draw um a few small ones. These are all the trees that consist of of rooted trees. Um so I have a a specific designated root node. Um and the children are ordered. That's where the or null I guess comes from. H and they can have an arbitrary number of children. And in principle we only care about the shape. There may be labels associated to the nodes but these can be stored separately. So what we focus on for this data structure is just unlabeled trees.

1:05 So how can trees with two nodes look like? Well, if it's if it's supposed to be u a single tree, then I guess we can only do this a single root with a single child. How about for three nodes? Well, clearly I can always build this chain. But here I also have this other option of making a a binary node. But that's all. Um for four I start to get a few more. I can always do the extreme cases. And then one guy with uh with these. Now I can also do um a binary tree um a tree with a binary node at the root. And because the tree is ordered, this is a different tree from this one where the second child has a second has another descendant. Uh I think these are all four options, right? Uh of course examples that um have roughly this this kind of shape usually with some labels uh abound. Um XML documents are essentially trees.

2:19 Maybe you haven't thought of them that way, but they have this nested structure, right? So, you have uh some tag, then maybe there's a child, and then you have some text, and then you have the closing tag for that child. Maybe you have another child.

2:45 And at some point, I have to close tag. So I can view this as a tree where tag is the root and then I have child and child and note I can have any number of children and they're precisely have an order left to right. So this matches precisely our definition apart from the labels. The labels are on top. So I would store them separately. Uh you can also use minimum spanning trees. If you use them for routing then they have an embedding in the plane. Whether they are rooted is maybe debatable but if you store them I guess they become rooted. Another is if you have a a stochastic uh contextf free grammar or uh I think if you want to parse them efficiently it better be contextf free then you can represent the string as uh a parse tree in that grammar. So, um I don't know, maybe you have a a contextf free grammar. An expression is either an expression plus another expression or it's an expression times another or it's a term and maybe a term can be replaced with a variable or uh some constants. I don't know. Let's make this tiny example or empty. Uh we also need to terminate at some point. I think I can I can just build T's. So I could I could say um I start with an E and that becomes open E plus E close. And then these become a t and these become an x.

4:37 So I can uh write x plus x and always have this parenthesis around. So clearly I could store this string open x + x close. But sometimes it's convenient to store this tree or one it might compress the string. That's one application. Or it might be convenient to do operations on the expression and keep that in in a parsed form.

5:08 uh it's another application maybe I didn't make too clear why but uh that's another option so let's try to store these succinctly what does that even mean first of all we have to count how many such trees there are to know what the information theoretic lower bound let me cheat before I give it away. the um the answer this is a classic combinatorial object um and we'll not completely rederive it. It turns out it's much cleaner if you instead count forests of such trees.

6:19 So again, still ordinal forests. So the forest has an order left to right and otherwise each of the trees is an ordinal tree. So you could think of having a dummy route connected to all your forests and then it is again a tree. Here's the real trees.

6:43 Maybe that's uh what they look like. Okay. Now if you symbolically write what is the the class of all such trees? Well, it's um some first tree and a collection of more trees. And what is that? That's just another forest.

7:13 And of course a force could also be empty. That's the other option though nothing. I don't know. Let's write epsilon for Um and also a tree. A single tree is one root with a forest attached.

7:36 I'm just drawing this somewhat pictographically. Maybe you'll see in a second why that makes sense. So let's say um CN is the number of forests Then we can set up a recurrence for this uh by splitting off how many elements I have in the first tree.

8:15 I can have anything between one and everything in the first tree. Now the first tree looks like this. So it's a dummy root and a forest below. So I burn one of the nodes for sure for the root. And then I have as many options as I have forests for the rest of the sub tree, the first one. Um, that's the number of choices for the first tree.

8:48 Now I have to multiply that with all possible options of the remaining part of the forest. And that's another forest of n minus k nodes. And you can set some boundary conditions from what we've already uh worked out. So I guess with a single node there's a single forest.

9:19 Okay. Uh it turns out this recurrence I mean it looks a bit beastly and there's there's clever and and cute um derivations but this is really combinatorics so uh let me not do that but surprisingly it solves to um a very clean closed formula and these are known as the Catalan numbers.

9:53 So for example um if we calculate C2 that's a third of 4 choose 2 that's 4 * 3 / 2 right so six and that's two now how many forests are there with with two nodes I can a single tree of that shape or I can have the two single node uh trees. So that checks out. If it works for n equals 2, I guess it's correct for everything. You can prove by induction if you want. Okay. Um it turns out this also counts the number of binary trees on nodes. It's the same. And there's a bjection between those two with this um first child next sibling mapping. So uh again this is more combinatorics than anything else.

11:11 basically um you take your forest and you map it into a binary tree by putting a root and then uh if this forest looks like a t1 and then a remainder t2 onwards the first tree here and the construction that Well, so you can uh kind of embed embed your original trees as binary trees and vice versa if you've seen that before. Now, we don't really need this. Um what we use is just this counting fact and again combinotaurics uh cute cute proofs but let's um make uh progress on the data structures. Fine. So what does that mean? uh that's not a very convenient number to work with. Now you can approximate this um with sterling's formula and very very approximately this is 4 to the n and then divided some divided by some polomial factors.

12:54 And if you take the log of this that means we by and large want to use two n bits. Okay. So it's it's roughly 4 to the n otherwise known as 2 to the 2n and the logarithmic part here is a minus log n that we may uh choose to ignore. So the lower bound is asmtoic to 2n. It's a bit less. It's actually log 2 n minus some logarithmic term. But as a good approximation, we should use two bits per vertex per per note in the tree. Okay, that's not that much. Um, if you think about some normal tree representation, uh, we use much more I mean in the very least you would store maybe one parent pointer and so that's w bits each right or login bits say if the word size is login as we usually assume Well, let me let me say login pervertex, right? That's the usual per node. That's a lot more. We can't use pointers. We have to use something awkward and uh much more compact.

14:39 So, let's try with individual bits. Let me also foreshadow maybe um the whole list of operations one might be interested in asking about a tree. I don't know if you can even read the list. Uh the reason I'm giving the full table is that there's data structures known that get this with two n bits and can support all these operations in constant time. Uh some of these operations are are really even rather uh rather tricky to to dig through the definition even. So you can ask for the root of the tree. Fine. You can ask for the first child or iterate through the siblings. You can go to the parent. You can ask if something is a leaf. Um we can map node vert nodes in the tree uh to some first integer between one and n. Uh we can ask all sorts of things about the sub trees. How deep is the node? What's it the height of its subree? The number of things in so a lot of queries almost any question you can uh imagine that would could be useful is supported with the cleverest of these data structures.

16:18 I'm mentioning the term tree covering here. I don't know if you can read this covering. Uh because you you're not recovering from the cover of the slice. At least the the sketch.

17:00 Now let's uh let's first start with the simpler version though with a simpler data structure to give you a flavor of how these might work. Um and also fair to say that tree covering in the pure original form um may not be very practical because the constants in this little O become fairly fairly high. Uh instead we'll look at a a simpler way to represent trees that supports a subset of the operations.

17:50 I think it basically supports the the first and third group. So we can navigate locally to parent and children um and even access the the E child in one go. But that's largely it.

18:19 So how does that look like? Um let's look at some small example tree and um we'll not go through the full construction of all the operations but I want to give you some some hint of what it looks like.

18:39 So, say here's an ordinal tree with a bunch of nodes. Okay, maybe uh that's big enough. Uh the idea of louds, the name says what we're supposed to do. This stands for level order What does that mean? Well, level order is level by level through the tree. That's how the notes are already numbered. and uh one comes first because it's at the top level. And then um I'm going level by level through the nodes and for each um for each node I'm now going to write uh its degree in unary. So this first one has three children. So I'm going to write three ones followed by one zero.

20:03 Now the next one and let me to be to remain a bit sane let me underline where these bits come from that these are from the first node. Now the data structure will not need this but I think to work with it we will. The node two has two children so it is a one one and then zero.

20:33 And guess what? How we'll represent this bit sequence. Yeah, that's going to be a bit vector. So four has no children. So this is zero ones and just a zero. And then we continue with five and six and seven.

20:59 eight is a zero and nine is a zero and 10 is a zero. Uh let me try to also write in small uh the indices of this bit vector. Um okay. Now, uh there's a couple of things that we have to um talk about. First, this is just a bit vector. How am I going to talk about nodes? Let's let's try some some um simplest operation.

21:49 We want to find the parent of a node. For that, I need to write down the par the node that I want to find the parent of. What do I give as B? I don't have a an object. So, we need to define what a node looks like. So, notes here.

22:10 And this is really a definition uh are given by the starting position of their representation in the bit vector and let me just say their unary degree sequence their uts that's where they what they're represented with. So for example our node five this guy corresponds to 11 just as an integer. Okay. So I could ask what's the parent of five? Then I would have to ask what's the parent of 11 and we know this is two. Now I have to write parent of 11 for that. And what we expect the answer to be is the representation for two which is four. That's the starting position of the representation of node two. Okay. This is just a convention um uh that that seems to be a bit more convenient. So it seems before we can even work with these nodes, we may want to have a way to map between these internal this internal representation just some indices and the numbering from the outside.

23:38 And that's what these um these operations up here node map and node select are used for node map. um node map is given an index and is supposed to return the original name for this node. So we would want node map of 11 to return five.

24:19 So how could I get there? um the 11 is the starting position of that node. Now how can I get back to the representation of the nodes? The first important property of this louds representation is that I have exactly one zero bit per node and in the order of the level order. So um this position 11 in a way corresponds to the right node. I just have to count the number of zeros that are before. Then >> It's in the correct order. So, um the representation follows the level order.

25:08 So, right. Um let me and then you wrap around to the next level. You produce the level order by going level by level from left to right and in that's the order in which I write down the nodes and number five here means this was the fifth note that we wrote down in the bit vector and every node has exactly one zero so to the left of this representation or five I'm going to find one less zero So then my label right I want to uh for note map I want to use need a name for this let's call it L for for louds on this I call rank for the zero and I put in this V itself that's the starting index and remember my rank was defined to exclude the position I put Okay. Uh, and then I add one because I'm always um skipping myself. I'm querying before my representation. Okay, that's how I get from 11 to five because there's four zeros before me and I add one.

26:32 Now I can also do um the other direction uh node select sorry node select is the inverse operation. I want a certain uh index say I and now I want the internal representation and of course that's just the opposite. I'm doing a select query.

27:10 Now again, it's more convenient to select the zero before and then add one. So we select I minus one and then add one for the one position to the right. So you see how with rank and select we can puzzle ourselves uh together between operations between these two operations these two representations.

27:36 Let's um try to finish the uh operation parent. For that you need to really um use the properties of this louds. Where does my parent get stored? And uh in in particular from the five to the two there could be an arbitrary number of other things in between here right and this I I don't really know now uh let me maybe change my mind instead of five let's look at six it's a slightly less degenerate case so uh six is 12 it's otherwise the same the parent is the Okay.

28:18 So note that um all the nodes here to the right of the six uh are after after this position 12. And then there's a number of nodes to the left of this. These are um kind of before before the representation or six.

28:35 um all of the edges that lead down uh stay in the left to right order. So if I know that six here is the second node on this level, my parent is the one that has the second downgoing edge in that level.

28:57 Um so maybe as a second example we could look at the parent of of eight. Right? This is counting from the left the 1 2 3 fourth note on that level. So the 1 2 3 fourth child edge from the previous level is the one that I care about.

29:23 Now how do I know uh where the previous level was and even how many edges there are? So the key property for that is to observe that in louds and um I'm going to borrow our picture.

30:22 The key property that we're going to use for all these operations is that the way it's constructed the i one from the left and the i zero from the left are precisely the start and end point of one parent child edge. Let's try to do this for this edge from 3 to 8. Um, this corresponds to the 1 2 3 4 5 6 7th edge counting in level order. So, it should start at the seventh one and end at the seventh zero. 1 2 3 4 5 6 7. That's the one where it starts. And it ends at the seventh zero. 1 2 3 4 5 6 7 which is this one. Um 1 2 3 4 5 6 7. Did I uh one two three four five six Something's off right. I wanted the edge to eight.

31:47 Yeah, three is the parent. That that part's right. Um but it's the second edge from here, so it should match the second edge as well. Well, let me maybe uh mark the others.

32:02 Uh I think I'm off by one. It's it's not true as written here. Um because clearly these first ones the the first zero is out of the game. So uh this should be the i + first.

32:27 And the reason is that the um the root is special right the root doesn't have an edge. So this one this first zero we have to kind of uh uh ignore in the counting. Apart from that it's it's correct. You get this one is the first edge the starting edge of the first edge. Ignoring that first zero it leads to this zero.

32:55 So let's try to get okay zero is also gone. Good. Then the eighth zero is this one one further to the right and that is this edge. Okay, good. We double checked. But the pattern the the systematic pattern exists. It's really just the route that uh disrupts the counting a bit. And of course you might uh want to tweak the bit vector to avoid this corner case.

33:25 How can we find the parent of a node then? Well, uh if we're sitting at node six, we know um that there's six zeros before me including myself or five if I'm taking the rank from my position.

33:46 And I want the uh I + one that corresponds to that. Sorry, the I minus five zeros before me. I am the sixth zero in the total bit vector. Then um I + 1 is six. So I want the fifth one from um the beginning. And the fifth one is in my parent.

34:19 [snorts] So for parent we should do uh Now we're already given the position. So let's write this as an algorithm. This gives me the number of zeros before me.

35:03 Then I'm going to find the position of this of the one that is at the i minus first one. So again here uh we had the example of node six. So position 12. The number of zeros before then is 1 2 3 4. Now I want the uh the third one.

35:32 That gives me this one. No, I want the I think my minus the plus one. That's missing. That is my number. That's the I. So we're at six. And now I want the one less from that eye. So the fifth one that gives me this one.

36:02 And now I'm sitting in the representation of my parent. But the parent itself I want to be rounded to the next 0 + one. So this is the intermediate.

36:17 Uh uh my parent will be the node W. So I I'll take to get from this position in here. Um I'm doing one I'm getting to the previous zero.

36:38 Let's write it like this. And previous zero um you could build from select and rank. Right? This is uh select zero of rank zero of the same position and then I add plus one then I'm at the starting position of my parent.

37:15 So you see the uh fiddling out the details is almost something you would want to do in a program and on examples where you can double check. But by and large um it all circles around this this property that there's the edges in the tree preserved in the relative order of ones and zeros. And so you can navigate say to your parent using this. You can navigate to your children by using the edges in the other way around. you know where you're sitting in the bit vector. And if you want your first child, you go one position to the right. That's a one. So you can count with rank how many ones are to the left. And then you go to the appropriate zero. And that's the child that you want. Okay.

38:06 Now because my um my convention with what rank and select mean are slightly different I can't copy the code from Navaro's book. I'll link it on on the website. There's full details for all the operations given but with a slightly different um convention for what rank and select do. So I think it's more confusing to look at that. Now um let me just list that the operations of um first child I think it's just called fch child in the table last child and accessing a child by index. Okay, just child vt.

39:08 And what else? Okay, we can go to the next sibling and the previous sibling. All of this is kind of similar. And we can also list the number of children.

39:24 This we could also call the degree. All of these operations can be worked out with the same uh kind of reasonings as we've done for parent. However, it seems that certain things are not easily possible. for example, um I mean it's always hard to say that this is not possible, but it is indeed not known how to support how many nodes are in the sub tree below a node or how deep in the tree, what's the distance from the root?

40:17 and a whole collection of other operations. Um for this it just seems that this uh loud representation is is not convenient. We don't know how to do it without.

40:33 So there is another uh alternative entirely different approach closer to how we solved originally for the bit vectors to build indices. Uh and that's called tree covering. Um the idea is that you have an overall tree where each node actually stands for a mini tree and each mini tree again has nodes that stand for micro trees. There's a you have this three-level decomposition that we've seen for bit vectors. Now here within the micro trees we have actual nodes that's the end of the recursion and we make these so small by so if they have one quarter login nodes the number of different micro trees is four to that power which is uh roughly um square root n and that means again we uh we can store these is all in the lookup table.

41:48 Uh the other sizes are chosen so that here um you have a lot of nodes in this overall tree but you reduce their number by a log squared n which means for each of these nodes you can store login bits easily without being uh non not succinct.

42:27 or well the the nodes in the overall tree are the mini trees, right? Um then the mini trees have have uh roughly log nodes. So their number will be n divided login.

42:56 So we can no longer store login bits but we can store some double log that's fine to store for each of the blue nodes. And then for the micro trees we use exhaustive lookup tables.

43:32 So I think up up to this level of abstraction maybe it's conceivable that you could build something like this for example um you could say I can I can try to build an operation for the depth of a node um by uh how do I get the depth of some node B somehow from V from the representation I need to know in which micro tree it is and for that micro tree in which mini tree And for that mini tree where in the global tree it is then my depth will be the depth in the global tree I can store that because that's one number for each of these green vertices login bits each fine to store okay then for each of the blue nodes I store local to the mini tree how deep am I that's log login bits and then within the micro tree locally I can again store how deep I >> So I store the depths sorry of mini tree roots. I should have said these we store in in absolute numbers.

45:05 Micro tree roots is relative to the mini tree. And for the micro trees within micro trees I have the depth uh in the lookup table.

45:25 So I can combine this these three numbers and thereby get the depth of any node. Now for some other operations um it turns out it's a bit more tricky and indicative is maybe the subree size. So this is kind of fine. Think about how we would do subtree size. How many nodes are below me?

45:52 We could try the same scheme, right? I could store uh for each mini for each of these green trees, I could store how much is below me. I could store for this for this guy how much is below me. Uh but how about these? There might be nodes where an entire subree is omitted.

46:10 I can store for the blue guys. I only have space to store something that's local to the green bubble. I cannot afford to store login bits each. And so if I'm not careful, I might have many of these omitted sub trees and I would have to store all of their sizes and somehow puzzle together the sub tree sizes from that. So at this point it starts to matter how you break your tree into these bubbles. That's the point. And there's been um a sequence of papers with ever more clever and sophisticated schemes how to do that. Uh and the ultimate answer is is this by uh Parsan and Monroe uh which is is a relatively simple recursive algorithm. It it works bottom up from the leaves back up to the root and has a certain rule how to deal with um the different cases. And at this point I'm I'm not even going to explain how the algorithm works. Uh what it does is um it breaks an arbitrary ordinal tree into certain uh trees of a given size. It's a parameter. you tell me how big the components are allowed to be.

47:19 And they have this um this property even for any kind of ordinal tree. Any component has maybe a root component where it connects to the rest above it. It may have to the left and to the right from its um same same root node. A node can have an arbitrarily large degree an arbitrary number of children. So I can never fit all the children in one small component. There may always be too many. So I have a list to the left and to the right where I'm I'm conceptually extending the child list of my root node. And I have a single sub tree that is omitted. I never need more than that. And here's some example. That's that's the overall tree. And the colors show you the components. And here is shown how these components connect. And for example, you see that here this um this root is duplicated in these two components. There's two of the first two children are part of this component and then the second two are part of this component. And there's one child edge that's omitted from this subree which is uh to be inserted in at this position and because it's a single one you can remember where it connects to etc.

48:41 Now this gets horrendously complicated because you need to do this for two levels. This is one decomposition. You need to do this at mini tree level and at microtree level. And then for each of the operations you can somehow store the right amount at each level and puzzle together all the operations. Um and that allows you to support all all operations in that table. In particular, you can do sub tree size now. Um because you have only this one omitted thing, you can precisely tell where it connects into the tree. And so you store this this sub tree size uh once or you can look it up from from the this child component and you know exactly which nodes need this uh added to their subree. All of these I can locally check they're not above this node where the sub tree is emitted. So I don't add it. Well is a A long case distinction.