# 9. Augmentation: Range Trees

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=xVka6z1hu-I
**Transcript page:** https://www.withtranscript.ai/video/xVka6z1hu-I

## Chapters

- 0:00 — Chapter 1 (0:00)
- 1:21 — Chapter 2 (1:21)
- 2:42 — Chapter 3 (2:42)
- 4:47 — Chapter 4 (4:47)
- 7:33 — Chapter 5 (7:33)
- 9:50 — Chapter 6 (9:50)
- 11:26 — Chapter 7 (11:26)
- 13:11 — Chapter 8 (13:11)
- 17:16 — Chapter 9 (17:16)
- 19:55 — Chapter 10 (19:55)
- 21:41 — Chapter 11 (21:41)
- 23:50 — Chapter 12 (23:50)
- 25:31 — Chapter 13 (25:31)
- 27:28 — Chapter 14 (27:28)
- 28:54 — Chapter 15 (28:54)
- 30:47 — Chapter 16 (30:47)
- 32:16 — Chapter 17 (32:16)
- 35:09 — Chapter 18 (35:09)
- 36:44 — Chapter 19 (36:44)
- 40:06 — Chapter 20 (40:06)
- 40:55 — Chapter 21 (40:55)
- 45:37 — Chapter 22 (45:37)
- 47:15 — Chapter 23 (47:15)
- 50:31 — Chapter 24 (50:31)
- 53:25 — Chapter 25 (53:25)
- 54:40 — Chapter 26 (54:40)
- 57:06 — Chapter 27 (57:06)
- 59:32 — Chapter 28 (59:32)
- 1:02:01 — Chapter 29 (62:01)
- 1:03:03 — Chapter 30 (63:03)
- 1:04:06 — Chapter 31 (64:06)
- 1:04:48 — Chapter 32 (64:48)
- 1:07:30 — Chapter 33 (67:30)
- 1:09:00 — Chapter 34 (69:00)
- 1:10:35 — Chapter 35 (70:35)
- 1:12:43 — Chapter 36 (72:43)
- 1:14:17 — Chapter 37 (74:17)
- 1:16:57 — Chapter 38 (76:57)
- 1:19:38 — Chapter 39 (79:38)
- 1:24:00 — Chapter 40 (84:00)

## Transcript

**[0:00]:** The following content is provided under a creative commons license. Your support will help MIT Open Courseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT Open Courseware at ocw.mit.edu.

**[0:21]:** All right, let's get started. Today we have another data structures topic, which is data structure augmentation. The idea here is we're going to take some existing data structure and augment it to do extra cool things. So

**[0:46]:** take some other data structure that we've covered. Typically that'll be a balanced search tree like an AVL tree or a 2-3 tree.

**[0:59]:** And then we'll modify it to store extra information which will enable additional kinds of searches, typically. And sometimes to do updates better.

**[1:21]:** And in 6 you've seen an example of this where you took AVL trees and augmented AVL trees so that every node knew the number of nodes in that rooted subtree. Today we're going to see that example, but also a bunch of other examples, different types of augmentation you could do. And we'll start out with a very simple one which I call easy tree augmentation

**[1:48]:** which will include subtree size as a special case.

**[1:57]:** So with easy tree augmentation uh, the idea is you have a tree, like an AVL tree or two-three tree or something like that, and you'd like to store for every node X some function of the subtree rooted at X, such as the number of nodes in there or the sum of the weights of the nodes or the sum of the squares of the weights or, uh, the min or the max or the median maybe, I'm not sure. Uh, any some some function f of X, which is a function of that. Maybe not f of X, but we want to compute uh, store some function of that subtree.

**[2:42]:** Say the goal is to store f of the subtree rooted at X

**[2:57]:** uh, at each node X in a field which I'll call X dot f. So, normally nodes have like a left child, right child, parent, but we're going to store an extra field X dot f for some function that you define. This is not always possible, but here's a case where it is possible. This is going to be the easy case. Suppose X dot f can be computed uh, locally using lower information, lower nodes.

**[3:47]:** And we'll say let's suppose it can be computed in constant time from information in the node X uh, from X's children and uh, from the f value that's stored in the children. I'll call that children. f, but really I mean left child. f, right child. f, or if you have a 2-3 tree, you have three children potentially and the .f of each of them. Okay, so suppose that you can compute x.f uh sort of locally just using one level down in constant time. Then as you might expect, you can update whenever a node needs whenever a node ends up changing. uh so more formally if some set of nodes change

**[4:47]:** call the set S.

**[5:17]:** uh So uh I'd staying a very general theorem here. If there is some set of nodes which we change something about them we change either their f field, uh we change some of the data that's in the node, or we change we do a rotation, move some nodes around then we count the total number of ancestors of these nodes. So this uh subtree those are the nodes that need to be updated because we're assuming we can compute x.f just given the children data. So if these if this data is changing, we have to update its parent's value of f because it depends on this child value. We have to update all those parents all the way up to the root. Okay, so however many nodes there are there, that's the total cost. Now, luckily, in an AVL tree or 2-3 tree, most balanced search structures, the updates you do are very localized.

**[6:20]:** Like when we do splits in a 2-3 tree, we only do it up a single path to the root. So the number of ancestors here is just going to be log n. Same thing with an AVL tree. If you look at the rotations you do, they're up a single leaf-to-root path. And so the number of ancestors is that that need to be updated is always order log n. Order log n things change, and there's a order log n ancestors of them. So this is a little more general than we need, but it's just to point out if we did log n rotations spread out somewhere in the tree, that would actually be bad because the total number of ancestors could be like log squared. Right? But because in the structures we've seen, we just work on a single path to the root, we get log n.

**[7:33]:** So in a little more detail here, whenever we do a rotation in an AVL tree,

**[7:49]:** uh let's say a b c x y Number of rotations. It's been a while since we've done rotations. Uh so we've we've we haven't changed any of the nodes in a b c, but we have changed the nodes x and y. So we're going to We would have to trigger an update of y. First, we'd want to update y.f. And then we're going to trigger the update to x.f. And as long as this one can be computed from its children, then uh then we compute y.f., then we compute x from its children. Right? So a constant number of extra things we need to do whenever we do a rotation. And because the rotations lie in a single path, uh total costs that that you know once we stop doing the rotations uh in AVL insert, say, then we still have to keep updating up to the root.

