**Source:** Wikipedia: Tree (Data Structure)

Tree (data structure)

From Wikipedia, the free encyclopedia

(Redirected from Tree data structure)

Jump to:navigation, search

Mergefrom.svg

It has been suggested that Leaf object be merged into this article or section. (Discuss)

Merge-arrow.svg

It has been suggested that this article or section be merged into Tree structure. (Discuss)

A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent.

In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.

Mathematically, it is not a tree, but an arborescence: an acyclic connected graph where each node has zero or more children nodes and at most one parent node. Furthermore, the children of each node have a specific order.

Contents

[hide]

* 1 Terminology

* 2 Tree representations

* 3 Trees and graphs

* 4 Relationship with trees in graph theory

* 5 Traversal methods

* 6 Common operations

* 7 Common uses

* 8 See also

o 8.1 Other trees

* 9 References

* 10 External links

[edit] Terminology

A node is a structure which may contain a value, a condition, or represent a separate data structure (which could be 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.

Nodes that do not have any children are called leaf nodes. They are also referred to as terminal nodes.

A free tree is a tree that is not rooted.

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). This is commonly needed in the manipulation of the various self balancing trees, AVL Trees in particular. Conventionally, the value -1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.

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.

An internal node or inner node is any node of a tree that has child nodes and is thus not a leaf node.

A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. (This is different from the formal definition of subtree used in graph theory.[1]) 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).

[edit] 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).

[edit] Trees and graphs

The tree data structure can be generalized to represent directed graphs by allowing cycles to form in the parent-child relationship. Instead of parents and children, we speak of the sources and targets of the edges of the directed graph. However this is not a common implementation strategy; see graph (data structure).

[edit] Relationship with trees in graph theory

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.

[edit] Traversal methods

Main article: Tree traversal

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.

[edit] Common operations

* Enumerating all the items

* Enumerating a section of a tree

* 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

[edit] Common uses

* Manipulate hierarchical data

* Make information easy to search (see tree traversal)

* Manipulate sorted lists of data

* As a workflow for compositing digital images for visual effects

* Router algorithms

[edit] See also

* Tree (graph theory)

* Tree (set theory)

* Tree structure

* Hierarchy (mathematics)

[edit] Other trees

* DSW algorithm

* Enfilade

* Left child-right sibling binary tree

[edit] References

1. ^ E.W. Weisstein. ""Subtree."". http://mathworld.wolfram.com/Subtree.html.

* Eric W. Weisstein "Subtree." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/Subtree.html

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

[edit] External links

Search Wikimedia Commons Wikimedia Commons has media related to: Tree structures

* Description from the Dictionary of Algorithms and Data Structures

* STL-like C++ tree class

* Description of tree data structures from ideainfo.8m.com

* flash actionscript 3 opensource implementation of tree and binary tree — opensource library

[show]

v • d • e

Trees in computer science

Binary trees

Binary search tree (BST) · Van Emde Boas tree · Cartesian tree · Top Tree · T-tree

Self-balancing binary search trees

Red-black tree · AVL tree · AA tree · Splay tree · Scapegoat tree · Treap

B-trees

B+ tree · B*-tree · UB-tree · 2-3 tree · 2-3-4 tree · (a,b)-tree · Dancing tree · Htree · Bx-tree

Tries

Suffix tree · Radix tree · Ternary search tree

Binary space partitioning (BSP) trees

Quadtree · Octree · kd-tree (implicit) · VP-tree

Non-binary trees

Exponential tree · Fusion tree · Interval tree · PQ tree · Range tree · SPQR tree

Spatial data partitioning trees

R-tree · R+-tree · R*-tree · X-tree · M-tree · Segment tree

Other trees

Heap · Hash tree · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance

[show]

v • d • e

Data structures

Types

Collection · Container

Arrays

Associative array · Multimap · Set · Multiset · Hash table

Lists

Double-ended queue · Linked list · Queue · Stack · Circular Queue/Buffer

Trees

B-tree · Binary search tree · Heap

Graphs

Directed graph · Directed acyclic graph · Binary decision diagram

List of data structures

Retrieved from "http://en.wikipedia.org/wiki/Tree_(data_structure)"

Categories: Trees (structure) | Knowledge representation

Hidden categories: Articles to be merged from April 2009 | All articles to be merged | Articles to be merged from October 2009

Personal tools

* New features

* Log in / create account

Namespaces

* Article

* Discussion

Variants

Views

* Read

* Edit

* View history

Actions

Search

Search

Navigation

* Main page

* Contents

* Featured content

* Current events

* Random article

Interaction

* About Wikipedia

* Community portal

* Recent changes

* Contact Wikipedia

* Donate to Wikipedia

* Help

Toolbox

* What links here

* Related changes

* Upload file

* Special pages

* Permanent link

* Cite this page

Print/export

* Create a book

* Download as PDF

* Printable version

Languages

* Català

* Česky

* Dansk

* Español

* فارسی

* Français

* Bahasa Indonesia

* Italiano

* Lietuvių

* Македонски

* Nederlands

* 日本語

* Norsk (bokmål)

* Polski

* Português

* Русский

* Slovenščina

* Српски / Srpski

* ไทย

* Українська

* Tiếng Việt

* 中文

* This page was last modified on 4 June 2010 at 16:20.

* Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. See Terms of Use for details.

Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.

* Contact us