Tree
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. 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).
- Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp. 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. 214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253–320.
0 komentar:
Posting Komentar