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):
  • an Array Data Structure.
• See: Recursive DB Structure, Tree Adjoining Grammar, string, Tree Distance Function, Dendogram, Ordered Tree, Trie.

---

---

References

• http://en.wikibooks.org/wiki/Data_Structures/Trees

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).

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.

---