(as told by Jim Blandy, jimb@cs.oberlin.edu) So, you've got this array, foo: _______________________________________________________________ foo = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | --------------------------------------------------------------- (indexing is done from 1 wlog to avoid confusion). The array represents a balanced binary tree. How? Well, take foo[1] to be root. A node's two children are foo[2n] and foo[2n +1], so root's children are 2 and 3. 2's children are 4 and 5. foo[n]'s parent is, of course, foo[(n - n%2) / 2]. Good. Now we can talk about it as a tree, remembering that there is this great way to implement it without the overhead of linked-lists or any kinds of structures. --------------- R -------------- | ("R" for "Root") | | | ------ A ------ ------ B ------ | | | | | | | | -- C -- -- D -- -- E -- -- F -- | | | | | | | | G H I J K L M N Suppose that each node must store a number, and that the lowest number must always be at the root. We need two procedures: 1) Take the root number away, and shift everything around so that the lowest number is again at root. 2) Add a new number and shift everything around so that it ends up in the "right" place. These two procedures can be designed with a minimum of shifting (and a practical application will be given later). Assume that the tree looks like this (a letter means an empty node): --------------- 2 -------------- | ("R" for "Root") | | | ------ 3 ------ ------ 5 ------ | | | | | | | | -- 8 -- -- 7 -- -- 6 -- -- F -- | | | | | | | | G H I J K L M N For procedure 1, what happens when 2 is popped off the root node? Root's two children are compared, and the lower of the two is moved into its parent's space (the parent in this case being root). Then the same procedure is called on the now-empty child node, and so on, until both children of the node are empty. In this case, 3 would move up, then 7. Procedure 2 requires finding the first free node and inserting n, then number to be added. The first free node is F, in this example. Let's use n = 4. n is compared with its parent; if n < p(n), then n and the parent swap places. The same procedure is called again on n in its new home, until there n is not less than its parent. These two procedures together guarantee that no n lower than root's value will ever occupy any node, so the n on top can be taken as the "lowest". One application is a timer, which needs to always look at the "next" alarm setting and see if the current time is greater than that setting. There is no need to check every setting, just the first (root) one. Settings can be added dynamically without screwing up the timer, since settings will always bubble into the correct node. Questions: does it have to be binary, or will an n-ary tree be just as easy to implement, so long as it's balanced? I think balance is the only important thing, in fact. 1 3 4 5 9 10 11 12 13 14 15 16 17 Well, no, we get huge gaps. Never mind -- this might have some interesting applications, with overlapping trees implemented in very efficient space or something. The holes could hold something, after all, since we know exactly where they are.