Tree (data structure)

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Not to be confused with trie, a specific type of tree data structure. Tree (data structure)_sentence_0

Not to be confused with tree (graph theory), a specific type of mathematical object. Tree (data structure)_sentence_1

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. Tree (data structure)_sentence_2

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root. Tree (data structure)_sentence_3

Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. Tree (data structure)_sentence_4

Both these perspectives are useful: while a tree can be analyzed mathematically as a whole, when actually represented as a data structure it is usually represented and worked with separately by node (rather than as a set of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). Tree (data structure)_sentence_5

For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general, as a data structure, a given node only contains the list of its children but does not contain a reference to its parent (if any). Tree (data structure)_sentence_6

Common uses Tree (data structure)_section_0

Tree (data structure)_unordered_list_0

Terminology Tree (data structure)_section_1

A node is a structure which may contain a value or condition, or represent a separate data structure (which could be a tree of its own). Tree (data structure)_sentence_7

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). Tree (data structure)_sentence_8

A node that has a child is called the child's parent node (or superior). Tree (data structure)_sentence_9

A node has at most one parent, but possibly many ancestor nodes, such as the parent's parent. Tree (data structure)_sentence_10

Child nodes with the same parent are sibling nodes. Tree (data structure)_sentence_11

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. Tree (data structure)_sentence_12

Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes. Tree (data structure)_sentence_13

The topmost node in a tree is called the root node. Tree (data structure)_sentence_14

Depending on the definition, a tree may be required to have a root node (in which case all trees are non-empty), or may be allowed to be empty, in which case it does not necessarily have a root node. Tree (data structure)_sentence_15

Being the topmost node, the root node will not have a parent. Tree (data structure)_sentence_16

It is the node at which algorithms on the tree begin, since as a data structure, one can only pass from parents to children. Tree (data structure)_sentence_17

Note that some algorithms (such as post-order depth-first search) begin at the root, but first visit leaf nodes (access the value of leaf nodes), only visit the root last (i.e., they first access the children of the root, but only access the value of the root last). Tree (data structure)_sentence_18

All other nodes can be reached from it by following edges or links. Tree (data structure)_sentence_19

(In the formal definition, each such path is also unique.) Tree (data structure)_sentence_20

In diagrams, the root node is conventionally drawn at the top. Tree (data structure)_sentence_21

In some trees, such as heaps, the root node has special properties. Tree (data structure)_sentence_22

Every node in a tree can be seen as the root node of the subtree rooted at that node. Tree (data structure)_sentence_23

The height of a node is the length of the longest downward path to a leaf from that node. Tree (data structure)_sentence_24

The height of the root is the height of the tree. Tree (data structure)_sentence_25

The depth of a node is the length of the path to its root (i.e., its root path). Tree (data structure)_sentence_26

This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. Tree (data structure)_sentence_27

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. Tree (data structure)_sentence_28

Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1. Tree (data structure)_sentence_29

A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. Nodes thus correspond to subtrees (each node corresponds to the subtree of itself and all its descendants) – the subtree corresponding to the root node is the entire tree, and each node is the root node of the subtree it determines; the subtree corresponding to any other node is called a proper subtree (by analogy to a proper subset). Tree (data structure)_sentence_30

Other terms used with trees: Tree (data structure)_sentence_31

Tree (data structure)_description_list_1

  • Neighbor: Parent or child.Tree (data structure)_item_1_10
  • Ancestor: A node reachable by repeated proceeding from child to parent.Tree (data structure)_item_1_11
  • Descendant: A node reachable by repeated proceeding from parent to child. Also known as subchild.Tree (data structure)_item_1_12
  • Internal node: A node with at least one child.Tree (data structure)_item_1_13
  • Degree: For a given node, its number of children. A leaf has necessarily degree zero.Tree (data structure)_item_1_14
  • Degree of tree: The degree of a tree is the maximum degree of a node in the tree.Tree (data structure)_item_1_15
  • Distance: The number of edges along the shortest path between two nodes.Tree (data structure)_item_1_16
  • Level: 1 + the number of edges between a node and the root, i.e. (depth + 1)Tree (data structure)_item_1_17
  • Width: The number of nodes in a level.Tree (data structure)_item_1_18
  • Breadth: The number of leaves.Tree (data structure)_item_1_19
  • Forest: A set of n ≥ 0 disjoint trees.Tree (data structure)_item_1_20
  • Ordered tree: A rooted tree in which an ordering is specified for the children of each vertex.Tree (data structure)_item_1_21
  • Size of a tree: Number of nodes in the tree.Tree (data structure)_item_1_22

Preliminary definition Tree (data structure)_section_2

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. Tree (data structure)_sentence_32

A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees. Tree (data structure)_sentence_33

Drawing trees Tree (data structure)_section_3

Trees are often drawn in the plane. Tree (data structure)_sentence_34

Ordered trees can be represented essentially uniquely in the plane, and are hence called plane trees, as follows: if one fixes a conventional order (say, counterclockwise), and arranges the child nodes in that order (first incoming parent edge, then first child edge, etc.), this yields an embedding of the tree in the plane, unique up to ambient isotopy. Tree (data structure)_sentence_35

Conversely, such an embedding determines an ordering of the child nodes. Tree (data structure)_sentence_36

If one places the root at the top (parents above children, as in a family tree) and places all nodes that are a given distance from the root (in terms of number of edges: the "level" of a tree) on a given horizontal line, one obtains a standard drawing of the tree. Tree (data structure)_sentence_37

Given a binary tree, the first child is on the left (the "left node"), and the second child is on the right (the "right node"). Tree (data structure)_sentence_38

Common operations Tree (data structure)_section_4

Tree (data structure)_unordered_list_2

  • Enumerating all the itemsTree (data structure)_item_2_23
  • Enumerating a section of a treeTree (data structure)_item_2_24
  • Searching for an itemTree (data structure)_item_2_25
  • Adding a new item at a certain position on the treeTree (data structure)_item_2_26
  • Deleting an itemTree (data structure)_item_2_27
  • Pruning: Removing a whole section of a treeTree (data structure)_item_2_28
  • Grafting: Adding a whole section to a treeTree (data structure)_item_2_29
  • Finding the root for any nodeTree (data structure)_item_2_30
  • Finding the lowest common ancestor of two nodesTree (data structure)_item_2_31

Traversal and search methods Tree (data structure)_section_5

Main article: Tree traversal Tree (data structure)_sentence_39

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. Tree (data structure)_sentence_40

Often, an operation might be performed when a pointer arrives at a particular node. Tree (data structure)_sentence_41

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. Tree (data structure)_sentence_42

(This last scenario, referring to exactly two subtrees, a left subtree and a right subtree, assumes specifically a binary tree.) Tree (data structure)_sentence_43

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. Tree (data structure)_sentence_44

Representations Tree (data structure)_section_6

There are many different ways to represent trees; common representations represent the nodes as dynamically allocated records with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap). Tree (data structure)_sentence_45

