TREE DATA STRUCTURE

A simple example binary tree

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 (by convention in computer science, trees grow down - not up as they do in nature). A node that has a child is called the child's parent node. A child has at most one parent; The topmost node in a tree is called the root node. Being the topmost node, the root node will not have parents. Nodes at the bottom most level of the tree are called leaf nodes. Since they are at the bottom most level, they will not have any children.

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 trees. In an unordered tree, a tree is a tree in a purely structural sense - that is to say, given a node, there is no order for the children of that node. A tree on which an order is imposed -- for example, by assigning different natural numbers to each child of each node -- 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 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. 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.

See also

• Binary space partitioning
• heap
• tree (graph theory)
• tree search algorithm
• tree (set theory)
• tree structure
• exponential tree

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

External links

• Description from the Dictionary of Algorithms and Data Structures
• STL-like C++ tree class
• List of data structures from LEDA