Tree (data structure): Difference between revisions
No edit summary |
|||
| Line 37: | Line 37: | ||
## Visit the root of the first tree. |
## Visit the root of the first tree. |
||
==Tree representations== |
'''==Tree representations== |
||
There are many different ways to represent trees; common representations represent the nodes as records allocated on the [[heap (programming)|heap]] (not to be confused with the [[heap (data structure)|heap data structure]]) 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]]). |
There are many different ways to represent trees; common representations represent the nodes as records allocated on the [[heap (programming)|heap]] (not to be confused with the [[heap (data structure)|heap data structure]]) 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]]). |
||
===Trees as graphs=== |
===Trees as graphs=== |
||
In [[graph theory]], a [[tree (graph theory)|tree]] is a connected [[acyclic]] [[Graph (data structure)|graph]]. A rooted tree is such a graph with a [[vertex (graph theory)|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'''. |
In [[graph theory]], a [[tree (graph theory)|tree]] is a connected [[acyclic]] [[Graph (data structure)|graph]]. A rooted tree is such a graph with a [[vertex (graph theory)|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'''.''' |
||
==Traversal methods== |
==Traversal methods== |
||
Revision as of 09:20, 30 October 2007
In computer science, a tree is a widely-used data structure that emulates a tree structure with a set of linked nodes.
Nodes
A node may contain a value or a condition or represents a separate data structure or a tree of its own. Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees grow down, not up as they do in nature). A node that has a child is called the child's parent node (or ancestor node, or superior). A node has at most one parent. The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).
Root nodes
The topmost node in a tree is called the root node. Being the topmost node, the root node will not have parents. It is the node at which operations on the tree commonly begin (although some algorithms begin with the leaf nodes and work up ending at the root). All other nodes can be reached from it by following edges or links. (In the formal definition, each such path is also unique). In diagrams, it is typically drawn at the top. In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that node.
Leaf nodes
Nodes at the bottommost level of the tree are called leaf nodes. Since they are at the bottommost level, they do not have any children.
Internal nodes
An internal node or inner node is any node of a tree that has child nodes and is thus not a leaf node.
Subtrees
A subtree is a portion of a tree data structure that can be viewed as a complete tree in itself. Any node in a tree T, together with all the nodes below it, comprise a subtree of T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree (in analogy to the term proper subset).
Tree ordering
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 edge leading to a node's children — is called an edge-labeled tree or an ordered tree with data structures built upon them being 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.
Forest
A Forest is an ordered set of ordered trees. Inorder, preorder and post order traversals are defined recursively for forests.
- Inorder
- Traverse inorder the forest formed by the subtrees of the first tree in the forest, if any.
- Visit the root of the first tree.
- Traverse inorder the forest formed by the remaining trees in the forest, if any.
- Preorder
- Visit the root of the first tree.
- Traverse preorder the forest formed by the subtrees of the first tree in the forest, if any.
- Traverse preorder the forest formed by the remaining trees in the forest, if any.
- Postorder
- Traverse postorder the forest formed by the subtrees of the first tree in the forest, if any.
- Traverse postorder the forest formed by the remaining trees in the forest, if any.
- Visit the root of the first tree.
==Tree representations== There are many different ways to represent trees; common representations represent the nodes as records allocated on the heap (not to be confused with the heap data structure) 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).
Trees as graphs
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.
Traversal methods
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.
Common operations
- 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
- Manipulate hierarchical data
- Make information easy to search (see tree traversal)
- Manipulate sorted lists of data
See also
- Binary space partitioning
- heap
- Tree (graph theory)
- Tree (set theory)
- Tree structure
- Trie
- Exponential tree
Popular tree data structures
Self balancing binary search trees
Self-balancing binary search trees:
Other trees
- B-tree (2-3 tree, B+ tree, B*-tree, UB-tree)
- DSW algorithm
- Dancing tree
- Fusion tree
- kd-tree
- Octree
- Quadtree
- R-tree
- Radix tree
- Skip list
- T-tree
- T-pyramid
- Top Trees
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.