Indeed, a binary tree can be implemented as a list of lists (a list where the values are 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). Tree (data structure)_sentence_46

This can be modified to allow values as well, as in Lisp S-expressions, 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. Tree (data structure)_sentence_47

In general a node in a tree will not have pointers to its parents, but this information can be included (expanding the data structure to also include a pointer to the parent) or stored separately. Tree (data structure)_sentence_48

Alternatively, upward links can be included in the child node data, as in a threaded binary tree. Tree (data structure)_sentence_49

Generalizations Tree (data structure)_section_7

Digraphs Tree (data structure)_section_8

If edges (to child nodes) are thought of as references, then a tree is a special case of a digraph, and the tree data structure can be generalized to represent directed graphs by removing the constraints that a node may have at most one parent, and that no cycles are allowed. Tree (data structure)_sentence_50

Edges are still abstractly considered as pairs of nodes, however, the terms parent and child are usually replaced by different terminology (for example, source and target). Tree (data structure)_sentence_51

Different implementation strategies exist: a digraph can be represented by the same local data structure as a tree (node with value and list of children), assuming that "list of children" is a list of references, or globally by such structures as adjacency lists. Tree (data structure)_sentence_52

In graph theory, a tree is a connected acyclic graph; unless stated otherwise, in graph theory trees and graphs are assumed undirected. Tree (data structure)_sentence_53

There is no one-to-one correspondence between such trees and trees as data structure. Tree (data structure)_sentence_54

We can take an arbitrary undirected tree, arbitrarily pick one of its vertices as the root, make all its edges directed by making them point away from the root node – producing an arborescence – and assign an order to all the nodes. Tree (data structure)_sentence_55

The result corresponds to a tree data structure. Tree (data structure)_sentence_56

Picking a different root or different ordering produces a different one. Tree (data structure)_sentence_57

Given a node in a tree, its children define an ordered forest (the union of subtrees given by all the children, or equivalently taking the subtree given by the node itself and erasing the root). Tree (data structure)_sentence_58

Just as subtrees are natural for recursion (as in a depth-first search), forests are natural for corecursion (as in a breadth-first search). Tree (data structure)_sentence_59

Via mutual recursion, a forest can be defined as a list of trees (represented by root nodes), where a node (of a tree) consists of a value and a forest (its children): Tree (data structure)_sentence_60

Data type versus data structure Tree (data structure)_section_9

There is a distinction between a tree as an abstract data type and as a concrete data structure, analogous to the distinction between a list and a linked list. Tree (data structure)_sentence_61

As a data type, a tree has a value and children, and the children are themselves trees; the value and children of the tree are interpreted as the value of the root node and the subtrees of the children of the root node. Tree (data structure)_sentence_62

To allow finite trees, one must either allow the list of children to be empty (in which case trees can be required to be non-empty, an "empty tree" instead being represented by a forest of zero trees), or allow trees to be empty, in which case the list of children can be of fixed size (branching factor, especially 2 or "binary"), if desired. Tree (data structure)_sentence_63

As a data structure, a linked tree is a group of nodes, where each node has a value and a list of references to other nodes (its children). Tree (data structure)_sentence_64

There is also the requirement that no two "downward" references point to the same node. Tree (data structure)_sentence_65

In practice, nodes in a tree commonly include other data as well, such as next/previous references, references to their parent nodes, or nearly anything. Tree (data structure)_sentence_66

Due to the use of references to trees in the linked tree data structure, trees are often discussed implicitly assuming that they are being represented by references to the root node, as this is often how they are actually implemented. Tree (data structure)_sentence_67

For example, rather than an empty tree, one may have a null reference: a tree is always non-empty, but a reference to a tree may be null. Tree (data structure)_sentence_68

Recursive Tree (data structure)_section_10

Recursively, as a data type a tree is defined as a value (of some data type, possibly empty), together with a list of trees (possibly an empty list), the subtrees of its children; symbolically: Tree (data structure)_sentence_69

Tree (data structure)_description_list_3

  • t: v [t, ..., t[k]]Tree (data structure)_item_3_32

(A tree t consists of a value v and a list of other trees.) Tree (data structure)_sentence_70

More elegantly, via mutual recursion, of which a tree is one of the most basic examples, a tree can be defined in terms of forest (a list of trees), where a tree consists of a value and a forest (the subtrees of its children): Tree (data structure)_sentence_71

Tree (data structure)_description_list_4

  • f: [t, ..., t[k]]Tree (data structure)_item_4_33
  • t: v fTree (data structure)_item_4_34

Note that this definition is in terms of values, and is appropriate in functional languages (it assumes referential transparency); different trees have no connections, as they are simply lists of values. Tree (data structure)_sentence_72

As a data structure, a tree is defined as a node (the root), which itself consists of a value (of some data type, possibly empty), together with a list of references to other nodes (list possibly empty, references possibly null); symbolically: Tree (data structure)_sentence_73

Tree (data structure)_description_list_5

  • n: v [&n, ..., &n[k]]Tree (data structure)_item_5_35

(A node n consists of a value v and a list of references to other nodes.) Tree (data structure)_sentence_74

This data structure defines a directed graph, and for it to be a tree one must add a condition on its global structure (its topology), namely that at most one reference can point to any given node (a node has at most a single parent), and no node in the tree point to the root. Tree (data structure)_sentence_75

In fact, every node (other than the root) must have exactly one parent, and the root must have no parents. Tree (data structure)_sentence_76

Indeed, given a list of nodes, and for each node a list of references to its children, one cannot tell if this structure is a tree or not without analyzing its global structure and that it is in fact topologically a tree, as defined below. Tree (data structure)_sentence_77

Type theory Tree (data structure)_section_11

As an abstract data type, the abstract tree type T with values of some type E is defined, using the abstract forest type F (list of trees), by the functions: Tree (data structure)_sentence_78

Tree (data structure)_description_list_6

  • value: T → ETree (data structure)_item_6_36
  • children: T → FTree (data structure)_item_6_37
  • nil: () → FTree (data structure)_item_6_38
  • node: E × F → TTree (data structure)_item_6_39

with the axioms: Tree (data structure)_sentence_79

Tree (data structure)_description_list_7

  • value(node(e, f)) = eTree (data structure)_item_7_40
  • children(node(e, f)) = fTree (data structure)_item_7_41

In terms of type theory, a tree is an inductive type defined by the constructors nil (empty forest) and node (tree with root node with given value and children). Tree (data structure)_sentence_80

Mathematical terminology Tree (data structure)_section_12

Viewed as a whole, a tree data structure is an ordered tree, generally with values attached to each node. Tree (data structure)_sentence_81

Concretely, it is (if required to be non-empty): Tree (data structure)_sentence_82

