Difference between revisions of "Binary tree"
m |
|||
| Line 1: | Line 1: | ||
| − | + | The '''binary tree''' is the simplest, and most commonly used, form of [[tree (data structure)|tree]]. A binary tree differs from other trees (such as a B3 tree) in that each node only has two links to other nodes. By convention, these links are called the '''left''' and '''right''' links. Data sorted before a node is inserted into the tree via the left link of that node, while data that sorts after is inserted into the tree via the right link. | |
| − | Note that sometimes an additional '''parent''' link is used to point back to the node's parent in the tree, however this link is implied by the parent's left or right link. Parent links are used to reduce the otherwise necessary context that must be kept during tree traversal, but they are not considered when describing the tree. Thus, a binary tree with a parent link is not considered a B3 tree. The root node of a tree is the node with no parent. It is the point from which all traversals begin | + | Note that sometimes an additional '''parent''' link is used to point back to the node's parent in the tree, however this link is implied by the parent's left or right link. Parent links are used to reduce the otherwise necessary context that must be kept during tree traversal, but they are not considered when describing the tree. Thus, a binary tree with a parent link is not considered a B3 tree. The root node of a tree is the node with no parent. It is the point from which all traversals begin. |
==Balanced Trees== | ==Balanced Trees== | ||
Revision as of 21:12, November 16, 2018
The binary tree is the simplest, and most commonly used, form of tree. A binary tree differs from other trees (such as a B3 tree) in that each node only has two links to other nodes. By convention, these links are called the left and right links. Data sorted before a node is inserted into the tree via the left link of that node, while data that sorts after is inserted into the tree via the right link. Note that sometimes an additional parent link is used to point back to the node's parent in the tree, however this link is implied by the parent's left or right link. Parent links are used to reduce the otherwise necessary context that must be kept during tree traversal, but they are not considered when describing the tree. Thus, a binary tree with a parent link is not considered a B3 tree. The root node of a tree is the node with no parent. It is the point from which all traversals begin.
Balanced Trees
When a tree structure is constructed, the structure can become skewed to the left or right resulting in an unbalanced tree. Trees constructed from random data tend to be more balanced. A perfectly balanced binary tree will have the most shallow structure, meaning the least possible number of levels from the root node to the deepest node. Because of the nature of the binary tree, a perfectly balanced tree will require no more than O(log n) comparisons to find a given node. However, an unbalanced tree could require as much as O(n) comparisons. Because of the performance problems associated with unbalanced trees, some binary tree implementations will adjust the nodes as they are added or deleted in order to keep the tree balanced. Such binary trees are called AVL, or self-balancing, trees. The extra complexity of implementation and the performance cost of the work of adjusting the tree structure means that AVL trees are not always the best choice when a binary tree is needed.
Applications
Binary trees are traditionally used in the implementation of Huffman encoding. They are also used in the sorting algorithms heapsort and mergesort. Certain complex algorithms, such as MapReduce, also make heavy use of binary trees. Finally, the binary tree can be used to represent certain dynamic processes, such as the distribution pattern of a file in a peer-to-peer network or the genealogical history of a person who is the product of a long line of two-parent families.
