 A simple example unordered tree In computer science, a tree is a widely-used data structure that emulates a tree structure with a set of linked nodes. Image File history File links Binary_tree. ...
Image File history File links Binary_tree. ...
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
A binary tree, a simple type of branching linked data structure. ...
A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ...
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). In a hierarchical tree structure of any kind, a superior is higher in the hierarchy and thus closer to the apex than the subordinate ones. ...
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. Example of a complete binary max heap In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). ...
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. 9, 14, 19, 67 and 76 are leaf nodes. ...
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. A node is a basic unit used to build data structures, such as linked lists and tree data structures. ...
A child node or descendant node is a node in a tree data structure that is linked to by a parent node. ...
9, 14, 19, 67 and 76 are leaf nodes. ...
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). A is a subset of B If X and Y are sets and every element of X is also an element of Y, then we say or write: X is a subset of (or is included in) Y; X ⊆ Y; Y is a superset of (or includes) X; Y...
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. Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...
A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13. ...
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). It has been suggested that this article or section be merged with Memory allocation. ...
Example of a complete binary max heap In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). ...
For the microarray in genetics, see SNP array. ...
Example of a complete binary max 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. A drawing of a graph. ...
A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
Acyclic can mean any of the following: In chemistry, an acyclic compound is a hydrocarbon compound having an open chain. ...
This article just presents the basic definitions. ...
In mathematics and computer science, graph theory studies the properties of graphs. ...
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. In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. ...
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
Pruning is a term in mathematics and informatics which describes a method of enumeration, which allows to cut parts of a decision tree. ...
Common uses A hierarchy (in Greek hieros = sacred, arkho = rule) is a system of ranking and organizing things. ...
In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. ...
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. ...
In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...
See also Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. ...
Example of a complete binary max heap In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). ...
A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
In set theory, a tree is a partially ordered set (poset) (T, <) such that for each t ε T, the set {s ε T : s < t} is well-ordered by the relation <. For each t ε T, the order type of {s ε T : s < t} is called the idxheight, or height of t...
A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ...
A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ...
An exponential tree is almost identical to a [binary search tree], with the exception that the dimension of the tree is not the same at all levels. ...
Popular tree data structures
Self balancing binary search trees Self-balancing binary search trees: In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ...
An Arne Andersson tree (AA tree) in computer science is a red-black tree with one additional rule. ...
An example of an unbalanced non-AVL tree In computer science, an AVL tree is a self-balancing binary search tree, and the first such data structure to be invented. ...
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. ...
A splay tree is a self-balancing binary search tree with the additional unusual property that recently accessed elements are quick to access again. ...
In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Igal Galperin and Ronald L. Rivest. ...
Other trees B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ...
A kind of B-tree that can contain only 2-nodes (a node with 1 element and 2 children) and 3-nodes (a node with 2 elements and 3 children). ...
A simple B+ tree example linking the keys 1-7 to data values d1-d7. ...
A B*-tree is a tree data structure, a variety of B-tree that is efficient for searching at the cost of a more expensive insertion. ...
The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. ...
The DSW algorithm, or in full Day/Stout/Warren algorithm, is a method for efficiently balancing binary search trees — that is, decreasing their height to O(log n) nodes, where n is the total number of nodes. ...
In computer science, a dancing tree is a tree data structure that is used by Namesys Reiser4 file system. ...
A fusion tree is a tree data structure that implements an associative array with integer keys up to a fixed size; by exploiting the constant-time machine word multiplication operation available on many real processors, it is able to achieve all operations in time (see Big O notation), which is...
A 3-dimensional kd-tree. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
The Quadtree is a tree data structure in which each internal node has up to four children. ...
This article is about an R-tree data structure. ...
A radix tree, Patricia trie/tree, or crit bit tree is a specialized set data structure based on the trie that is used to store a set of strings. ...
Invented in 1990 by William Pugh, a skip list is a probabilistic data structure, based on parallel linked lists, with efficiency comparable to a binary search tree (order O(log n) average time for most operations). ...
In computer science a T-tree is a type of tree data structure that is used by main-memory databases, such as, supposedly, TimesTen. ...
a T-pyramid is a tree in which every internal node has (exactly) 4 children. ...
The Top Tree is a binary tree based Data structure for unrooted dynamic trees which is used mainly for carrying out various path related operations, it allows simple Divide and conquer algorithms. ...
A van Emde Boas tree (or van Emde Boas priority queue), also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. ...
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.
Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ...
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ...
Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ...
Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ...
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ...
Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...
External links |
Feeds |
Contact