Tree (data structure)_unordered_list_8

  • A rooted tree with the "away from root" direction (a more narrow term is an "arborescence"), meaning:Tree (data structure)_item_8_42
    • A directed graph,Tree (data structure)_item_8_43
    • whose underlying undirected graph is a tree (any two vertices are connected by exactly one simple path),Tree (data structure)_item_8_44
    • with a distinguished root (one vertex is designated as the root),Tree (data structure)_item_8_45
    • 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),Tree (data structure)_item_8_46

together with: Tree (data structure)_sentence_83

Tree (data structure)_unordered_list_9

  • an ordering on the child nodes of a given node, andTree (data structure)_item_9_47
  • a value (of some data type) at each node.Tree (data structure)_item_9_48

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". Tree (data structure)_sentence_84

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 ...". Tree (data structure)_sentence_85

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). Tree (data structure)_sentence_86

The complete sets of operations on the tree must include fork operation. Tree (data structure)_sentence_87

Mathematical definition Tree (data structure)_section_13

Unordered tree Tree (data structure)_section_14

Mathematically, an unordered tree (or "algebraic tree") can be defined as an algebraic structure (X, parent) where X is the non-empty carrier set of nodes and parent is a function on X which assigns each node x its "parent" node, parent(x). Tree (data structure)_sentence_88

The structure is subject to the condition that every non-empty subalgebra must have the same fixed point. Tree (data structure)_sentence_89

That is, there must be a unique "root" node r, such that parent(r) = r and for every node x, some iterative application parent(parent(⋯parent(x)⋯)) equals r. Tree (data structure)_sentence_90

There are several equivalent definitions. Tree (data structure)_sentence_91

As the closest alternative, one can define unordered trees as partial algebras (X, parent) which are obtained from the total algebras described above by letting parent(r) be undefined. Tree (data structure)_sentence_92

That is, the root r is the only node on which the parent function is not defined and for every node x, the root is reachable from x in the directed graph (X, parent). Tree (data structure)_sentence_93

This definition is in fact coincident with that of an anti-arborescence. Tree (data structure)_sentence_94

The TAoCP book uses the term oriented tree. Tree (data structure)_sentence_95

The box on the right describes the partial algebra (X, parent) as a relational structure (X, ≺). Tree (data structure)_sentence_96

If (1) is replaced by Tree (data structure)_sentence_97

then condition (2) becomes redundant. Tree (data structure)_sentence_98

Using this definition, dedicated terminology can be provided for generalizations of unordered trees that correspond to distinguished subsets of the listed conditions: Tree (data structure)_sentence_99

Tree (data structure)_unordered_list_10

  • (1,2,3) – directed pseudotree,Tree (data structure)_item_10_49
  • (3) – directed pseudoforest,Tree (data structure)_item_10_50
  • (3,4) – unordered forest (whose components are unordered trees),Tree (data structure)_item_10_51
  • (4) – directed acyclic graph, assumed that X is finite,Tree (data structure)_item_10_52
  • (1',4) – acyclic accessible pointed graph (then condition (2) holds implicitly).Tree (data structure)_item_10_53

Another equivalent definition of an unordered tree is that of a set-theoretic tree that is singly-rooted and whose height is at most ω (a "finite-ish" tree). Tree (data structure)_sentence_100

That is, the algebraic structures (X, parent) are equivalent to partial orders (X, ≤) that have a top element r and whose every principal upset (aka principal filter) is a finite chain. Tree (data structure)_sentence_101

To be precise, we should speak about an inverse set-theoretic tree since the set-theoretic definition usually employs opposite ordering. Tree (data structure)_sentence_102

The correspondence between (X, parent) and (X, ≤) is established via reflexive transitive closure / reduction, with the reduction resulting in the "partial" version without the root cycle. Tree (data structure)_sentence_103

The definition of trees in descriptive set theory (DST) utilizes the representation of partial orders (X, ≥) as prefix orders between finite sequences. Tree (data structure)_sentence_104

In turns out that up to isomorphism, there is a one-to-one correspondence between the (inverse of) DST trees and the tree structures defined so far. Tree (data structure)_sentence_105

We can refer to the four equivalent characterizations as to tree as an algebra, tree as a partial algebra, tree as a partial order, and tree as a prefix order. Tree (data structure)_sentence_106

There is also a fifth equivalent definition – that of a graph-theoretic rooted tree which is just a connected acyclic rooted graph. Tree (data structure)_sentence_107

The expression of trees as (partial) algebras (also called functional graphs) (X, parent) follows directly the implementation of tree structures using parent pointers. Tree (data structure)_sentence_108

Typically, the partial version is used in which the root node has no parent defined. Tree (data structure)_sentence_109

However, in some implementations or models even the parent(r) = r circularity is established. Tree (data structure)_sentence_110

Notable examples: Tree (data structure)_sentence_111

Tree (data structure)_unordered_list_11

  • The Linux where "The root dentry has a d_parent that points to itself"..Tree (data structure)_item_11_54
  • The concept of an instantiation treeTree (data structure)_item_11_55

from object-oriented programming. Tree (data structure)_sentence_112

In this case, the root node is the top metaclass – the only class that is a direct instance of itself. Tree (data structure)_sentence_113

Note that the above definition admits infinite trees. Tree (data structure)_sentence_114

This allows for the description of infinite structures supported by some implementations via lazy evaluation. Tree (data structure)_sentence_115

A notable example is the infinite regress of eigenclasses from the Ruby object model. Tree (data structure)_sentence_116

In this model, the tree established via superclass links between non-terminal objects is infinite and has an infinite branch (a single infinite branch of "helix" objects – see the diagram). Tree (data structure)_sentence_117

Sibling sets Tree (data structure)_section_15

In every unordered tree (X, parent) there is a distinguished partition of the set X of nodes into sibling sets. Tree (data structure)_sentence_118

Two non-root nodes x, y belong to the same sibling set if parent(x) = parent(y). Tree (data structure)_sentence_119

The root node r forms the singleton sibling set {r}. Tree (data structure)_sentence_120

A tree is said to be locally finite or finitely branching if each of its sibling sets is finite. Tree (data structure)_sentence_121

Each pair of distinct siblings is incomparable in ≤. Tree (data structure)_sentence_122

This is why the word unordered is used in the definition. Tree (data structure)_sentence_123

Such a terminology might become misleading when all sibling sets are singletons, i.e. when the set X of all nodes is totally ordered (and thus well-ordered) by ≤ In such a case we might speak about a singly-branching tree instead. Tree (data structure)_sentence_124

Using set inclusion Tree (data structure)_section_16

As with every partially ordered set, tree structures (X, ≤) can be represented by inclusion order – by set systems in which ≤ is coincident with ⊆, the induced inclusion order. Tree (data structure)_sentence_125

Consider a structure (U, ℱ) such that U is a non-empty set, and ℱ is a set of subsets of U such that the following are satisfied (by Nested Set Collection definition): Tree (data structure)_sentence_126

Tree (data structure)_ordered_list_12

  1. ∅ ∉ ℱ. (That is, (U, ℱ) is a hypergraph.)Tree (data structure)_item_12_56
  2. U ∈ ℱ.Tree (data structure)_item_12_57
  3. For every X, Y from ℱ, X ∩ Y ∈ {∅, X, Y}. (That is, ℱ is a laminar family.)Tree (data structure)_item_12_58
  4. For every X from ℱ, there are only finitely many Y from ℱ such that X ⊆ Y.Tree (data structure)_item_12_59

Then the structure (ℱ, ⊆) is an unordered tree whose root equals U. Conversely, if (U, ≤) is an unordered tree, and ℱ is the set {↓x | x ∈ U} of all principal ideals of (U, ≤) then the set system (U, ℱ) satisfies the above properties. Tree (data structure)_sentence_127

The set-system view of tree structures provides the default semantic model – in the majority of most popular cases, tree data structures represent containment hierarchy. Tree (data structure)_sentence_128

This also offers a justification for order direction with the root at the top: The root node is a greater container than any other node. Tree (data structure)_sentence_129

Notable examples: Tree (data structure)_sentence_130

Tree (data structure)_unordered_list_13

Well-founded trees Tree (data structure)_section_17

An unordered tree (X, ≤) is well-founded if the strict partial order < is a well-founded relation. Tree (data structure)_sentence_131

In particular, every finite tree is well-founded. Tree (data structure)_sentence_132

Assuming the axiom of dependent choice a tree is well-founded if and only if it has no infinite branch. Tree (data structure)_sentence_133

Well-founded trees can be defined recursively – by forming trees from a disjoint union of smaller trees. Tree (data structure)_sentence_134

For the precise definition, suppose that X is a set of nodes. Tree (data structure)_sentence_135

Using the reflexivity of partial orders, we can identify any tree (Y, ≤) on a subset of X with its partial order (≤) – a subset of X × X. Tree (data structure)_sentence_136

The set ℛ of all relations R that form a well-founded tree (Y, R) on a subset Y of X is defined in stages ℛi, so that ℛ = ⋃{ℛi | i is ordinal}. Tree (data structure)_sentence_137

For each ordinal number i, let R belong to the i-th stage ℛi if and only if R is equal to Tree (data structure)_sentence_138

Tree (data structure)_description_list_14

  • ⋃ℱ ∪ ((dom(⋃ℱ) ∪ {x}) × {x})Tree (data structure)_item_14_65

where ℱ is a subset of ⋃{ℛk | k < i} such that elements of ℱ are pairwise disjoint, and x is a node that does not belong to dom(⋃ℱ). Tree (data structure)_sentence_139

(We use dom(S) to denote the domain of a relation S.) Observe that the lowest stage ℛ0 consists of single-node trees {(x,x)} since only empty ℱ is possible. Tree (data structure)_sentence_140

In each stage, (possibly) new trees R are built by taking a forest ⋃ℱ with components ℱ from lower stages and attaching a new root x atop of ⋃ℱ. Tree (data structure)_sentence_141

In contrast to the tree height which is at most ω, the rank of well-founded trees is unlimited, see the properties of "unfolding". Tree (data structure)_sentence_142

Using recursive pairs Tree (data structure)_section_18

In computing, a common way to define well-founded trees is via recursive ordered pairs (F, x): a tree is a forest F together with a "fresh" node x. Tree (data structure)_sentence_143

A forest F in turn is a possibly empty set of trees with pairwise disjoint sets of nodes. Tree (data structure)_sentence_144

For the precise definition, proceed similarly as in the construction of names used in the set-theoretic technique of forcing. Tree (data structure)_sentence_145

Let X be a set of nodes. Tree (data structure)_sentence_146

In the superstructure over X, define sets T, ℱ of trees and forests, respectively, and a map nodes : T → ℘(X) assigning each tree t its underlying set of nodes so that: Tree (data structure)_sentence_147

Tree (data structure)_description_list_15

  • (trees over X) t ∈ T ↔ t is a pair (F, x) from ℱ × X such that for all s ∈ F, x ∉ nodes(s), (forests over X) F ∈ ℱ ↔ F is a subset of T such that for every s,t ∈ F, s ≠ t, nodes(s) ∩ nodes(t) = ∅ }}, (nodes of trees) y ∈ nodes(t) ↔ t = (F, x) ∈ T and either y = x or y ∈ nodes(s) for some s ∈ F }}.Tree (data structure)_item_15_66

