View source for Tree (abstract data type)

{{Short description|Linked node hierarchical data structure}}{{For|graph theory|Tree (graph theory)}}{{Distinguish|text=[[Trie]], a specific type of tree data structure}}
[[File:Tree (computer science).svg|right|thumb|This unsorted tree has non-unique values (e.g., the value 2 existing in different nodes, not in a single node only) and is non-binary (while there are only up to two children nodes per parent node in a binary tree). The root node at the top (with the value 2 here), has no parent as it is the highest in the tree hierarchy.]]
In [[computer science]], a '''tree''' is a widely used [[abstract data type]] that represents a hierarchical [[tree structure]] with a set of connected [[Node (computer science)|nodes]]. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent,<ref name="Subero 2020 p. ">{{cite book | last=Subero | first=Armstrong | title=Codeless Data Structures and Algorithms | publisher=Apress | publication-place=Berkeley, CA | year=2020 | isbn=978-1-4842-5724-1 | doi=10.1007/978-1-4842-5725-8 | page= | chapter=3. Tree Data Structure | quote=A parent can have multiple child nodes. ... However, a child node cannot have multiple parents. If a child node has multiple parents, then it is what we call a graph.}}</ref><ref>{{Cite web |title=Abstract Tree / Tree ADT {{!}} Abstract Data Types {{!}} ECE 250 {{!}} University of Waterloo |url=https://ece.uwaterloo.ca/~dwharder/aads/Abstract_data_types/Hierarchical_ordering/Tree/ |access-date=2024-12-13 |website=ece.uwaterloo.ca}}</ref> except for the ''root'' node, which has no parent (i.e., the root node as the top-most node in the tree hierarchy). These constraints mean there are no cycles or "loops" (no node can be its own ancestor), and also that each child can be treated like the root node of its own subtree, making [[recursion]] a useful technique for [[tree traversal]]. In contrast to [[linear data structure]]s, many trees cannot be represented by relationships between neighboring nodes (parent and children nodes of a node under consideration, if they exist) in a single straight line (called edge or link between two adjacent nodes).

[[Binary tree]]s are a commonly used type, which constrain the number of children for each parent to at most two. When the order of the children is specified, this data structure corresponds to an [[ordered tree]] in [[graph theory]]. A value or pointer to other data may be associated with every node in the tree, or sometimes only with the ''leaf nodes'', which have no children nodes.

The [[abstract data type]] (ADT) can be represented in a number of ways, including a list of parents with pointers to children, a list of children with pointers to parents, or a list of nodes and a separate list of parent-child relations (a specific type of [[adjacency list]]). Representations might also be more complicated, for example using [[Database index|indexes]] or ancestor lists for performance.

Trees as used in computing are similar to but can be different from mathematical constructs of [[Tree (graph theory)|trees in graph theory]], [[Tree (set theory)|trees in set theory]], and [[Tree (descriptive set theory)|trees in descriptive set theory]].

==Terminology==
A [[node (computer science)|node]] is a structure which may contain data and connections to other nodes, sometimes called '''edges''' or '''links'''. Each node in a tree has zero or more '''child nodes''', which are below it in the tree (by convention, trees are drawn with ''descendants'' going downwards). A node that has a child is called the child's '''parent node''' (or [[Superior (hierarchy)|superior]]). All nodes have exactly one parent, except the topmost '''root node''', which has none. A node might have many '''ancestor nodes''', such as the parent's parent.  Child nodes with the same parent are '''sibling nodes'''. Typically siblings have an order, with the first one conventionally drawn on the left. Some definitions allow a tree to have no nodes at all, in which case it is called ''empty''.

{{anchor|Internal nodes}}An '''internal node''' (also known as an '''inner node''', '''inode''' for short, or '''branch node''') is any node of a tree that has child nodes. Similarly, an '''external node''' (also known as an '''outer node''', '''leaf node''', or '''terminal node''') is any node that does not have child nodes.

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''). Thus the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

Each non-root node can be treated as the root node of its own '''subtree''', which includes that node and all its descendants.{{efn|This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no descendants).}}<ref>{{MathWorld|id=Subtree|title=Subtree}}</ref>

Other terms used with trees:
{{glossary}}
{{term|Neighbor}} {{defn|Parent or child.}}
{{term|Ancestor}} {{defn|A node reachable by repeated proceeding from child to parent.}}
{{term|Descendant}} {{defn|A node reachable by repeated proceeding from parent to child. Also known as ''subchild''.}}
{{term|Degree}} {{defn|For a given node, its number of children. A leaf, by definition, has degree zero.}}
{{term|Degree of tree}} {{defn|The degree of a tree is the maximum degree of a node in the tree.}}
{{term|Distance}} {{defn|The number of edges along the shortest path between two nodes.}}
{{term|Level}} {{defn|The level of a node is the number of edges along the
unique path between it and the root node.<ref>{{cite book | url=https://dl.acm.org/doi/book/10.5555/1941983 | isbn=978-0-495-39132-6 | author=Susanna S. Epp | title=Discrete Mathematics with Applications | location=Pacific Grove, CA | publisher=Brooks/Cole Publishing Co. | date=Aug 2010 | page=694 }}</ref> This is the same as depth.}}
{{term|Width}} {{defn|The number of nodes in a level.}}
{{term|Breadth}} {{defn|The number of leaves.}}
{{term|Complete tree}} {{defn|A tree with every level filled, except the last.}}
{{term|Forest}} {{defn|A set of one or more disjoint trees.}}
{{term|Ordered tree}} {{defn|A rooted tree in which an ordering is specified for the children of each vertex.}}
{{term|Size of a tree}} {{defn|Number of nodes in the tree.}}
{{glossary end}}

==Common operations==
* Enumerating all the items
* Enumerating a section of a tree
* Searching for an item
* Adding a new item at a certain position on the tree
* Deleting an item
* [[Pruning (algorithm)|Pruning]]: Removing a whole section of a tree
* [[Grafting (algorithm)|Grafting]]: Adding a whole section to a tree
* Finding the root for any node
* Finding the [[lowest common ancestor]] of two nodes

===Traversal and search methods===
{{Main article|Tree traversal}}

Stepping through the items of a tree, by means of the connections between parents and children, is called '''walking the tree''', and the action is a ''walk'' of the tree. Often, an operation might be performed when a pointer arrives at a particular node. A walk in which each parent node is traversed before its children is called a '''pre-order''' walk; a walk in which the children are traversed before their respective parents are traversed is called a '''post-order''' walk; a walk in which a node's left subtree, then the node itself, and finally its right subtree are traversed is called an '''in-order''' traversal. (This last scenario, referring to exactly two subtrees, a left subtree and a right subtree, assumes specifically a [[binary tree]].) A '''level-order''' walk effectively performs a [[breadth-first search]] over the entirety of a tree; nodes are traversed level by level, where the root node is visited first, followed by its direct child nodes and their siblings, followed by its grandchild nodes and their siblings, etc., until all nodes in the tree have been traversed.

==Representations==

There are many different ways to represent trees. In working memory, nodes are typically [[Dynamic memory allocation|dynamically allocated]] records with pointers to their children, their parents, or both, as well as any associated data.  If of a fixed size, the nodes might be stored in a list. Nodes and relationships between nodes might be stored in a separate special type of [[adjacency list]]. In [[relational database]]s, nodes are typically represented as table rows, with indexed row IDs facilitating pointers between parents and children.

Nodes can also be stored as items in an [[Array data structure|array]], with relationships between them determined by their positions in the array (as in a [[binary heap]]).

A [[binary tree]] can be implemented as a list of lists: the head of a list (the value of the first term) is the left child (subtree), while the tail (the list of second and subsequent terms) is the right child (subtree). This can be modified to allow values as well, as in Lisp [[S-expression]]s, where the head (value of first term) is the value of the node, the head of the tail (value of second term) is the left child, and the tail of the tail (list of third and subsequent terms) is the right child.

Ordered trees can be naturally encoded by finite sequences, for example with natural numbers.<ref name="Afanasiev2005">
{{cite journal |author1=L. Afanasiev |author2=P. Blackburn |author3=I. Dimitriou |author4=B. Gaiffe |author5=E. Goris |author6=M. Marx |author7=M. de Rijke |year=2005 |title=PDL for ordered trees |url=http://mashup2.science.uva.nl/marx/pub/recent/pdl-trees-final.pdf#page=3 |journal=Journal of Applied Non-Classical Logics |volume=15 |issue=2 |pages=115–135 |doi=10.3166/jancl.15.115-135 |s2cid=1979330}}</ref>

==Examples of trees and non-trees==

{{multiple image
| align             = center
| image1            = Directed graph, disjoint.svg
| width1            = 130
| caption1          = {{color|#800000|Not a tree}}: two non-[[Connectivity (graph theory)#Definitions of components, cuts and connectivity|connected]] parts, A→B and C→D→E. There is more than one root.
| image2            = Directed graph with branching SVG.svg
| width2            = 101
| caption2          = {{color|#800000|Not a tree}}: undirected cycle 1-2-4-3. 4 has more than one parent (inbound edge).
| image3            = Directed graph, cyclic.svg
| width3            = 211
| caption3          = {{color|#800000|Not a tree}}: cycle B→C→E→D→B. B has more than one parent (inbound edge).
| image4            = Graph single node.svg
| width4            = 92
| caption4          = {{color|#800000|Not a tree}}: cycle A→A. A is the root but it also has a parent.
| image5            = Directed Graph Edge.svg
| width5            = 173
| caption5          = Each linear list is trivially {{color|#008000|a tree}}.
}}

==Type theory==
{{unreferenced section|date=April 2022}}
As an [[abstract data type]], the abstract tree type {{mvar|T}} with values of some type {{mvar|E}} is defined, using the abstract forest type {{mvar|F}} (list of trees), by the functions:
: value: {{mvar|T}} → {{mvar|E}}
: children: {{mvar|T}} → {{mvar|F}}
: nil: () → {{mvar|F}}
: node: {{mvar|E}} × {{mvar|F}} → {{mvar|T}}

with the axioms:
: value(node({{mvar|e}}, {{mvar|f}})) = {{mvar|e}}
: children(node({{mvar|e}}, {{mvar|f}})) = {{mvar|f}}

In terms of [[type theory]], a tree is an [[Recursive data type|inductive type]] defined by the constructors {{math|nil}} (empty forest) and {{math|node}} (tree with root node with given value and children).

==Mathematical terminology==
{{unreferenced section|date=April 2022}}
Viewed as a whole, a tree data structure is an [[ordered tree]], generally with values attached to each node. Concretely, it is (if required to be non-empty):
* A [[rooted tree]] with the "away from root" direction (a more narrow term is an "[[Arborescence (graph theory)|arborescence]]"), meaning:
** A [[directed graph]],
** whose underlying [[undirected graph]] is a [[tree (graph theory)|tree]] (any two vertices are connected by exactly one simple path),<ref>{{Cite book |last=Levin |first=Oscar |url=https://discrete.openmathbooks.org/dmoi3/sec_trees.html |title=Discrete Mathematics: An Open Introduction |date=31 December 2018 |isbn=978-1792901690 |edition=3rd |pages=247|publisher=Amazon Digital Services LLC - Kdp }}</ref>
** with a distinguished root (one vertex is designated as the root),
** which determines the direction on the edges (arrows point away from the root; given an edge, the node that the edge points from is called the ''parent'' and the node that the edge points to is called the ''child''), together with:
* an ordering on the child nodes of a given node, and
* a value (of some data type) at each node.

Often trees have a fixed (more properly, bounded) [[branching factor]] ([[outdegree]]), particularly always having two child nodes (possibly empty, hence ''at most'' two ''non-empty'' child nodes), hence a "binary tree".

Allowing empty trees makes some definitions simpler, some more complicated: a rooted tree must be non-empty, hence if empty trees are allowed the above definition instead becomes "an empty tree or a rooted tree such that ...". On the other hand, empty trees simplify defining fixed branching factor: with empty trees allowed, a binary tree is a tree such that every node has exactly two children, each of which is a tree (possibly empty).

==Applications==
Trees are commonly used to represent or manipulate [[hierarchical]] data in applications such as:
* [[File systems]] for:
** [[Directory structure]] used to organize subdirectories and files ([[symbolic link]]s create non-tree graphs, as do multiple [[hard link]]s to the same file or directory)
** The mechanism used to allocate and link blocks of data on the storage device
* [[Class hierarchy]] or "inheritance tree" showing the relationships among [[Class (programming)|classes]] in [[object-oriented programming]]; [[multiple inheritance]] produces non-tree graphs
* [[Abstract syntax tree]]s for computer languages
* [[Natural language processing]]:
** [[Parse tree]]s
** Modeling utterances in a [[generative grammar]]
** [[Dialogue tree]] for generating conversations
* [[Document Object Model]]s ("DOM tree") of [[XML]] and [[HTML]] documents
* [[Search tree]]s store data in a way that makes an efficient [[search algorithm]] possible via [[tree traversal]]
** A [[binary search tree]] is a type of [[binary tree]]
* Representing [[sorting algorithm|sorted lists]] of data
* [[Computer-generated imagery]]:
** [[Space partitioning#Data structures|Space partitioning]], including [[binary space partitioning]] 
** [[Digital compositing]]
* Storing [[Barnes–Hut simulation|Barnes–Hut]] trees used to simulate galaxies
* Implementing [[Heap (data structure)|heaps]]
* [[Nested set collection]]s
* [[Taxonomy (general)#Applications|Hierarchical taxonomies]] such as the [[Dewey Decimal Classification]] with sections of increasing specificity.
* [[Hierarchical temporal memory]]
* [[Genetic programming]]
* [[Hierarchical clustering]]

Trees can be used to represent and manipulate various mathematical structures, such as:
* Paths through an arbitrary [[Graph (discrete mathematics)|node-and-edge graph]] (including [[multigraph]]s), by making multiple nodes in the tree for each graph node used in multiple paths
* Any [[Hierarchy (mathematics)|mathematical hierarchy]]

Tree structures are often used for mapping the relationships between things, such as:
* Components and subcomponents which can be visualized in an [[exploded-view drawing]]
* [[Subroutine call]]s used to identify which subroutines in a program call other subroutines non recursively
* Inheritance of DNA among species by [[evolution]], of source code by software projects (e.g. [[:File:Linux_Distribution_Timeline_Dec._2020.svg|Linux distribution timeline]]), of designs in various types of cars, etc.
* The contents of hierarchical [[namespace]]s

[[JSON]] and [[YAML]] documents can be thought of as trees, but are typically represented by nested [[List (abstract data type)|lists]] and [[associative array|dictionaries]].

==See also==
* [[Distributed tree search]]
* [[:Category:Trees (data structures)]] (catalogs types of computational trees)

==Notes==
{{notelist}}

==References==
{{Reflist}}
{{refbegin}}
{{refend}}

==Further reading==
* [[Donald Knuth]]. ''[[The Art of Computer Programming]]: Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89683-4}} . Section 2.3: Trees, pp.&nbsp;308–423.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}}. Section 10.4: Representing rooted trees, pp.&nbsp;214–217. Chapters 12–14 (Binary Search Trees, Red–Black Trees, Augmenting Data Structures), pp.&nbsp;253–320.

==External links==
{{Commons category|Tree structures}}
* [https://xlinux.nist.gov/dads/HTML/tree.html Description] from the [[Dictionary of Algorithms and Data Structures]]

{{CS-Trees}}
{{Graph traversal algorithms}}
{{Data structures}}

{{DEFAULTSORT:Tree (Data Structure)}}
[[Category:Data types]]
[[Category:Trees (data structures)| ]]
[[Category:Knowledge representation]]
[[Category:Abstract data types]]

[[de:Baum (Graphentheorie)]]