Editing 835: Tree
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 4: | Line 4: | ||
| title = Tree | | title = Tree | ||
| image = tree.png | | image = tree.png | ||
+ | | imagesize = | ||
| titletext = 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. | | titletext = 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== | ==Explanation== | ||
− | + | {{w|Binary tree}}s 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." | |
− | *A tree starts at a single node, called its root. | ||
− | *Each node in a tree has two | ||
− | |||
− | |||
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 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 | + | 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 {{w|Heap (data structure)|heap}} is a special kind of tree, subject to one additional rule: |
− | *For every node in the tree, ''everything'' beneath that node - both | + | * 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. | "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. | ||
− | + | ==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. | ||
− | + | {{comic discussion}} | |
− | + | <!-- Include any categories below this line--> | |
− | |||
− | |||
− | |||
[[Category:Comics with color]] | [[Category:Comics with color]] | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− |