Circularities in the above conditions can be eliminated by stratifying each of T, ℱ and nodes into stages like in the previous subsection. Tree (data structure)_sentence_148

Subsequently, define a "subtree" relation ≤ on T as the reflexive transitive closure of the "immediate subtree" relation ≺ defined between trees by Tree (data structure)_sentence_149

Tree (data structure)_description_list_16

  • s ≺ t ↔ s ∈ π1(t)Tree (data structure)_item_16_67

where π1(t) is the projection of t onto the first coordinate; i.e., it is the forest F such that t = (F, x) for some x ∈ X. Tree (data structure)_sentence_150

It can be observed that (T, ≤) is a multitree: for every t ∈ T, the principal ideal ↓t ordered by ≤ is a well-founded tree as a partial order. Tree (data structure)_sentence_151

Moreover, for every tree t ∈ T, its "nodes"-order structure (nodes(t), ≤t) is given by x ≤t y if and only if there are forests F, G ∈ ℱ such that both (F, x) and (G, y) are subtrees of t and (F, x) ≤ (G, y). Tree (data structure)_sentence_152

Using arrows Tree (data structure)_section_19

Another formalization as well as generalization of unordered trees can be obtained by reifying parent-child pairs of nodes. Tree (data structure)_sentence_153

Each such ordered pair can be regarded as an abstract entity – an "arrow". Tree (data structure)_sentence_154

This results in a multidigraph (X, A, s, t) where X is the set of nodes, A is the set of arrows, and s and t are functions from A to X assigning each arrow its source and target, respectively. Tree (data structure)_sentence_155

The structure is subject to the following conditions: Tree (data structure)_sentence_156

Tree (data structure)_ordered_list_17

  1. (A, s ○ t) is an unordered tree, as a total algebra.Tree (data structure)_item_17_68
  2. The t map is a bijection between arrows and nodes.Tree (data structure)_item_17_69

In (1), the composition symbol ○ is to be interpreted left-to-right. Tree (data structure)_sentence_157

The condition says that inverse consecutivity of arrows is a total child-to-parent map. Tree (data structure)_sentence_158

Let this parent map between arrows be denoted p, i.e. p = s ○ t. Then we also have s = p ○ t, thus a multidigraph satisfying (1,2) can also be axiomatized as (X, A, p, t), with the parent map p instead of s as a definitory constituent. Tree (data structure)_sentence_159

Observe that the root arrow is necessarily a loop, i.e. its source and target coincide. Tree (data structure)_sentence_160

An important generalization of the above structure is established by allowing the target map t to be many-to-one. Tree (data structure)_sentence_161

This means that (2) is weakened to Tree (data structure)_sentence_162

