Tree (data structure)

related topics
{math, number, function}
{specie, animal, plant}
{woman, child, man}
{line, north, south}

In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.

Mathematically, it is a tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at most one parent node. Furthermore, the children of each node have a specific order.

Contents

Terminology

A node is a structure which may contain a value, a condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn growing downwards). A node that has a child is called the child's parent node (or ancestor node, or superior). A node has at most one parent.

Nodes that do not have any children are called leaf nodes. They are also referred to as terminal nodes.

A free tree is a tree that is not rooted.

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self balancing trees, AVL Trees in particular. Conventionally, the value -1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.

The topmost node in a tree is called the root node. Being the topmost node, the root node will not have parents. It is the node at which operations on the tree commonly begin (although some algorithms begin with the leaf nodes and work up ending at the root). All other nodes can be reached from it by following edges or links. (In the formal definition, each such path is also unique). In diagrams, it is typically drawn at the top. In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that node.

An internal node or inner node is any node of a tree that has child nodes and is thus not a leaf node.

A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. (This is different from the formal definition of subtree used in graph theory.[1]) The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree (in analogy to the term proper subset).

Full article ▸

related documents
Diffeomorphism
Isomorphism theorem
Generalized Riemann hypothesis
Algebraic topology
Monotonic function
Discriminant
Conjunctive normal form
Axiom of regularity
Differential topology
Mean value theorem
Knight's tour
Cartesian product
Spectrum of a ring
Product topology
Laurent series
Theory of computation
Kolmogorov space
De Morgan's laws
Diophantine set
Well-order
Lebesgue measure
Goodstein's theorem
Carmichael number
Least common multiple
Group representation
Cauchy-Riemann equations
Local ring
Automata theory
Golden ratio base
Graftal