iPedia Free Information Center

Information about Internal Node

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.
  1. Inorder
  2. Traverse inorder the forest formed by the subtrees of the first tree in the forest, if any.
  3. Visit the root of the first tree.
  4. Traverse inorder the forest formed by the remaining trees in the forest, if any.
  5. Preorder
  6. Visit the root of the first tree.
  7. Traverse preorder the forest formed by the subtrees of the first tree in the forest, if any.
  8. Traverse preorder the forest formed by the remaining trees in the forest, if any.
  9. Postorder
  10. Traverse postorder the forest formed by the subtrees of the first tree in the forest, if any.
  11. Traverse postorder the forest formed by the remaining trees in the forest, if any.
  12. 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

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.

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

See also

Popular tree data structures

Self balancing binary search trees

Self-balancing binary search trees:

Other trees

References

External links

Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type.
..... Click the link for more information.
tree structure is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the graph looks a bit like a tree, even though the tree is generally shown upside down compared with a real tree; that is to say with the root
..... Click the link for more information.
In a hierarchy or tree structure of any kind, a superior is an individual or position at a higher level in the hierarchy than another (a "subordinate"), and thus closer to the apex.
..... Click the link for more information.
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).
..... Click the link for more information.
In computer science, a leaf node is a node of a tree data structure that has zero child nodes. Often, leaf nodes are the nodes farthest from the root node. In the graph theory tree, a leaf node is a vertex of degree 1 other than the root (except when the tree has only one vertex;
..... Click the link for more information.
A node is an abstract basic unit used to build linked data structures, such as linked lists and trees, and computer-based representation of graphs. Nodes contain data and/or links to other nodes. Links between nodes are often implemented by pointers or references.
..... Click the link for more information.
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.
..... Click the link for more information.
In computer science, a leaf node is a node of a tree data structure that has zero child nodes. Often, leaf nodes are the nodes farthest from the root node. In the graph theory tree, a leaf node is a vertex of degree 1 other than the root (except when the tree has only one vertex;
..... Click the link for more information.
subset of a set B if A is "contained" inside B. Notice that A and B may coincide. The relationship of one set being a subset of another is called inclusion or containment.
..... Click the link for more information.
In mathematics, a natural number can mean either an element of the set (i.e the positive integers or the counting numbers) or an element of the set (i.e. the non-negative integers).
..... Click the link for more information.
binary search tree (BST) is a binary tree data structure which has the following properties:
  • Each node has a value.
  • A total order is defined on these values.
  • The left subtree of a node contains only values less than the node's value.

..... Click the link for more information.
In computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. It is a way of distributing ownership of limited memory resources among many pieces of data and code.
..... Click the link for more information.
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).
..... Click the link for more information.
array is a data structure consisting of a group of elements that are accessed by indexing. In most programming languages each element has the same data type and the array occupies a contiguous area of storage. Most programming languages have a built-in array data type.
..... Click the link for more information.
Binary heaps are a particularly simple kind of heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
  • The shape property

..... Click the link for more information.
graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges
..... Click the link for more information.
In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. Alternatively, any connected graph with no cycles is a tree. A forest is a disjoint union of trees.
..... Click the link for more information.
Acyclic can refer to:
  • in chemistry, a compound which is not cyclic, e.g. alkanes and acyclic aliphatic compounds
  • in mathematics:
  • a directed acyclic graph

..... Click the link for more information.
graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.
..... Click the link for more information.
vertex (plural vertices) or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered
..... Click the link for more information.
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.
..... Click the link for more information.
Pruning is a term in mathematics and informatics which describes a method of enumeration, which allows to cut parts of a decision tree. Pruned parts of the tree are no longer considered because the algorithm knows based on already collected data (e.g.
..... Click the link for more information.
hierarchy (in Greek: Ἱεραρχία, derived from ἱερός — hieros, 'sacred', and
..... Click the link for more information.
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.
..... Click the link for more information.
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.
..... Click the link for more information.
In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order.
..... Click the link for more information.
Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.
..... Click the link for more information.
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).
..... Click the link for more information.
In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. Alternatively, any connected graph with no cycles is a tree. A forest is a disjoint union of trees.
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus


page counter