**[8:46]:** But there's only log n at most log n nodes to do that. Okay, same thing with uh with 2-3 trees. We have a node split. So we have I guess three keys, four children. That's too many. So we split to uh two nodes and an extra node up here. Uh, then we just trigger an update of this f value and update of this f value and an update of that f value. And because that just follows a single path, everything's log n. Okay, so this is a general theorem about augmentation. Any function that's well-behaved in this sense we can maintain in AVL trees and 2-3 trees. And I'll remind you and state a little more generally what you did in 006 which are called order statistic trees in the textbook.

**[9:50]:** So here um we're going to Let me first tell you what we're trying to achieve. This is the abstract data type or the interface of the data structure.

**[10:03]:** Uh, we want to do insert,

**[10:07]:** uh delete,

**[10:11]:** and uh say successor searches.

**[10:16]:** It's the usual thing we want out of a binary search tree. Predecessor two, sure. We want to do rank of a of a given key, which is tell me what is the index of that key in the overall sorted order of the items, of the keys. We've talked about rank a few times already in this class. Depends whether you start at zero or one, but let's say we start at one. So if you say rank of the key that happens to be the minimum, you want to get one. If you say rank of the key that happens to be the median, you want to get n over two plus one and so on. Okay? So it's a natural thing you might want to find out. And the converse operation is select say of i which is give me the key of rank i.

**[11:26]:** Okay, we've talked about select as an offline operation. Given an array find me the median or find me the n over seventh rank item and we can do that in linear time given no data structure. Here we want a data structure so that we can find the median or the seventh item or the n over seventh key whatever in log n time. We want to do all of these in log n per operation.

**[12:05]:** Okay, so in particular rank of select of i should equal i. Right? We're trying to find the item of rank. So far, so good. Uh, and just to plug these two parts together, we have this data structure augmentation tool. We have this goal we want to achieve. We're going to achieve this goal by applying this technique where F is just the subtree size, the number of nodes in that subtree because that will let us compute rank. So we're going to use uh easy tree augmentation

**[12:56]:** with F of subtree equal to the number of nodes in the subtree.

**[13:11]:** So in order for this to apply, we need to check that given a node X, uh we can compute X.F just using its children. This is easy. Uh we just add everything up. So X.F would be equal to one. That's for X plus the sum of C.F for every child C.

**[13:41]:** I'll write this as a Python interpolation. So it looks a little more like an algorithm. Um I'm trying to be generic here. If it's a binary search tree, you just do X.left.F plus X.right.F, but this will work also for two three trees. Pick your favorite uh data structure. As long as there's a constant number of children, then uh this will take constant time. So we satisfy this condition. So we can do easy tree augmentation and now we know we have subtree sizes. So given any node, we know the number of children, sorry, the number of descendants below that node. So that's cool. It lets us compute rank and select. I'll just give you those algorithms quickly. We can check that they're log n time.

**[14:39]:** Yeah, so the the the idea is pretty simple. You have some key. Let's think about binary trees now because it's a little bit easier. We have some item X. It has a left subtree, right subtree. And now let's let's look up from X. Just keep calling X dot parent. So sometimes the parent is to the right of us, and sometimes the parent is to the left of us. Okay, I'm going to draw this in a kind of funny way.

**[15:18]:** But this funny way has a very special property, which is that the X coordinate in this diagram is the key value, or is the sorted order of the keys, right? Everything in the left subtree of X is has a value less than X. If we say all the keys are different. Everything to the right of X has a value greater than X. If the parent if X was the left child of its parent, that means this thing is also greater than X. And if we follow a parent and it was and this was the right child of that parent, that means this thing is less than X. So that's why I drew it all the way over to the left. This thing is also less than X cuz it was a I'll call it a left parent. Here we have a right parent, so that means this is something greater than X.

**[16:04]:** And over here we have a left parent, so this is something less than X. Let's say that's the root. In general, there's going to be some left edges and some right edges as we go up. These arrows will go either left or right in a binary tree. So the rank of x is just one plus the number of nodes that are less than x, number of keys that are less than x. So, there's these guys, there's these guys, and there's whatever is hanging off. Okay, here I've almost violated my x coordinate rule. If I make these really narrow, that's right. So, all of these things uh all of these nodes in the left subtrees of these less than x nodes will also be less than x. If you think about these other subtrees, they're going to be bigger than x, so we don't really care about them.

**[16:54]:** So, we just want to count up all of these nodes and all of these nodes.

**[17:06]:** So, the algorithm to do that is pretty simple.

**[17:16]:** Uh we're just going to uh start out with

**[17:33]:** I'm going to switch from this f notation to size. That's a little more natural and generally you might have many functions, so size is the usual notion for usual notation for subtree size. Uh so, we start out by counting up how many items are here, and if we want to start at a rank of one, if the min has rank one, then I should also do plus one for x itself. If you want to start at zero, you just omit that plus one. And then all I do is walk up from x to the root of the tree. And uh whenever we go left

**[18:19]:** uh uh from say x to x prime. So that means we have an x prime. Its right child is x and so when we went from x to its parent we went to the left. Uh then we say uh rank plus equals uh x prime dot left dot size uh plus one for x prime itself. And maybe there are maybe x x prime dot left dot size is zero. Maybe there's no nodes over there, but at the very least we have to count those nodes that are to the left of us. And if there are anything down here we add up all those things. So that lets us compute rank. How long does it take? Well, we're just walking up one path from a leaf to root or not necessarily leaf, but from some node x to the root. And as long as we're using a balanced structure like AVL trees uh I guess I want binary here.

**[19:19]:** So let's say AVL trees uh then this will take log n time. So I'm spending constant work per step and there's log n steps. Clear? So that's good old rank. Easy to do once you have subtree size. Let's do select for fun.

**[19:55]:** This may seem like review, but I drew out this picture explicitly because we're going to do it a lot today. We'll have pictures like this uh a bunch of times. Really helps to think about where the nodes are, which ones are less than x, which ones are greater than x. Okay, let's do select first.

**[20:13]:** This you might not have seen in 006.

**[20:19]:** So we're going to do the reverse. We're going to start at the root and we're going to walk down. Sounds easy enough. Uh but now walking down is kind of like doing a search, but we don't have a key we're searching for. We have a rank we're searching for. So uh what is that rank? Rank is i. Okay. So uh on the other hand, we have the node x. We'd like to know the rank of x and compare that to i. That will tell us whether we should go left or go right or whether we happen to find the item. Now one possibility is we call rank of x to find the rank of x, but that's dangerous uh cuz I'm going to have a a for loop here and if ev and it's going to take log n iterations. If at every iteration I'm computing rank of x and rank costs log n, then overall cost might be log squared n.

