Tree ADTs

From

(Difference between revisions)
Jump to: navigation, search
m (Protected "Overview of Tree Abstract Data Types" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite)))
m (→Glossary of terms for rooted trees)
 
(16 intermediate revisions not shown)
Line 1: Line 1:
 +
<noinclude>
 +
{{CS2:BookNav|base=/|up=Contents: CS2|prev=|next=Binary Trees}}
 +
</noinclude>
 +
<br/>
 +
 +
[[Image:binary tree.svg|right|192|thumb|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.]]
A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the '''root''' together with any number of successors which are also trees ('''subtrees''' in this case), which are disjoint from each other and from the root. The roots of the subtrees are called '''children''' of the root, and there is an '''edge''' from each node to its children, and a node is said to be the '''parent''' of its children. A node that has at least one child is called an '''internal node''', and a node that has no children is called a '''leaf node'''.
A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the '''root''' together with any number of successors which are also trees ('''subtrees''' in this case), which are disjoint from each other and from the root. The roots of the subtrees are called '''children''' of the root, and there is an '''edge''' from each node to its children, and a node is said to be the '''parent''' of its children. A node that has at least one child is called an '''internal node''', and a node that has no children is called a '''leaf node'''.
 +
<br/><br/>
-
== Paths ==
+
More formally, in computer science, a tree is an acyclic connected graph where each node has a set of zero or more children nodes, and at most one parent node.
 +
<br/><br/>
-
If n<sub>1</sub>, n<sub>2</sub>, …, n<sub>n</sub> is a sequence of nodes in the tree such that ni is the parent of n<sub>i+1</sub>, then this sequence is called a path. The length of the path is the number of edges, which is one less than the number of node: in this case the length of the path is n-1. If there is a path from a node M to a node N, then N is called a '''descendent''' of M and M is called an '''ancestor''' of N.
+
==Terminology==
 +
A node is a structure which may contain a value or a condition or represent a separate data structure or a tree of its own. Each node in a tree has zero or more '''child nodes''' two child for binary tree, 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.
 +
<br/><br/>
-
== Depth/Level ==
+
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''). Thus the depth of the root is 0. 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 '''height''' of the tree is 1 more than the depth of the deepest node. All nodes at depth d are said to be at '''level''' d.
 +
<br/><br/>
-
The '''depth''' of a node M in the tree is the length of the path from the root to M. Thus the depth of the root is 0. The '''height''' of the tree is 1 more than the depth of the deepest node. All nodes at depth d are said to be at '''level''' d.
+
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.
<br/><br/>
<br/><br/>
 +
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.
 +
They are also referred to as terminal nodes.
 +
<br/><br/>
 +
 +
An '''internal node''' or '''inner node''' is any node of a tree that has child nodes and is thus not a leaf node.
 +
<br/><br/>
 +
 +
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 is a '''proper subtree''' (in analogy to the term proper subset).
 +
<br/><br/>
 +
==Glossary of terms for rooted trees==
 +
* A '''directed edge''' refers to the link from the parent to the child (the arrows in the picture of the tree).
 +
* The '''root node''' of a tree is the node with no parents.  There is at most one root node in a rooted tree.
 +
* A '''leaf node''' has no children.
 +
* The '''depth''' of a node n is the length of the path from the root to the node.  The set of all nodes at a given depth is sometimes called a '''level''' of the tree. The root node is at depth zero.
 +
* The '''height''' of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero.
 +
* '''Siblings''' are nodes that share the same parent node.
 +
* If a path exists from node p to node q, where node p is closer to the root node than q, then p is an '''ancestor''' of q and q is a '''descendant''' of p.
 +
* The '''size''' of a node is the number of descendants it has including itself.
 +
*'''In-degree''' of a node is the number of edges arriving at that node.
 +
* '''Out-degree''' of a node is the number of edges leaving that node.
 +
*Root is the only node in the tree with In-degree = 0
 +
<br/>
 +
 +
== Paths ==
 +
If n<sub>1</sub>, n<sub>2</sub>, …, n<sub>n</sub> is a sequence of nodes in the tree such that ni is the parent of n<sub>i+1</sub>, then this sequence is called a path. The length of the path is the number of edges, which is one less than the number of node: in this case the length of the path is n-1. If there is a path from a node M to a node N, then N is called a '''descendent''' of M and M is called an '''ancestor''' of N.
 +
<br/><br/>
 +
===Trees===
 +
*[[Binary Trees|Binary Trees]] <br/> 
 +
**[[Binary Search Trees]]  <br/>
 +
**[[AVL Trees]]  <br/>
 +
**[[Red-Black Trees]] <br/> 
 +
**[[Splay Trees]]  <br/>
 +
**[[Heaps]]  <br/>
 +
*[[Multi-Way Trees]] <br/>
 +
**[[B-Trees]] <br/>
 +
**[[B+Trees]] <br/>
 +
*[[General Trees]] <br/>
 +
 +
 +
----
 +
{{CS2/ChapNav}}
 +
----
 +
[[Category:CS2|{{SUBPAGENAME}}]]

Current revision as of 14:32, 21 April 2010

Begin ↑ Contents: CS2 Binary Trees →


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.

A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the root together with any number of successors which are also trees (subtrees in this case), which are disjoint from each other and from the root. The roots of the subtrees are called children of the root, and there is an edge from each node to its children, and a node is said to be the parent of its children. A node that has at least one child is called an internal node, and a node that has no children is called a leaf node.

More formally, in computer science, a tree is an acyclic connected graph where each node has a set of zero or more children nodes, and at most one parent node.

Contents

Terminology

A node is a structure which may contain a value or a condition or represent a separate data structure or a tree of its own. Each node in a tree has zero or more child nodes two child for binary tree, 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). Thus the depth of the root is 0. 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 height of the tree is 1 more than the depth of the deepest node. All nodes at depth d are said to be at level d.

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.

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. They are also referred to as terminal 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 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 is a proper subtree (in analogy to the term proper subset).

Glossary of terms for rooted trees

  • A directed edge refers to the link from the parent to the child (the arrows in the picture of the tree).
  • The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.
  • A leaf node has no children.
  • The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.
  • The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero.
  • Siblings are nodes that share the same parent node.
  • If a path exists from node p to node q, where node p is closer to the root node than q, then p is an ancestor of q and q is a descendant of p.
  • The size of a node is the number of descendants it has including itself.
  • In-degree of a node is the number of edges arriving at that node.
  • Out-degree of a node is the number of edges leaving that node.
  • Root is the only node in the tree with In-degree = 0


Paths

If n1, n2, …, nn is a sequence of nodes in the tree such that ni is the parent of ni+1, then this sequence is called a path. The length of the path is the number of edges, which is one less than the number of node: in this case the length of the path is n-1. If there is a path from a node M to a node N, then N is called a descendent of M and M is called an ancestor of N.

Trees


CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs

Retrieved from "http://archive.occcwiki.org/index.php/Tree_ADTs"
Personal tools
MediaWiki Appliance - Powered by TurnKey Linux