Changes

Trees are one of the fundamental [[data structure]]s of [[computer science]], along with the [[array]], the [[index]], and the [[look-up table]]. The '''binary tree''' is the simplest, and most commonly used, form of tree.  The primary distinguishing feature of a tree data structure is that it is tree-shaped (if balanced).  All tree structures contain nodes which contain data, and links from the node to other nodes.  The relative position of the nodes to each other based on the links means that the tree's data can be retrieved in an ordered fashion if the proper traversal method is used.  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.

Trees are one of the fundamental [[data structure]]s of [[computer science]], along with the [[array]], the [[index]], and the [[look-up table]]. The '''binary tree''' is the simplest, and most commonly used, form of tree.  The primary distinguishing feature of a tree data structure is that it is tree-shaped (if balanced).  All tree structures contain nodes which contain data, and links from the node to other nodes.  The relative position of the nodes to each other based on the links means that the tree's data can be retrieved in an ordered fashion if the proper traversal method is used.  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.  A node whose left and right links don't point to another node is called a leaf, or terminal, node.  The depth of a node is the number of levels between that node and the root node.

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.  A node whose left and right links don't point to another node is called a leaf, or terminal, node.  The depth of a node is the number of levels between that node and the root node.

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 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.

 

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==

==Applications==