**[21:13]:** So I can't afford to I want to know what the rank of x is, but I can't afford to say rank open paren x cuz that recursive call will be too expensive. So what is the rank of x in this case? This is a little special. What's that? Number of left children Number of left or the size of the left subtree plus one. Yeah.

**[21:41]:** Plus one if we're counting starting at one. Very good.

**[21:49]:** Slowly getting better. Didn't hit anyone this time. Okay. So at least for the root, this is the rank and that only takes us constant time in this special case. We'll have to check that it still holds after I do the loop, but it will. Uh so cool. Now there are three cases. Uh if i equals rank, if the rank we're searching for is the rank that we happen to have, then we're done, right? We just return x. That's the easy case. More more likely is that I will be either less than or greater than the rank of x.

**[22:28]:** Okay. Uh so if I is less than the rank, this is for the easy, we just say uh x = x dot left.

**[22:40]:** Uh did I get that right? Yeah. Um in this case the rank So here we have x. It's at rank rank. And then we have the left subtree uh and the right subtree. And so if the rank we're searching for is less than rank, that means we know it's in here, so we should go left. And if we just set x = x dot left, uh you might ask, well what rank are we searching for in here? Well exactly the same rank. Fine. That's the easy case. Uh in the other situation, if we're searching in here, we're searching for a rank greater than rank, uh then I want to go right. But the new rank that I'm searching for is local to this subtree. I'm searching for uh I minus this stuff. This stuff is rank. So I'm going to let I be I minus rank.

**[23:37]:** Make sure I don't have any off by one errors. Yep, that's seems to be right. Okay. And then I do a loop. So I'll write repeat.

**[23:50]:** Uh so then I'm going to go up here and say, okay, now relative to this thing, what is the rank of the root of this subtree? Uh well it's again going to be that node dot left dot size + 1. And now I have the new rank I'm searching for I. And I just keep going. You could write this recursively if you like, but here's an iterative version. So it's actually very familiar to the select algorithm that we had. Uh like when we did deterministic linear time median finding or randomized median finding, uh they had a very similar kind of recursion. But in that we were spending linear time to do the partition, and that was expensive. Here we're just spending constant time at each node, and so the overall cost is log n. about that?

**[24:44]:** Okay. Uh, I have a note here, subtree size is obvious once you know that that's what you should do. Another natural thing to try to do would be to augment for each node, what is the rank of that node? Cuz then rank is really easy to find, and then select would basically be a regular search. I just look at the rank of the root, I see whether the rank I'm looking for is too big or too small, and I go left or right accordingly. What would be bad about augmenting with rank of a node? Updates. Why?

**[25:19]:** What's a bad example for an update? Yeah. Add a new minimum element. Right. Say we insert a new minimum element.

**[25:31]:** Good catch, cameraman. That was for the camera, obviously. Um, so right, if we insert uh, this is off to the side, but say we insert, I'll call it minus infinity, a new key that is smaller than all other keys, then the rank of every node changes. So uh, that's bad. Uh, it means that easy tree augmentation in particular isn't going to apply, and furthermore, it would take linear time to do this. And you could keep inserting, if you insert keys in decreasing order from there, every time you do an insert, all the ranks increase by one. Maintaining that's going to cost linear time per update. So you have to be really careful that uh, the the function you you want to store actually can be maintained. Be very careful about that, say on the quiz coming up, uh, that when you're augmenting something you can actually maintain it.

**[26:23]:** For example, it's very hard to maintain the depths of nodes because when you do a rotation, a whole lot of depths change. If your depth counting from the root, how deep am I? Uh, when I do a rotation, then this entire subtree went down by one. This entire subtree went up by one. In this picture. Uh, but it's very easy to maintain heights, for example. Height counting from the bottom is okay because I don't affect the height of A, B, and C. I affect it for X and Y, but that's just two nodes. That I can afford. Okay, so that's what you want to be careful of uh in the easy tree augmentation. So most of the time, easy tree augmentation does the job, but uh in the remaining two examples, I want to show you cooler examples of augmentation. These are things you probably wouldn't be expected to come up with on your own, but they're cool.

**[27:16]:** So um they let us do more sophisticated operations.

**[27:28]:** So first one is uh called level linking.

**[27:36]:** And here we're going to do it in the context of 2-3 trees, partly for variety. Um so uh the idea of level linking is very simple. Let me draw a 2-3 tree.

**[28:03]:** Not a very impressive 2-3 tree because I don't feel like drawing too much. Uh level linking is the idea of in addition to these child and parent pointers, we're going to add links on all the levels.

**[28:19]:** Horizontal links, you might call them.

**[28:54]:** Okay. So that's nice. Uh two questions. Can we do this and what's it good for? So let's start with can we do this? Um remember in 2-3 trees all we have to think about are splits and merges. So in a split we have for a brief period, let's say uh three keys, four children. That's too many. So we change that to uh uh hm. Yeah. I'm going to change this in a moment, but for now this is the split you know and love, maybe at least know. And uh if we think about where the level link pointers are, we have one before uh and then we just need to distribute those pointers uh to the two resulting nodes and then we have to create a new pointer between the nodes that we just created. This is of course easy to do. We're here. We're taking this node.

**[29:51]:** We're splitting it in half. Uh so we have the nodes right in our hands, so just add pointers between them. And key thing is there's some node over here on the left. It used to point to this node. Now we have to change it to point to the left version, the left half of the node. And there's some node over on the right. We have to change it's left pointer to point to uh this right half of the node. But that's it, constant time. Okay, so this is this doesn't fall under the category of easy tree augmentation because this is not isolated to the subtree. We're also dealing with its left and right subtrees, but still easy to do in constant time.

**[30:36]:** Uh merging nodes is going to be similar.

**[30:47]:** Uh, if we steal a node from our uh, parent then or from our sibling, nothing happens in terms of level links. But if we have say an empty node and a node that cannot afford any stealing, so we have single child here, two children, and we merge it into uh,

**[31:09]:** we're taking something from our parent, bringing it down, and we have three children afterwards. Again, we used to have these these level pointers. Now we just have these level pointers. It's easy to maintain. It's just a constant size neighborhood. Because we have the level links, we can get to our left and right neighbors and change where the links point to. So easy to maintain in constant time.

