# Hierarchical Data Structure

A Hierarchical Data Structure is a data structure that can represent a rooted acyclic graph (with tree nodes and tree edges).

**AKA:**Tree-based Data Structure.**Context:**- It can be represented by a Tree ADT.
- It can be visualized by a Visualized Tree Structure.
- It can support a Tree Data Structure Operation, such as a tree traversal operation.
- It can range from being a Directed Tree Data Structure (associated with a DAG) to being an Undirected Tree Data Structure.
- It can be populated with a Tree Dataset.
- It can be a Subtree (a Leaf is a Node in a Directed Tree with no children).
- It can be a Rooted Tree or an Unrooted Tree.
- It can range from being an Ordered Tree Structure to being an Unordered Tree Structure (in which the child nodes of every node are ordered in according to some relation).
- It can range from being an Unlabeled Tree Structure to being a Labeled Tree Structure (a tree where each node v contains a label label(v) in A).
- It can range from being an Unordered Tree Structure to being a Partial Order Tree Structure.
- …

**Example(s):**- a Tree-based Index, such as a B-Tree Data Structure http://en.wikipedia.org/wiki/B-tree
- a Decision Tree Data Structure.
- a Concept Hierarchy Structure, such as a Taxonomy Structure.
- a Python-based Tree Data Structure, such as
`def tree(): return defaultdict(tree)`

- a Scala-based Tree Data Structure, such as
`object BST { def empty[T](implicit c:(T,T) ⇒ Int) : BST[T] = new EmptyBST(c) }`

- a Binary Search Tree Structure.
- a Chart-of-Accounts Segment Tree Structure.
- a Trie Data Structure.
- …

**Counter-Example(s):****See:**Recursive DB Structure, Tree Adjoining Grammar, string, Tree Distance Function, Dendogram, Ordered Tree, Trie.

## References

### 2014

- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/tree_(data_structure) Retrieved:2014-7-29.
- In computer science, a
**tree**is a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes.A tree data structure can be defined recursively (locally) 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.

Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. 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 list of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). 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).

- In computer science, a

### 2012

- http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Trees_and_graphs
- 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. 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*). Different implementation strategies exist, for example adjacency lists.In graph theory, a tree is a connected acyclic graph; unless stated otherwise, trees and graphs are undirected. There is no one-to-one correspondence between such trees and trees as data structure. 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. The result corresponds to a tree data structure. Picking a different root or different ordering produces a different one.

- 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. Edges are still abstractly considered as pairs of nodes, however, the terms