# 835: Tree

Jump to: navigation, search
 Tree Title text: Not only is that terrible in general, but you just KNOW Billy's going to open the root present first, and then everyone will have to wait while the heap is rebuilt.

## Explanation

Binary trees are data structures in computer science, based on two simple rules:

• A binary tree starts at a single node, called its root.
• Each node in a binary tree has two spaces for its children, each of which may be empty or occupied by another node. (Of course, that node may have its own children, and so forth.) As a bit of trivia, a node with no children is called a "leaf node."

The "Christmas tree" is a basic representation of a binary tree - the star at the top is the root node, and the lights running down indicate the connections between parent and child. Contrary to what the terms "root" and "leaf" might imply, trees in computer science are typically represented upside-down, with the root on top and the leaves fanning out below.

The Christmas tree is constructed based on no apparent rules, but the main power of binary trees comes in organizing them according to specific rules. Because code that runs later can assume the data are organized in this specific way, it can use different algorithms that make things run faster. One way of doing this is with a heap. A heap is a special kind of binary tree, subject to one additional rule:

• For every node in the tree, everything beneath that node - both of its children, all of its children's children, all of their children, and so on - are "less than" the node itself.

"Less than" in this case can refer to any comparison that can be made between two nodes - in this case, it's based on the size of the presents. Of course, there's a cost to all this; the heap must first be placed in that order. Not only that, but if a node gets removed from the heap, the heap has to be "rebuilt" to put it back in the right order. This is referenced in the title text - if Billy opens the root present, several comparisons must be done to shift other presents in its place to preserve the heap rule.

Technically the heap of presents isn't a true heap, since the green present on the right has three children. It's possible the leftmost child was supposed to be a child of the green polka-dotted present to its left, and Randall drew the line in the wrong place.

## Transcript

[There is a binary Christmas tree, with each node a ball, and lights strung between parent and child nodes. Beneath it is a heap of presents - sorted with the largest on top, smaller presents connected to it with string. Next to the tree are a kid and his or her parents.]
Billy: It's a Christmas tree with a heap of presents underneath!
Mother: ... We're not inviting you home next year.

# Discussion

I didn't really look too closely, but it seems to be based on Red-Black trees (Red Green in the case of Christmas): http://en.wikipedia.org/wiki/Red_black_tree

Nope. For a Red-Black tree, all the leaves have to be the same color as the root, and no red nodes can have a red parent. The root here is a yellow star, the leaves are mixed colors, and both colors have instances of a node with a color that matches it's parent, so nether red nor green can be the "Red" for the algorithm. 108.162.221.58 (talk) (please sign your comments with ~~~~)

Then again it could just be a color scheme. 132.3.25.79 12:35, 23 April 2013 (UTC)Tyler

The title text doesn't really make sense - removing the root of a heap is a very common practice for a variety of applications. In fact, you almost always want to process heaps by removing the root. Ciotog (talk) 14:05, 2 March 2014 (UTC)

It is common, ok. And, in fact, Billy WILL process the heap by removing the root. It makes however sense, since all heaps must be "refreshed" after you remove the root. While it takes small time for a computer, it can be lengthy for a human. And it would be probably better an unsorted array of presents, so Billy can open any present without effecting any effect (see Comic 326) --108.162.229.42 14:10, 17 June 2014 (UTC)

Hmmm... The heap seems sketchy. Note the second and third levels. Not a heap by C++ standards. 108.162.245.218 22:08, 18 June 2014 (UTC)

The heap doesnt look like a heap to me (or at least not a common binary heap): the root has 4 children for a start, and it is not balanced, for seconds. 108.162.250.163 (talk) (please sign your comments with ~~~~)

##### Tools

It seems you are using noscript, which is stopping our project wonderful ads from working. Explain xkcd uses ads to pay for bandwidth, and we manually approve all our advertisers, and our ads are restricted to unobtrusive images and slow animated GIFs. If you found this site helpful, please consider whitelisting us.

Want to advertise with us, or donate to us with Paypal?