**[31:43]:** I'll call it constant overhead. Every time we do a split or merge, we spend uh, an additional constant time to do it. We were already spending constant time, so just changes everything by a constant factor. So far so good. Uh, Now I'm going to have to tweak this data structure a little bit, but let me first tell you why. What am I trying to achieve with this data structure?

**[32:16]:** What I'm trying to achieve is something called uh, the finger search property.

**[32:32]:** This is uh, So let's just think about the case where I'm doing uh, a successful search. I'm searching for a key X, and I find it in the data structure. I find it in the tree. Uh, suppose I found one I searched for X, I found it, and then I searched for another key Y. Actually, I think I'll do the reverse. I first I found Y, now I'm searching for X. If X and Y are nearby in the tree, I want this to run especially fast. For example, if X is a successor of Y, I want this to take constant time. That would be nice. Uh, in the worst case, X and Y are very far away from me in the tree, then I want it to take log N time. So how could I interpolate between uh constant time for finding the the successor and log N time for finding the uh worst case search.

**[33:28]:** So I'm going to call this search of X from Y, meaning uh this is a little imprecise, but what I mean is when I call search, I tell it where I've already found Y, and here it is. Here is the node storing Y. And now I want to I'm given a key X, and I want to find that key X given the node that stores key Y. So how long should this take? What would be a good way to interpolate between constant time at one extreme, the good case when X and Y are basically neighbors in in the sorted order versus uh log N time in the worst case. Yeah. The distance along the graph. Distance along the graph, that would be one reasonable definition. Um so I I have a tree, which you can think of as a graph, measure the shortest path length from X to Y, or or we have a more sophisticated graph over here.

**[34:29]:** Uh maybe that that length. The trouble with the distance in the graph, that's a reasonable suggestion, but it's very data structure specific. If I use an AVL tree without level lengths, then the distance could be one thing, if I use uh two three tree, even without level links, it's going to be a different distance. If I use a two three tree with level links, it's going to be yet another distance. So that's a little unsatisfying. Uh I want this to be an answer to a question. Uh I don't want to phrase the question in terms of that data structure. Yeah. Difference between ranks between x and y. That's close.

**[35:09]:** So I'm going to look at rank of x and rank of y. Let's say take the absolute difference. That's kind of how far away they are in sorted order. Do you want to add anything? Log. Yeah. Because uh in the worst case, the difference in ranks could be linear. So uh I want to add a log out here to get log n in that worst case. Add a big O for safety. That's how much time we want to achieve. So this would be the finger search property that you can solve this problem in this much time. So again, difference in ranks is at most n. So this is at most log n. But if y is a successor of x, this will only be constant and this will be constant. So this is great if you're doing lots of searches and you're always you tend to search for things that are nearby, but sometimes you search for things that are far away.

**[36:03]:** This gives you a nice nice bound. Uh so um on the one hand, we have this is our goal, log difference of ranks. On the other hand, we have the suggestion that what we can achieve is something like the distance in the graph. Uh but we have a problem with this. I used to think that data structure solved this problem, but it doesn't. Um so

**[36:34]:** I just draw Actually, I have a tree right there. I'm going to use that one.

**[36:44]:** Suppose uh x is here and y is here. Okay, this is a bit of a small tree, but if you think about it long enough, uh this node is the predecessor of this node. So their difference in rank should be one.

**[37:06]:** But their the distance in the graph here is two. Okay, not very impressive, but in general you have a tree of height log n. If you look at the root and the predecessor of the root, they will have a rank difference of one by definition of predecessor, but the graph distance will be log n. So that's bad news because if we're only following pointers, there's no way to get from here to there in constant time. So we're not quite there. Uh we're going to use a different another tweak on that data structure, which is uh store the data in the leaves.

**[37:52]:** Tried to find a data structure that didn't require this and still got finger search, but as far as I know there is none, no such data structure. So uh if if you've looked if you look at say Wikipedia about B-trees, you'll see there's a ton of variations of B-trees, B+ trees, B* trees. This is one of those. I think B+ trees. Um as you saw B-trees or 2-3 trees, every node stored uh one or two keys, and each key only existed in one spot. We're still only going to put each key in one spot, kind of, uh but it's only going to be the leaf spots. Okay, good news is most nodes are leaves, right? Constant fraction of the nodes are going to be leaves. So it doesn't change too much from uh efficiency space efficiency standpoint if we just put data down here and don't put I'm not going to put any keys up here for now.

**[38:45]:** Okay? Uh so this is a little weird. Let me draw an example of such a tree. So maybe we have two and five and seven and uh eight nine let's say. Uh, let's put one here. So I'm going to have a node here with three children, a node here with two children, and here's a node with two children. So I think this mimics this tree roughly. I got Oh, no, I got it exactly right. So here I've taken this tree structure. I've redrawn it. There's now no keys in these nodes, but everything else is going to be the same. Every node is going to have zero children if it's a leaf or two or three children otherwise. Never have one child cuz then you wouldn't get logarithmic depth. All the leaves are going to be at the same depth. Uh, and that's it. Okay, that is uh two-three tree with the data stored in the leaves.

**[39:52]:** It's a useful trick to know. Uh, now we're going to do a level-linked two-three tree. So in addition to that picture, we're going to have links like this.

**[40:06]:** Okay, and I should check that I can still do insert and delete into these structures. It's actually not too hard, uh but let's think about it.

**[40:30]:** Uh, I think actually it might be easier. Let's Let's see. Uh, so if I want to do an insert

**[40:41]:** uh okay, I have to first search for where I'm inserting. Uh, I haven't told you how to do search yet. Um, okay, so let's first think about search.

**[40:55]:** What we're going to do is uh data structure augmentation. We have simple tree augmentation. Um, so I'm going to do it and at each node, what the functions I'm going to store are the minimum key in the subtree and the maximum key in the subtree.

**[41:23]:** There are there are many ways to do this, but uh here I think this is kind of the simplest.

**[41:33]:** So, what that means is at this node, I'm going to store one as the min and seven as the max. Uh and at this node, it's going to be one at the min and nine at the max. And here we have eight as the min and nine as the max. Again, min and max of subtrees are easy to store. If I ever change a node, I can update it uh based on its children just by looking at the min of the leftmost child and the max of the rightmost child. Right? If I had to if I didn't know one and nine, I could just look at this min and that max, and that's going to be the min and the max of the overall tree. So, in constant time, I can update the min and the max of a node given the min and the max of its children.