Tree (data structure)_description_list_18

  • (2') The t map is surjective – each node is the target of some arrow.Tree (data structure)_item_18_70

Note that condition (1) asserts that only leaf arrows are allowed to have the same target. Tree (data structure)_sentence_163

That is, the restriction of t to the range of p is still injective. Tree (data structure)_sentence_164

Multidigraphs satisfying (1,2') can be called "arrow trees" – their tree characteristics is imposed on arrows rather than nodes. Tree (data structure)_sentence_165

These structures can be regarded as the most essential abstraction of the Linux VFS because they reflect the hard-link structure of filesystems. Tree (data structure)_sentence_166

Nodes are called inodes, arrows are dentries (or hard links). Tree (data structure)_sentence_167

The parent and target maps p and t are respectively represented by d_parent and d_inode fields in the dentry data structure. Tree (data structure)_sentence_168

Each inode is assigned a fixed file type, of which the type plays a special role of "designed parents": Tree (data structure)_sentence_169

Using dashed style for the first half of the root loop indicates that, similarly to the parent map, there is a partial version for the source map s in which the source of the root arrow is undefined. Tree (data structure)_sentence_170

This variant is employed for further generalization, see #Using paths in a multidigraph. Tree (data structure)_sentence_171

Using paths in a digraph Tree (data structure)_section_20

Unordered trees naturally arise by "unfolding" of accessible pointed graphs. Tree (data structure)_sentence_172

Let ℛ = (X, R, r) be a pointed relational structure, i.e. such that X is the set of nodes, R is a relation between nodes (a subset of X × X), and r is a distinguished "root" node. Tree (data structure)_sentence_173

Assume further that ℛ is accessible, which means that X equals the preimage of {r} under the reflexive transitive closure of R, and call such a structure an accessible pointed graph or apg for short. Tree (data structure)_sentence_174

(⁎) Then one can derive another apg ℛ' = (X', R', r') – the unfolding of ℛ – as follows: Tree (data structure)_sentence_175

Tree (data structure)_unordered_list_19

  • X' is the set of reversed paths to r, i.e. the set of non-empty finite sequences p of nodes (elements of X) such that (a) consecutive members of p are inversely R-related, and (b) the first member of p is the root r,Tree (data structure)_item_19_71
  • R' is a relation between paths from X' such that paths p and q are R'-related if and only if p = q ⁎ [x] for some node x (i.e. q is a maximal proper prefix of p, the "popped" p), andTree (data structure)_item_19_72
  • r' is the one-element sequence [r].Tree (data structure)_item_19_73

Apparently, the structure (X', R') is an unordered tree in the "partial-algebra" version: R' is a partial map that relates each non-root element of X' to its parent by path popping. Tree (data structure)_sentence_176

The root element is obviously r'. Tree (data structure)_sentence_177

Moreover, the following properties are satisfied: Tree (data structure)_sentence_178

Tree (data structure)_unordered_list_20

  • ℛ is isomorphic to its unfolding ℛ' if and only if ℛ is a tree (⁑). (In particular, unfolding is idempotent, up to isomorphism.)Tree (data structure)_item_20_74
  • Unfolding preserves well-foundedness: If R is well-founded then so is R'.Tree (data structure)_item_20_75
  • Unfolding preserves rank: If R is well-founded then the ranks of R and R' coincide.Tree (data structure)_item_20_76

Notes: Tree (data structure)_sentence_179

Tree (data structure)_description_list_21

  • (⁎) To establish a concordancy between R and the parent map, the presented definition uses reversed accessibility: r is reachable from any node. In the original definition by P. Aczel, every node is reachable from r (thus, instead of "preimage", the word "image" applies).Tree (data structure)_item_21_77
  • (⁑) We have implicitly introduced a definition of unordered trees as apgs: call an apg ℛ = (X, R, r) a tree if the reduct (X, R) is an unordered tree as a partial algebra. This can be translated as: Every node is accessible by exactly one path.Tree (data structure)_item_21_78

Using paths in a multidigraph Tree (data structure)_section_21

As shown on the example of hard-link structure of file systems, many data structures in computing allow multiple links between nodes. Tree (data structure)_sentence_180

Therefore, in order to properly exhibit the appearance of unordered trees among data structures it is necessary to generalize accessible pointed graphs to multidigraph setting. Tree (data structure)_sentence_181

To simplify the terminology, we make use of the term quiver which is an established synonym for "multidigraph". Tree (data structure)_sentence_182

Let an accessible pointed quiver or apq for short be defined as a structure Tree (data structure)_sentence_183

Tree (data structure)_description_list_22

  • ℳ = (X, A, s, t)Tree (data structure)_item_22_79

where Tree (data structure)_sentence_184

Tree (data structure)_description_list_23

  • X is a set of nodes,Tree (data structure)_item_23_80
  • A is a set of arrows,Tree (data structure)_item_23_81
  • s is a partial function from A to X (the source map), andTree (data structure)_item_23_82
  • t is a total function from A to X (the target map).Tree (data structure)_item_23_83

Thus, ℳ is a "partial multidigraph". Tree (data structure)_sentence_185

The structure is subject to the following conditions: Tree (data structure)_sentence_186

Tree (data structure)_ordered_list_24

  1. There is exactly one "root" arrow, ar, whose source s(ar) is undefined.Tree (data structure)_item_24_84
  2. Every node x ∈ X is reachable via a finite sequence of consecutive arrows starting with the root arrow ar.Tree (data structure)_item_24_85

ℳ is said to be a tree if the target map t is a bijection between arrows and nodes. Tree (data structure)_sentence_187

The unfolding of ℳ is formed by the sequences mentioned in (2) – which are the accessibility paths (cf. Tree (data structure)_sentence_188

Path algebra). Tree (data structure)_sentence_189

As an apq, the unfolding can be written as Tree (data structure)_sentence_190

Tree (data structure)_description_list_25

  • ℳ' = (X', A', s', t')Tree (data structure)_item_25_86

where Tree (data structure)_sentence_191

Tree (data structure)_description_list_26

  • X' is the set of accessibility paths,Tree (data structure)_item_26_87
  • A' coincides with X',Tree (data structure)_item_26_88
  • s' coincides with path popping, andTree (data structure)_item_26_89
  • t' is the identity on X'.Tree (data structure)_item_26_90

Like with apgs, unfolding is idempotent and always results in a tree. Tree (data structure)_sentence_192

The underlying apg is obtained as the structure Tree (data structure)_sentence_193

Tree (data structure)_description_list_27

  • (X, R, t(ar))Tree (data structure)_item_27_91

where Tree (data structure)_sentence_194

Tree (data structure)_description_list_28

  • R = {(t(a),s(a)) | a ∈ A \ {ar‍}‍}‍.Tree (data structure)_item_28_92

The diagram above shows an example of an apq with 1 + 14 arrows. Tree (data structure)_sentence_195

In JavaScript, Python or Ruby, the structure can be created by the following (exactly the same) code: Tree (data structure)_sentence_196

Using names Tree (data structure)_section_22

Unordered trees and their generalizations form the essence of naming systems. Tree (data structure)_sentence_197

There are two prominent examples of naming systems: file systems and (nested) associative arrays. Tree (data structure)_sentence_198

The multidigraph-based structures from previous subsections provided anonymous abstractions for both cases. Tree (data structure)_sentence_199

To obtain naming capabilities, arrows are to be equipped with names as identifiers. Tree (data structure)_sentence_200

A name must be locally unique – within each sibling set of arrows there can be at most one arrow labelled by a given name. Tree (data structure)_sentence_201

Tree (data structure)_table_general_0

sourceTree (data structure)_header_cell_0_0_0 nameTree (data structure)_header_cell_0_0_1 targetTree (data structure)_header_cell_0_0_2
s(a)Tree (data structure)_cell_0_1_0 σ(a)Tree (data structure)_cell_0_1_1 t(a)Tree (data structure)_cell_0_1_2

This can be formalized as a structure Tree (data structure)_sentence_202

Tree (data structure)_description_list_29

  • ℰ = (X, Σ, A, s, σ, t)Tree (data structure)_item_29_93

where Tree (data structure)_sentence_203

Tree (data structure)_description_list_30

  • X is a set of nodes,Tree (data structure)_item_30_94
  • Σ is a set of names,Tree (data structure)_item_30_95
  • A is a set of arrows,Tree (data structure)_item_30_96
  • s is a partial function from A to X,Tree (data structure)_item_30_97
  • σ is a partial function from A to Σ, andTree (data structure)_item_30_98
  • t is a total function from A to X.Tree (data structure)_item_30_99

For an arrow a, constituents of the triple (s(a), σ(a), t(a)) are respectively a's source, name and target. Tree (data structure)_sentence_204

The structure is subject to the following conditions: Tree (data structure)_sentence_205

Tree (data structure)_ordered_list_31

  1. The reduct (X, A, s, t) is an accessible pointed quiver (apq) as defined previously.Tree (data structure)_item_31_100
  2. The name function σ is undefined just for the source-less root arrow.Tree (data structure)_item_31_101
  3. The name function σ is injective in the restriction to every sibling set of arrows, i.e. for every non-root arrows a, b, if s(a) = s(b) and σ(a) = σ(b) then a = b.Tree (data structure)_item_31_102

This structure can be called a nested dictionary or named apq. Tree (data structure)_sentence_206

In computing, such structures are ubiquitous. Tree (data structure)_sentence_207

The table above shows that arrows can be considered "un-reified" as the set A' = {(s(a), σ(a), t(a)) | a ∈ A \ {ar}} of source-name-target triples. Tree (data structure)_sentence_208

This leads to a relational structure (X, Σ, A') which can be viewed as a relational database table. Tree (data structure)_sentence_209

Underlines in source and name indicate primary key. Tree (data structure)_sentence_210

The structure can be rephrased as a deterministic labelled transition system: X is a set of "states", Σ is a set of "labels", A' is a set of "labelled transitions". Tree (data structure)_sentence_211

(Moreover, the root node r = t(ar) is an "initial state", and the accessibility condition means that every state is reachable from the initial state.) Tree (data structure)_sentence_212

The diagram on the right shows a nested dictionary ℰ that has the same underlying multidigraph as the example in the previous subsection. Tree (data structure)_sentence_213

The structure can be created by the code below. Tree (data structure)_sentence_214

Like before, exactly the same code applies for JavaScript, Python and Ruby. Tree (data structure)_sentence_215

First, a substructure, ℰ0, is created by a single assignment of a literal {...} to r. This structure, depicted by full lines, is an "arrow tree" (therefore, it is a spanning tree). Tree (data structure)_sentence_216

The literal in turn appears to be a JSON serialization of ℰ0. Tree (data structure)_sentence_217

Subsequently, the remaining arrows are created by assignments of already existing nodes. Tree (data structure)_sentence_218

Arrows that cause cycles are displayed in blue. Tree (data structure)_sentence_219

In the Linux VFS, the name function σ is represented by the d_name field in the dentry data structure. Tree (data structure)_sentence_220

The ℰ0 structure above demonstrates a correspondence between JSON-representable structures and hard-link structures of file systems. Tree (data structure)_sentence_221

In both cases, there is a fixed set of built-in types of "nodes" of which one type is a container type, except that in JSON, there are in fact two such types – Object and Array. Tree (data structure)_sentence_222

If the latter one is ignored (as well as the distinction between individual primitive data types) then the provided abstractions of file-systems and JSON data are the same – both are arrow trees equipped with naming σ and a distinction of container nodes. Tree (data structure)_sentence_223

Pathnames Tree (data structure)_section_23

The naming function σ of a nested dictionary ℰ naturally extends from arrows to arrow paths. Tree (data structure)_sentence_224

Each sequence p = [a1, ..., an] of consecutive arrows is implicitly assigned a pathname (cf. Tree (data structure)_sentence_225

Pathname) – the sequence σ(p) = [σ(a1), ..., σ(an)] of arrow names. Tree (data structure)_sentence_226

Local uniqueness carries over to arrow paths: different sibling paths have different pathnames. Tree (data structure)_sentence_227

In particular, the root-originating arrow paths are in one-to-one correspondence with their pathnames. Tree (data structure)_sentence_228

This correspondence provides a "symbolic" representation of the unfolding of ℰ via pathnames – the nodes in ℰ are globally identified via a tree of pathnames. Tree (data structure)_sentence_229

Ordered tree Tree (data structure)_section_24

The structures introduced in the previous subsection form just the core "hierarchical" part of tree data structures that appear in computing. Tree (data structure)_sentence_230

In most cases, there is also an additional "horizontal" ordering between siblings. Tree (data structure)_sentence_231

In search trees the order is commonly established by the "key" or value associated with each sibling, but in many trees that is not the case. Tree (data structure)_sentence_232

For example, XML documents, lists within JSON files, and many other structures have order that does not depend on the values in the nodes, but is itself data — sorting the paragraphs of a novel alphabetically would lose information. Tree (data structure)_sentence_233

The correspondent expansion of the previously described tree structures (X, ≤) can be defined by endowing each sibling set with a linear order as follows. Tree (data structure)_sentence_234

An alternative definition according to Kuboyama is presented in the next subsection. Tree (data structure)_sentence_235

An ordered tree is a structure (X, ≤V, ≤S) where X is a non-empty set of nodes and ≤V and ≤S are relations on X called vertical (or also hierarchical) order and sibling order, respectively. Tree (data structure)_sentence_236

The structure is subject to the following conditions: Tree (data structure)_sentence_237

Tree (data structure)_ordered_list_32

  1. (X, ≤V) is a partial order that is an unordered tree as defined in the previous subsection.Tree (data structure)_item_32_103
  2. (X, ≤S) is a partial order.Tree (data structure)_item_32_104
  3. Distinct nodes are comparable in <S if and only if they are siblings:Tree (data structure)_item_32_105
    • (<S) ∪ (>S) = ((≺V) ○ (≻V)) ∖ idX.Tree (data structure)_item_32_106
  4. Every node has only finitely many preceding siblings, i.e. every principal ideal of (X, ≤S) is finite. (This condition can be omitted in the case of finite trees.)Tree (data structure)_item_32_107

Conditions (2) and (3) say that (X, ≤S) is a component-wise linear order, each component being a sibling set. Tree (data structure)_sentence_238

Condition (4) asserts that if a sibling set S is infinite then (S, ≤S) is isomorphic to (ℕ, ≤), the usual ordering of natural numbers. Tree (data structure)_sentence_239

Given this, there are three (another) distinguished partial orders which are uniquely given by the following prescriptions: Tree (data structure)_sentence_240

Tree (data structure)_description_list_33

  • Tree (data structure)_item_33_108
    • (<H) = (≤V) ○ (<S) ○ (≥V) (the horizontal order), (<L⁻) = (>V) ∪ (<H) (the "discordant" linear order), (<L⁺) = (<V) ∪ (<H) (the "concordant" linear order).Tree (data structure)_item_33_109

This amounts to a "V-S-H-L" system of five partial orders ≤V, ≤S, ≤H, ≤L⁺, ≤L⁻ on the same set X of nodes, in which, except for the pair { ≤S, ≤H }, any two relations uniquely determine the other three, see the determinacy table. Tree (data structure)_sentence_241

Notes about notational conventions: Tree (data structure)_sentence_242

This yields six versions ≺, <, ≤, ≻, >, ≥ for a single partial order relation. Tree (data structure)_sentence_243

Except for ≺ and ≻, each version uniquely determines the others. Tree (data structure)_sentence_244

Passing from ≺ to <requires that < be transitively reducible. Tree (data structure)_sentence_245

This is always satisfied for all of <V, <S and <H but might not hold for <L⁺ or <L⁻ if X is infinite. Tree (data structure)_sentence_246

The partial orders ≤V and ≤Hare complementary: Tree (data structure)_sentence_247

Tree (data structure)_description_list_34

  • (<V) ⊎ (>V) ⊎ (<H) ⊎ (>H) = X × X ∖ idX.Tree (data structure)_item_34_110

As a consequence, the "concordant" linear order <L⁺ is a linear extension of <V. Tree (data structure)_sentence_248

Similarly, <L⁻ is a linear extension of >V. Tree (data structure)_sentence_249

Definition using horizontal order Tree (data structure)_section_25

The Kuboyama's definition of "rooted ordered trees" makes use of the horizontal order ≤H as a definitory relation. Tree (data structure)_sentence_250

(See also Suppes.) Tree (data structure)_sentence_251

Using the notation and terminology introduced so far, the definition can be expressed as follows. Tree (data structure)_sentence_252

An ordered tree is a structure (X, ≤V, ≤H) such that conditions (1–5) are satisfied: Tree (data structure)_sentence_253

Tree (data structure)_ordered_list_35

  1. (X, ≤V) is a partial order that is an unordered tree. (The vertical order.)Tree (data structure)_item_35_111
  2. (X, ≤H) is a partial order. (The horizontal order.)Tree (data structure)_item_35_112
  3. The partial orders ≤V and ≤H are complementary: (<V) ⊎ (>V) ⊎ (<H) ⊎ (>H) = X × X ∖ idX.Tree (data structure)_item_35_113
    • (That is, pairs of nodes that are incomparable in (<V) are comparable in (<H) and vice versa.)Tree (data structure)_item_35_114
  4. The partial orders ≤V and ≤H are "consistent": (<H) = (≤V) ○ (<H) ○ (≥V).Tree (data structure)_item_35_115
    • (That is, for every nodes x, y such that x <H y, all descendants of x must precede all the descendants of y.)Tree (data structure)_item_35_116
  5. Every node has only finitely many preceding siblings. (That is, for every infinite sibling set S, (S, ≤H) has the order type of the natural numbers.) (Like before, this condition can be omitted in the case of finite trees.)Tree (data structure)_item_35_117

The sibling order (≤S) is obtained by (<S) = (<H) ∩ ((≺V) ○ (≻V)), i.e. two distinct nodes are in sibling order if and only if they are in horizontal order and are siblings. Tree (data structure)_sentence_254

Determinacy table Tree (data structure)_section_26

The following table shows the determinacy of the "V-S-H-L" system. Tree (data structure)_sentence_255

Relational expressions in the table's body are equal to one of <V, <S, <H, <L⁻, or <L⁺ according to the column. Tree (data structure)_sentence_256

It follows that except for the pair { ≤S, ≤H }, an ordered tree (X, ...) is uniquely determined by any two of the five relations. Tree (data structure)_sentence_257

Tree (data structure)_table_general_1

Tree (data structure)_header_cell_1_0_0 <VTree (data structure)_header_cell_1_0_1 <STree (data structure)_header_cell_1_0_2 <HTree (data structure)_header_cell_1_0_3 <L⁻Tree (data structure)_header_cell_1_0_4 <L⁺Tree (data structure)_header_cell_1_0_5
V,STree (data structure)_header_cell_1_1_0 Tree (data structure)_cell_1_1_1 Tree (data structure)_cell_1_1_2 (≤V) ○ (<S) ○ (≥V)Tree (data structure)_cell_1_1_3 Tree (data structure)_cell_1_1_4 Tree (data structure)_cell_1_1_5
V,HTree (data structure)_header_cell_1_2_0 Tree (data structure)_cell_1_2_1 (<H) ∩ ((≺V)○(≻V))Tree (data structure)_cell_1_2_2 Tree (data structure)_cell_1_2_3 (>V) ∪ (<H)Tree (data structure)_cell_1_2_4 (<V) ∪ (<H)Tree (data structure)_cell_1_2_5
V,L⁻Tree (data structure)_header_cell_1_3_0 Tree (data structure)_cell_1_3_1 (<L⁻) ∩ ((≺V)○(≻V))Tree (data structure)_cell_1_3_2 (<L⁻) ∖ (>V)Tree (data structure)_cell_1_3_3 Tree (data structure)_cell_1_3_4 Tree (data structure)_cell_1_3_5
V,L⁺Tree (data structure)_header_cell_1_4_0 Tree (data structure)_cell_1_4_1 (<L⁺) ∩ ((≺V)○(≻V))Tree (data structure)_cell_1_4_2 (<L⁺) ∖ (<V)Tree (data structure)_cell_1_4_3 Tree (data structure)_cell_1_4_4 Tree (data structure)_cell_1_4_5
H,L⁻Tree (data structure)_header_cell_1_5_0 (>L⁻) ∖ (<H)Tree (data structure)_cell_1_5_1 Tree (data structure)_cell_1_5_2 Tree (data structure)_cell_1_5_3 Tree (data structure)_cell_1_5_4 Tree (data structure)_cell_1_5_5
H,L⁺Tree (data structure)_header_cell_1_6_0 (<L⁺) ∖ (<H)Tree (data structure)_cell_1_6_1 Tree (data structure)_cell_1_6_2 Tree (data structure)_cell_1_6_3 Tree (data structure)_cell_1_6_4 Tree (data structure)_cell_1_6_5
L⁻,L⁺Tree (data structure)_header_cell_1_7_0 (>L⁻) ∩ (<L⁺)Tree (data structure)_cell_1_7_1 Tree (data structure)_cell_1_7_2 (<L⁻) ∩ (<L⁺)Tree (data structure)_cell_1_7_3 Tree (data structure)_cell_1_7_4 Tree (data structure)_cell_1_7_5
S,L⁻Tree (data structure)_header_cell_1_8_0 x ≺V y ↔ y = infL⁻(Y) where Y is the image of {x} under (≥S)○(≻L⁻)Tree (data structure)_cell_1_8_1
S,L⁺Tree (data structure)_header_cell_1_9_0 x ≺V y ↔ y = supL⁺(Y) where Y is the image of {x} under (≤S)○(≺L⁺)Tree (data structure)_cell_1_9_1

In the last two rows, infL⁻(Y) denotes the infimum of Y in (X, ≤L⁻), and supL⁺(Y) denotes the supremum of Y in (X, ≤L⁺). Tree (data structure)_sentence_258

In both rows, (≤S) resp. (≥S) can be equivalently replaced by the sibling equivalence (≤S)○(≥S). Tree (data structure)_sentence_259

In particular, the partition into sibling sets together with either of ≤L⁻ or ≤L⁺ is also sufficient to determine the ordered tree. Tree (data structure)_sentence_260

The first prescription for ≺V can be read as: the parent of a non-root node x equals the infimum of the set of all immediate predecessors of siblings of x, where the words "infimum" and "predecessors" are meant with regard to ≤L⁻. Tree (data structure)_sentence_261

Similarly with the second prescription, just use "supremum", "successors" and ≤L⁺. Tree (data structure)_sentence_262

The relations ≤S and ≤H obviously cannot form a definitory pair. Tree (data structure)_sentence_263

For the simplest example, consider an ordered tree with exactly two nodes – then one cannot tell which of them is the root. Tree (data structure)_sentence_264

XPath axes Tree (data structure)_section_27

The table on the right shows a correspondence of introduced relations to XPath axes, which are used in structured document systems to access nodes that bear particular ordering relationships to a starting "context" node. Tree (data structure)_sentence_265

For a context node x, its axis named by the specifier in the left column is the set of nodes that equals the image of {x} under the correspondent relation. Tree (data structure)_sentence_266

As of XPath 2.0, the nodes are "returned" in document order, which is the "discordant" linear order ≤L⁻. Tree (data structure)_sentence_267

A "concordance" would be achieved, if the vertical order ≤V was defined oppositely, with the bottom-up direction outwards the root like in set theory in accordance to natural trees. Tree (data structure)_sentence_268

Traversal maps Tree (data structure)_section_28

Below is the list of partial maps that are typically used for ordered tree traversal. Tree (data structure)_sentence_269

Each map is a distinguished functional subrelation of ≤L⁻ or of its opposite. Tree (data structure)_sentence_270

Tree (data structure)_unordered_list_36

  • ≺V ... the parent-node partial map,Tree (data structure)_item_36_118
  • ≻S ... the previous-sibling partial map,Tree (data structure)_item_36_119
  • ≺S ... the next-sibling partial map,Tree (data structure)_item_36_120
  • (≺L⁻) ∖ (<H) ... the first-child partial map,Tree (data structure)_item_36_121
  • (≻L⁺) ∖ (>H) ... the last-child partial map,Tree (data structure)_item_36_122
  • ≻L⁻ ... the previous-node partial map,Tree (data structure)_item_36_123
  • ≺L⁻ ... the next-node partial map.Tree (data structure)_item_36_124

Generating structure Tree (data structure)_section_29

The traversal maps constitute a partial unary algebra (X, parent, previousSibling, ..., nextNode) that forms a basis for representing trees as linked data structures. Tree (data structure)_sentence_271

At least conceptually,there are parent links, sibling adjacency links, and first / last child links. Tree (data structure)_sentence_272

This also applies to unordered trees in general, which can be observed on the dentry data structure in the Linux VFS. Tree (data structure)_sentence_273

Similarly to the "V-S-H-L" system of partial orders, there are pairs of traversal maps that uniquely determine the whole ordered tree structure. Tree (data structure)_sentence_274

Naturally, one such generating structure is (X, V, S) which can be transcribed as (X, parent, nextSibling) – the structure of parent and next-sibling links. Tree (data structure)_sentence_275

Another important generating structure is (X, firstChild, nextSibling) known as left-child right-sibling binary tree. Tree (data structure)_sentence_276

This partial algebra establishes a one-to-one correspondence between binary trees and ordered trees. Tree (data structure)_sentence_277

Definition using binary trees Tree (data structure)_section_30

The correspondence to binary trees provides a concise definition of ordered trees as partial algebras. Tree (data structure)_sentence_278

Tree (data structure)_ordered_list_37

  1. The partial maps lc and rs are disjoint, i.e. (lc) ∩ (rs) = ∅ .Tree (data structure)_item_37_125
  2. The inverse of (lc) ∪ (rs) is a partial map p such that the partial algebra (X, p) is an unordered tree.Tree (data structure)_item_37_126

The partial order structure (X, ≤V, ≤S) is obtained as follows: Tree (data structure)_sentence_279

Tree (data structure)_description_list_38

  • (≺S) = (rs), (≻V) = (lc) ○ (≤S).Tree (data structure)_item_38_127

Encoding by sequences Tree (data structure)_section_31

Per-level ordering Tree (data structure)_section_32

As a possible expansion of the "V-S-H-L" system, another distinguished relations between nodes can be defined, based on the tree's level structure. Tree (data structure)_sentence_280

First, let us denote by ∼E the equivalence relation defined by x ∼E y if and only if x and y have the same number of ancestors. Tree (data structure)_sentence_281

This yields a partition of the set of nodes into levels L0, L1, ... (, Ln) – a coarsement of the partition into sibling sets. Tree (data structure)_sentence_282

Then define relations <E, <B⁻ and <B⁺ by Tree (data structure)_sentence_283

It can be observed that <E is a strict partial order and <B⁻ and <B⁺ are strict total orders. Tree (data structure)_sentence_284

Moreover, there is a similarity between the "V-S-L" and "V-E-B" systems: <E is component-wise linear and orthogonal to <V, <B⁻ is linear extension of <E and of >V, and <B⁺ is a linear extension of <E and of <V. Tree (data structure)_sentence_285

See also Tree (data structure)_section_33

Tree (data structure)_unordered_list_39

Other trees Tree (data structure)_section_34

Tree (data structure)_unordered_list_40


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Tree (data structure).