Tree (Data Structure)

Trees are one of the fundamental data structures of computer science, along with the array, the index, and the look-up table. The primary distinguishing feature of a tree data structure is that it is an inverted tree shape (if relatively balanced) when represented as a drawing.

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 node whose links don't point to any other nodes is called a leaf, or terminal, node. The depth of a node is the number of levels between that node and the root node. Within a given tree, the number of maximum links from each node is consistent. A tree with two links from each node is called a B2, or Binary tree. A tree with three links from each node is a B3 tree. One with four links from each node is a B4 tree, and so on.