**[42:18]:** Uh special cases at the leaves, then you have to actually look at keys and compare them, but leaves only have at most two keys, so pretty easy to compare them uh constant time. Okay. So, that's how I do the augmentation. Now, how do I do a search? Well, if I'm at a node and I'm searching for a key, uh well, let's say I'm at this node. I'm searching for a key like uh eight. What I'm going to do is look at all of the children. In this case, there's two. In the worst case, there's three. I look at the min and max, and I see where does eight fall? Well, it falls in this interval. If I was searching for seven and a half, I'd know it's not there. It's somewhere it's going to be in between here. If I'm doing a successor, uh then uh I'll go to the right.

**[43:03]:** If I'm doing predecessor, I'll go to the left and then take the either the maximum item or the minimum item. If I'm searching for eight, I see oh eight falls in the interval between eight and nine, so I should clearly take the right child among those two children. In general, there's three children, three intervals. Constant time I can find where my key falls in the interval. Okay, so search is going to take log n time again provided I have these mins and maxes. Okay, so it's it's if think about stare at it long enough, this is pretty much the same thing as regular search in a 2-3 tree uh but I've put the data just one level down. Okay. Good. That was regular search. Uh I still need to do finger search, but we'll get there. Uh now if I want to do an insert into this data structure, uh what happens?

**[43:54]:** Well, I search for the key. Let's say I'm inserting six. Uh so maybe I go here. I say oh six cuz six is in this interval. Uh six is in neither of these intervals, so uh but it's closest to the interval 2-5 or the interval seven. Let's say I go down to 2-5 and well I to insert six, I'll just add a six on there. Of course, now that node is too big. So there's still going to be a split case at the leaves where I have uh let's say a b c too many keys. I'm going to split that into a b and c. This is different from before. It used to be I would promote b to the parent cuz the parent needed a key there. Now parents don't have keys, so I'm just going to split this thing roughly in half. It works.

**[44:43]:** Uh it's still the case that whoever was the parent up here now has an additional child. One more child, so maybe that node now has four children, but it's supposed to be two or three. So if I have a node with four children, what I'm going to do, suppose to use these fancy arrows. Uh what do I do in this case? I'm just going to split that into two nodes with two children. Okay, and again, this needs to have a parent. Now that parent has an additional child, and that may cause another split. It's just like before. We'll just potentially split all the way up to the root. If we split the root, then we get an additional level. But uh we can do all this, and we can still maintain our uh level links if we want.

**[45:37]:** Then everything will take log n. I won't draw the delete case. It's it's uh delete is slightly more annoying, but I think in this case you never have to worry about where's the key coming from, your child or your your parent. You're just uh you're just merging nodes, so it's a little bit simpler. But you have to deal with the leaf case separately from the non-leaf case. Okay, so all this was to convince you that we can store data in the leaves, two-three trees still work fine. Now I claim that the graph distance in level link trees is within a constant factor of the finger search bound. So I claim I can get the finger search property in two-three trees with data in the leaves with level links. Okay, so lots of changes here, but in the end we're going to get a finger search bound.

**[46:24]:** Let's go to here.

**[46:45]:** So here's a finger search operation. Uh first thing I want to do is identify uh a node that I'm working with. I I to start from Y's node, and we're so we're supposing that we're told the node, a leaf, uh that contains Y. So I'm going to let uh V be that leaf.

**[47:15]:** Okay, because we're supposing we've already found Y, and now all the data's in the leaves, so give me the leaf that contains Y. So that should take constant time. That's just part of the input. Now I'm going to do a combination of going up and horizontal. So I'm starting at a leaf, and uh the first thing I'm going to do is check, does this leaf contain what I want? Does it contain the key I'm searching for, which is X? So that's going to be the case. At every node I store the min and the max. So if X happens to fall between the min and the max, then I'm happy. Then I'm going to do uh a regular search

**[48:03]:** uh in V's subtree. Okay, this seems weird in the case of a leaf. In the case of a leaf, this is just check the two keys that are there, whether which one is X. Okay, but in general, uh I gave you this search algorithm which was uh if uh I decide which child to take according to the ranges, that's a downward search. So that what I'm calling regular search here. Maybe downward would be a little better.

**[48:33]:** This is the usual log N time thing. Uh but we're going to claim a a bound better than log N. If this is not the case, then I know X either falls before B.min or after V.max.

**[48:49]:** So if X is less than V.min, then I'm going to uh go left. V equals V. uh I'll call it level left to be clear. You might say left is the left child. So there's no left child here of course, but level left is clear. We take the horizontal left pointer. Uh and otherwise x is greater than b dot max. And in that case we'll go right. That seems logical.

**[49:25]:** And in both cases we're going to go up. x equals x dot parent. Whoops. v equals v dot parent. x is not changing here. x is a key we're searching for. v is the node. v for vertex. So we're always going to go up and then we're going to go either left or right. And we're going to keep doing that until we find the subtree that contains x in terms of key range. Then we're going to stop this part and we're just going to do downward search. I should say return here or something. I'm going to do a downward search which was this regular algorithm. And then whatever it finds that's what I return. Okay, I claim the algorithm should be clear. What's less clear is that it achieves the bound that we want. But I claim this will achieve the finger search property. Let me draw a picture of what this thing looks like.

**[50:31]:** Kind of generically. On small examples it's hard to see what's going on. So I'm going to draw a piece of a large example. So let's say we start here. This is where y was. I'm searching for x. Let's suppose x is to the right just because otherwise I go to the other board. So x is to the right. I'll discover that the range, you know, with just this node, this node maybe contains one other key, Well, find that range is to uh small. So, I'm going to go follow the level right pointer and I get to some other node. Then I'm going to go to the parent. Maybe the parent was the parent of those two child children. So, I'm going to draw it like that. Um maybe I find this range is still too too low. I need to go right to get to X.

**[51:23]:** So, I'm going to follow a level pointer to the right. Uh I find a new subtree. Uh I'll go to its parent. Uh maybe I find that this subtree still the max is too small. So, I have to go to the right again. And then I take the parent. Uh so, this was an example of a rightward parent. Here's an example of a leftward parent. This is maybe the parent of both of these two children. Uh then maybe this subtree is still too small. The max is still smaller than X. So, then I go right one more time. Uh then I follow the parent, always alternating between right and parent until I find a node whose subtree contains X. It might have actually X may be down here cuz I immediately went to the parent without checking whether I found where X is. But if I know that X is somewhere in here, then I will do a downward search.

