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 19: | Line 19: | ||
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 is 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 (usually a binary tree, but in this case a | + | 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 is 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 (usually a binary tree, but in this case a ternary tree), subject to one additional rule: |
*For every node in the tree, ''everything'' beneath that node - both or all of its children, all of its children's children, all of ''their'' children, and so on - are "less than" the node itself. | *For every node in the tree, ''everything'' beneath that node - both or all of its children, all of its children's children, all of ''their'' children, and so on - are "less than" the node itself. |