Tree (data structure)
In computer science , a is tree (engl. Tree ) is a data structure and an abstract data type , can be mapped to the hierarchical structures. Because, on the one hand, many combinatorial problems can be traced back to trees or (in the case of spanning trees ) are the results of graph algorithms (such as latitude or depth search ), trees play a special role in computer science. Starting from the root, several objects of the same type can be linked with one another, so that the linear structure of the list is broken up and a branch takes place. Since trees are one of the most commonly used data structures in computer science, there are many specializations.
The advantage of trees over linear structures such as fields or lists is their efficient access. For example, a search is only carried out in logarithmic time versus linear time for fields (for details see article on binary search ). The advantage of trees as a data structure compared to network structures is the small number of edges (connections) that have to be saved or taken into account. The number of edges of the complete graph corresponds to the triangle number . The number of edges in a tree with the same number of nodes (objects), however, is only .
Like other graph structures, trees can be stored via an adjacency list or matrix or via an incidence matrix .
terminology
In general, all conceivable terms are borrowed from graph theory . The objects specified by the hierarchy are called nodes . Typically, starting from a first node, the root , each node stores a list of references to its subordinate nodes. These references are called edges . It is then common practice to speak of children for the child nodes and a parent for the referring node . Other names borrowed from genealogy are also used. If a knot has no children of its own, it is called a leaf .
The terms root trees are particularly relevant: the roots of these trees are clearly defined. Once you have recorded a root, the following can be defined in addition to the terms that you already have in graph-theoretic trees - distance , subtree , node degree , isomorphism : The depth of a node indicates how many edges it is away from the root . The root has the depth 0. The nodes with the same depth together form a level . The height of a tree is then the maximum depth of a node.
Binary tree
An important special case is the binary tree , in which each node can only have a maximum of two children. In binary trees, for example, the number of children is at most two, and in height-balanced trees it also applies that the heights of the left and right subtree at each node do not differ too much.
In the case of ordered trees, especially search trees , the elements are stored in the tree structure in an orderly manner so that elements can be found quickly in the tree. A further distinction is made here between binary search trees with AVL trees as a balanced version and B trees and a variant, the B * trees . Specializations of B-trees are 2-3-4-trees , which are often implemented as red-black trees .
A special case of the AVL trees are Fibonacci trees . They are used as extreme cases and objects of comparison when considering the efficiency of height-balanced trees, especially AVL trees.
Geometric tree structures such as the R-tree and its variants are not sorted, but “nested” . Only those subtrees that overlap the requested area are searched here.
Although trees are multi-dimensional in their structure, the interlinking of the objects is often unidirectional. The concatenation of the stored objects begins at the root of the tree and from there in the direction of the nodes of the tree.
literature
- Hartmut Ernst, Jochen Schmidt, Gerd Beneken: Basic course in computer science. Basics and concepts for successful IT practice - A comprehensive, practice-oriented introduction , 5th edition, Springer, Wiesbaden 2015, pp. 523–596
- Heinz-Peter Gumm, Manfred Sommer: Introduction to Computer Science , 10th edition, Oldenbourg, Munich 2013, pp. 372–398