**[52:17]:** Uh it might go left and then down here or it might go right or there's actually plus potentially three children. One of these searches will find the key X that I'm looking for because uh I'm in the case where X is between v.min and v.max. I know it's in there somewhere. Uh it could be X doesn't exist, but it's uh predecessor or successor is in there somewhere. Uh and so, one of these three subtrees will contain the X range. And then I go follow that path and keep going down uh until I find X or its predecessor or successor. Once I find its predecessor, I can use a level right pointer to find its successor and so on. So, that's kind of the general picture of what's going on. We keep going rightward and we keep going up. Now, uh suppose we do k up steps.

**[53:15]:** Let's look at this uh this last step here, uh step k.

**[53:25]:** How high am I in the tree? I started at the leaf level. Remember in a 2-3 tree all the leaves have the same level. And I went up every step. Uh sorry uh I don't know what this is like the two-step dance uh where when I let's say every iteration of this loop I do one left or right step and then a parent step. So uh I should call this iteration k. I guess there's 2k steps then.

**[53:58]:** Clear? Uh so an iteration k that means I've gone up k times and I've gone either right or left k times. You can show that if you start going right you will keep going right. If you keep if you initially go left you'll keep going left. That that doesn't matter too much. Um at iteration k I am at height k.

**[54:21]:** Or k - 1 or however you want to count. Okay, but let's call it k. So when I do this right pointer here I know that uh for example I am skipping over

**[54:40]:** all of these keys. All the keys down keys are in the leaves. So all these keys down here I'm jumping over them. How many keys are down there? Can you tell me uh roughly how many keys I'm skipping over when I'm moving right at height k?

**[55:00]:** It's not a unique answer. You can give me some bounds.

**[55:16]:** Say again? Take the number of Number of children to the K power, yeah. Except we don't know the number of children, but it's between two and three. Sorry, cluster one should be easy, but I fail. Um so it's between two and three children, so there's uh the number if you look at a uh a height K tree, how many leaves does it have? It's going to be between two to the K and three to the K. Cuz I have between two and three children at every node. And so it's exponential in K. That's all I'll need. And so okay, when I'm at height K here, I'm skipping over a height K minus one tree or something. Uh but it's going to be So in iteration K I'm I'm skipping uh at least some constant times two to the K, maybe two to the K minus one or two to the K minus two.

**[56:17]:** I don't I'm being very sloppy, it doesn't matter. As long as it's exponential in K, I'm happy because I'm supposing that X and Y are somewhat close. Let's call this rank difference D. Then I claim the number of iterations I'll need to do in this loop is at most order log D. Because if uh when I get to the Kth iteration, I'm jumping over two to the K elements, how how large does K have to be before two to the K is larger than uh D? Well, log D. Log base two.

**[57:06]:** So uh the The of iterations

**[57:15]:** is order log D where D is the rank difference. D is the absolute value between rank of X and rank of Y.

**[57:29]:** And being a little sloppy here, you probably want to use an induction. You need to show that they're really these items here that you're skipping over that are strictly between X and Y. But we know that there's only D items between X and Y. Actually, D - 1, I guess. So as soon as we skipped over all the items between X and Y, then we'll find a range that contains X and then we'll go do the downward search. Now, how long does the downward search cost? Whatever the height of the tree is. What's the height of the tree? That's the number of iterations. So total cost the downward search will cost the same as the rest of the search. And so total cost is going to be order log D. Okay? Any questions about finger searching with level lengths data at the leaves two three trees?

**[58:25]:** Yeah. Sorry, I'm not sure what definition of rank is. I'm defining D to be the rank of X minus rank of Y. So then my goal is to achieve a log D bound and I'm claiming that because once I've skipped over D items, then I'm done. Then I found X. And that and at step K, I'm skipping over to the K items. So how big is K going to be? Log D. That's all. Yeah, that was just I used D for our notation here. Cool. So finger searching it's nice especially if you're doing many consecutive searches that are all relatively close to each other. But that was easy. Let's do a more difficult augmentation, right? Uh, so the last topic for today is range trees. This is probably the coolest example of augmentation, at least that you'll see in this class. If you want to see more, you should take Advanced Data Structures 6851.

**[59:27]:** Uh,

**[59:32]:** and range trees solve a problem called orthogonal range searching, not orthogonal search ranging. Uh, orthogonal range search.

**[59:51]:** So, uh, what's the problem? I'm going to give you a bunch of points. Draw them as fat dots so you can actually see them uh, in some dimension. So here's this is for example a 2D point set. Okay, over here I will draw a 3D point set. You can tell the difference I'm sure.

**[1:00:19]:** There, now it's a 3D point set. Uh, and this is a static point set. You could make this dynamic, but let's just think about the static case. Uh, don't want the 2D points and the 3D points to mix, so um, now you get to pre-process this into a data structure. So it's a static data structure problem, and now I'm going to come along with a whole bunch of queries. A query will be a box. Okay, in two dimensions a box is a rectangle. Something like this, axis aligned. So I give you an x min and x max, a y min and y max. I want to know what are the points inside. Maybe I want you to list them. There's a lot of them, it's going to take a long time to list them. Maybe I just want to know 10 of them as examples.

**[1:01:05]:** You know, maybe this is a Google search or something. I just get the first 10 results on the first page, I hit next, then I want the next 10, that kind of thing. Uh, or maybe I want to know how many search results there are. Number of points in the rectangle, bunch of different problems. In 3D, it's a a 3D box, which is a little harder to draw, but Sorry. Can't really tell which points are inside the box. Let's say these three points are all inside the box. I give you an interval on x, an interval on y, and an interval on z, and I want to know what are the points inside, how many are there, list them all, list 10 of them, whatever. Okay. Uh I want to do this in polylog time. Let's say I'm going to do I'm going to achieve today log squared for the 2D problem and log cubed for the 3D problem, plus whatever the size of the output is.

**[1:02:01]:** So let me just write that down.

**[1:02:14]:** So the goal is to preprocess

**[1:02:22]:** end points in D dimensions. Uh so you got to spend a bunch of time preprocessing to support a query which is uh given a box, axis-aligned box, uh find let's say the number of points in the box, uh find k points in the box.

