Tree (data structure)

From Free net encyclopedia

Image:Binary tree.svg In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. It is a special case of a graph. Each node has zero or more child nodes, which are below it in the tree (in computer science, unlike in nature, trees grow down, not up). A node that has a child is called the child's parent node. A child has at most one parent; a node without a parent is called the root node (or root). Nodes with no children are called leaf nodes.

In graph theory, a tree is a connected acyclic graph. A rooted tree is such a graph with a vertex singled out as the root. In this case, any two vertices connected by an edge inherit a parent-child relationship. An acyclic graph with multiple connected components or a set of rooted trees is sometimes called a forest.

There are two basic types of tree. In an unordered tree, there is no distinction between the various children of a node — none is the "first child" or "last child". A tree in which such distinctions are made is called an ordered tree, and data structures built on them are called ordered tree data structures. Ordered trees are by far the most common form of tree data structure.

Binary search trees are one kind of ordered tree, and there is a one-to-one mapping between binary trees and general ordered trees.

There are many different ways to represent trees; common representations represent the nodes as records allocated on the heap 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).

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 where the operation happens to a node before it happens to its children is called a pre-order walk; a walk where the children are operated upon before the parent is called a post-order walk. See tree traversal for a discussion of pre-order, in-order and post-order traversal.

Common operations on trees are:

Enumerating all the items;
Searching for an item;
Adding a new item at a certain position on the tree;
Deleting an item;
Removing a whole section of a tree (called pruning);
Adding a whole section to a tree (called grafting);
Finding the root for any node.

Common uses for trees are to:

Manipulate hierarchical data;
Make information easy to search (see also: tree search algorithm);
Manipulate sorted lists of data.

[edit]

References

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 0262032937. Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.253–320.