**[1:03:03]:** I think that's good. That includes a special case of find all the points in the box. Uh so this, of course, we have to pay a penalty of order k for the output. Okay. No getting around that. Uh, but I want the rest of the time to be log to the D.

**[1:03:28]:** I want to achieve log to the D N plus size of the output.

**[1:03:36]:** And you get to control how big you want the output to be. So it's a pretty reasonable data structure. In a certain sense, we will understand what the output is in log to the D time. If you actually want to list points, well then you have to spend the time to do it. All right. So 2D and 3D are great, but let's start with 1D. First, we should understand 1D completely, then we can generalize.

**[1:04:06]:** 1D we already know how to do, but

**[1:04:12]:** 1D I have a line. I have some points on the line.

**[1:04:22]:** And I'm given as a query some interval.

**[1:04:29]:** And I want to know how many points are in the interval, give me the points in the interval, and so on. So how do I do this anyways?

**[1:04:48]:** Uh, if D is one, so I want to achieve log D sorry, log N plus size of output.

**[1:04:58]:** I hear whispers.

**[1:05:05]:** Yeah? A segment tree. Segment tree? That's fancy. Uh, we won't cover segment trees. You probably probably segment trees do it. But yeah, there are lots of ways to do this. Yeah? Sorted array. Sorted array is probably the simplest. If I the items in the sorted array, and I have two values here. I'll call them x1 and x2. This is the like the x min and the x max. Uh binary search for x1, binary search for x2. Find the successor of x1 and the predecessor of x2. I'll find these two guys, and then I know all the ones in between. That's the match. Okay, so that'll take log n time to find those points, and then we're good. Okay, so we could do a sorted array. Uh for a sorted array is a little hard to generalize. Uh I don't want to do a 2D array.

**[1:05:55]:** That sounds bad. Uh you could of course do a binary search tree, like an AVL tree. Same thing cuz we have log n search, find successor predecessor. I guess you could use van Emde Boas, but that's hard to generalize to 2D. Um you could use level linked Here's a fancy version. Uh we could use level linked uh 2-3 trees with data in the leaves. Then once I find x min, I find this point, I can go to the successor in constant time because that's a finger search with a rank difference of one. And I can just keep calling successor, and in constant time per item, I will find the next item. So we could do that easily with a sorted array. BST is not so great if cuz successor might cost log n each time. Uh but if I have the level lengths, then basically I'm just walking down the linked list at the bottom of the tree.

**[1:06:49]:** Okay, so actually level linked is even better. Uh BST would achieve something like uh log n plus k log n, where k is the size of the output. There k If I want k points in the box, I have to pay log n for each. Level linked, I'll only play uh log n plus k. Here I actually only need the levels of at the leaves, but the level links. Okay, all all good, but I actually want to tell you a different way to do it, uh that will generalize better. So

**[1:07:30]:** the pictures are going to look just like the pictures we've talked about.

**[1:07:43]:** So

**[1:07:53]:** because I'm uh so this these would actually work dynamically. Uh my goal here is just to achieve a static data structure. I'm going to idealize uh this solution a little bit and just say uh suppose I have a perfect perfectly balanced binary search tree. That's going to be my data structure. Okay? So the data structure is not hard, uh but what's interesting is how I do range search. So if I do uh range query of the interval, I'll call it AB, then what I'm just what I'm going to do is do a binary search for A, do a binary search for B,

**[1:08:42]:** uh trim the common prefix of those search paths. That's basically finding the lowest common ancestor of those of A and B.

**[1:09:00]:** And then I'm going to do some stuff. Let me draw the picture. So here is suppose here's the node that contains A. Here's the node that contains B. They may not be at the same depth. Who knows? Uh then I'm going to look at the parents of A. I mean I just came down from some path here and some path down to B. I want to find this branching point where the paths to A and the paths to B diverge. So uh let's just at the parent of A. Could be a right parent. Uh I guess like that. In which case there's a subtree here. Could be a left parent. There's a subtree here. Uh I'm going to follow my convention again that x-coordinate corresponds roughly to key. So maybe it's like this. Left parent here. Could be a right parent here.

**[1:10:07]:** Okay, something like that. Uh

**[1:10:23]:** Okay, remember it's a perfect tree. So actually all the leaves will be at the same level.

**[1:10:35]:** And roughly here x-coordinate corresponds to key. So here is A. And I want to return all the keys that are between A and B. So that's everything in this sweep line.

**[1:10:50]:** Okay, the parents of the LCA don't matter because this parent is either going to be way over to the right or way over to the left. In both cases it's outside the interval A to B. So what I've tried to highlight here, and I will color it in blue, is the relevant nodes for the search between A and B. So A is between A and B. Uh this subtree is greater than A and less than B. Uh this node and these nodes. This node and these nodes. This node and these nodes. Uh the common ancestor. And then the corresponding thing over here.

**[1:11:31]:** Okay, all the nodes in all these blue subtrees plus these individual nodes fall in the interval between A and B. And that's it. Okay, this should look super familiar. It's just like when we were computing rank. We were trying to figure out how many guys are to our left or to our right. We're basically doing a rightward rank from A and a leftward rank from B. And that finds all the nodes until and stopping when those two searches converge. And then we're finding all the nodes between A and B. Okay, I'm not going to write down the pseudocode. It's the same kind of thing. You look at right parents and left parents. Whenever you you just walk up from A, whenever you get a right parent, then you want that node and the subtree to its right. And so that will highlight these nodes. Same for B, but you look at left parents.

**[1:12:17]:** And then you stop when those two searches converge. So you're going to do them in lockstep. You do one step for A and B, one step for A and B. And when they happen to hit the same node, then you done. You add that node to your list. And what you end up with is a bunch of nodes and rooted subtrees.

**[1:12:43]:** The things I circled in blue is going to be my return value. So I'm going to return all of these nodes explicitly. And I'm also going to return these subtrees. I'm not going to have to write them down. I'm just going to return the root of the subtree and say, hey look, here's an entire subtree that contains nodes points that are in the answer. Don't have to list them explicitly. I can just give you the tree. Then if I want to know how many results are in the answer, well, just augment to store subtree size at the beginning. Then I can count how many nodes are down here, how many nodes are down here, add that up for all the triangles, and then also add one for each of the blue nodes. And then I've counted the number uh the size of the answer in how much time.

**[1:13:30]:** How many subtrees how many nodes am I returning here? Log.

**[1:13:40]:** Log n nodes and log n rooted subtrees because at each step I'm going up by one for A and up by one for B. So it's like two log n. Log n. Cool? So I would call this an implicit representation of the answer. From that implicit representation you can do uh subtree size augmentation to count the size of the answer. You can just start walking through one by one uh do an in-order traversal of the trees and you'll get the first k points in the answer in order k time. Question?

**[1:14:17]:** but you don't That's right. As I'm walking up the tree if it's a right parent then I take the right subtree and include that in the answer. If it 's a left parent just forget about it. Don't do anything. Just keep following parents. Whenever I do right parent then I also add that node and the right subtree. If it's a left parent I don't include the node. I don't include the left subtree. I also don't include the right subtree. That would have too much stuff. Yep. It's easy when you see the picture. If you write down the algorithm it's clear it's left versus right uh parents. Yeah. Do you include the left subtree of B in log I would also thank you. I should color the left subtree of B. I didn't apply symmetry perfectly. So we have the right subtree of A and the left subtree of B.

**[1:15:03]:** Thanks. Uh I would also include B if it's a closed interval. Okay, slightly more general. If A and B are not in the tree then this is really the successor of A and this is the predecessor of B. Okay, so then A and B don't have to be in there. This is still a well-defined range search. Okay, now we really understand 1D. I claim we're we've almost solved all dimensions. All we need is a little bit of augmentation. So, let's do it.

**[1:15:51]:** Let's start with 2D, but then 3D and 4D and so on will be easy. Why do I care about 4D range trees? Because maybe I have a database. Each of these points is actually just a row in the database, which has four columns, four values. And what I'm trying to do here is like find all the people in my database that have a salary between this and this and have an age between this and that and have a profession between this and this. I don't know what that means, but number of degrees between this and this. Whatever. If you have some numerical data representing a person or a thing in your database, then this is a typical kind of search you want to do. And you want to know how many answers you've got and then list the first 100 of them or whatever. So, this is a This is a practical thing in databases.

**[1:16:40]:** It's what you might call an index in the database. Okay, but let's start Suppose your data is just two-dimensional. You have two fields for every item. What I'm going to do is store a 1D range tree

**[1:16:57]:** on all points

**[1:17:02]:** by X. So, this this data structure makes sense if you fix a dimension. You say X is all I care about. Forget about Y. Still have my point set? Yeah. So, what that corresponds to is projecting each of these points onto the X axis.

**[1:17:30]:** Okay? And now also projecting my query. So, my new query is here to here in x. And so, this data structure will let me find all these points that match in x. Now, that's not good because there's actually only two points that I want, but I find four points in this picture. Okay? But it's half of the answer. It's all the x matches forgetting about y. Now, here's the fun part. So, when I do a search here, I get log n nodes. Nodes are good cuz they have a single key in them. So, I'll just check for each of those log n nodes, do they also match in y? If they do, add it to the answer. If they don't, forget about it. Okay? But the tricky part is I also get log n subtrees representing parts of the answer. So, potentially, you know, it could be that your search, this this rectangle only has like five points.

**[1:18:33]:** But if you look at this whole vertical slab, there's a billion points. Now, luckily, those billion points are represented succinctly. There's just log n subtrees saying, well, there's half a billion here and a quarter billion here and an eighth of a billion here. Uh so, can now for each of those that big chunk of output, I want to very quickly find the ones that match in y. How would I find the ones matching in y? A range tree. Yeah. Okay. So, here's what we're going to do. For each node uh let's call it x. Oh, x x is overloaded. It's coordinates, so many things. Uh let's call it v uh in the this thing I'm going to call the x tree. So, for every node in the x tree, I'm going to store another 1D range tree, but this time using the y coordinate.

**[1:19:38]:** Uh on all points in these rooted subtree. Okay, at this point I really want to draw a diagram.

**[1:19:58]:** So uh rough picture.

**[1:20:11]:** Okay, forgive me for not drawing this perfectly. Uh this is roughly what the answer looks like for the 1D range search. Here this is the X tree. And here I've searched between this value and this value in the X coordinate. Basically I have log N nodes. I'm going to check those separately. Then I also have these log N subtrees. For each of those log N subtrees I'm going to have a pointer. This is the augmentation. To uh another tree of exactly the same size on exactly the same data that's in here it's also over here but it's going to be sorted by Y. And so 1D range tree by Y. Tons of data duplication here. I took all these points and I copied them over here but then built a 1D range tree in Y. This is all preprocessing. So I'm not I don't have to pay for this.

**[1:21:08]:** It's polynomial time. Don't worry too much. Um and then I'm going to search in here. What does the search in there look like? I'm going to get, you know, some more trees and a couple more nodes. Okay, but now those items, those points match in X and Y because this whole subtree matched in X and I just did a Y search so I found things that matched in Y. So I get here another log N trees that are actually in my answer. And for each of these nodes I I a corresponding other data structure where I find I do a little search and I get part of the answer.

**[1:21:49]:** Okay, I get the idea. Everyone sounds huge. The data structure sounds huge, but it's actually small. Uh, but one thing that's clear is it takes log squared n time because I have log n triangles over here. For each of them I spend log n to find triangles over here. The total output is log squared n nodes. For each of them I have to check manually plus uh and so over here I there's log n different searches I'm doing. Each one has size log n. So I get log squared little triangles that contain the results that match in x and y. How much space in this data structure? That's the remaining challenge. Uh actually it's it's not that hard because if you look at a key so look at some key in this x tree. Let's look at a leaf because that's maybe the most interesting.

**[1:22:52]:** Uh I'm going to start start over here. Sorry. Here's the x tree. x tree has linear size, just one tree. If I look at some key value well uh you know it lives in this subtree and so there's going to be a corresponding blue structure of that size that contains that key. And then there's the parent. So there's a structure here. That has a corresponding blue triangle. And then its parent that's another triangle that contains I'm looking at a key uh k here. All of these triangles contain the key k and so key k will be duplicated all this many times. But how many how many subtrees is k in? log n Each key fundamental fact about uh binary balanced binary search trees. Each key lives in log n subtrees, namely all of its ancestors.

**[1:24:00]:** Awesome. Because that means the total space is n log n. There's n keys. Each of them is duplicated at most log n times. In general, log to the d - 1. So if you do it in 3D, each of the blue trees, every node in it has a corresponding pointer to a red tree that's sorted by z. And you just keep doing this sort of nested searching. It's like super augmentation, but you're only losing a log factor each dimension you add.
