/
0 Comments
Tree Data Structure
Definition
A tree is a (possibly non-linear) data structure made up of
nodes or vertices and edges without having any cycle. The tree with no nodes is
called the null orempty tree.
A tree that is not empty consists of a root node and potentially many levels of
additional nodes that form a hierarchy.
In computer
science, a tree is a widely used abstract data type (ADT) or data
structure implementing
this ADT that simulates a hierarchical tree
structure, with a root value and subtrees of children, represented
as a set of linked nodes.
A
tree data structure can be defined recursively (locally) as a collection of nodes (starting
at a root node), where each node is a data structure consisting of a value,
together with a list of references to nodes (the "children"), with
the constraints that no reference is duplicated, and none points to the root.
Alternatively,
a tree can be defined abstractly as a whole (globally) as an ordered tree,
with a value assigned to each node. Both these perspectives are useful: while a
tree can be analyzed mathematically as a whole, when actually represented as a
data structure it is usually represented and worked with separately by node
(rather than as a list of nodes and an adjacency
list of edges between
nodes, as one may represent a digraph,
for instance). For example, looking at a tree as a whole, one can talk about
"the parent node" of a given node, but in general as a data structure
a given node only contains the list of its children, but does not contain a
reference to its parent (if any).
Terminologies Used in Trees
·
Root – The
top node in a tree.
·
Parent – The
converse notion of child.
·
Siblings –
Nodes with the same parent.
·
Descendant – a
node reachable by repeated proceeding from parent to child.
·
Ancestor – a
node reachable by repeated proceeding from child to parent.
·
Leaf – a
node with no children.
·
Internal node – a
node with at least one child.
·
External node – a
node with no children.
·
Degree –
number of sub trees of a node.
·
Edge –
connection between one node to another.
·
Path – a
sequence of nodes and edges connecting a node with a descendant.
·
Level – The
level of a node is defined by 1 + the number of connections between the node
and the root.
·
Height of tree –The
height of a tree is the number of edges on the longest downward path between
the root and a leaf.
·
Height of node –The
height of a node is the number of edges on the longest downward path between
that node and a leaf.
·
Depth –The
depth of a node is the number of edges from the node to the tree's root node.
·
Forest – A
forest is a set of n ≥ 0 disjoint trees.
A node is a structure which may
contain a value or condition, or represent a separate data structure (which
could be a tree of its own). Each node in a tree has zero or morechild nodes,
which are below it in the tree (by convention, trees are drawn growing
downwards). A node that has a child is called the child's parent node (or ancestor
node, orsuperior). A node has at most one parent.
An internal
node (also known as an inner node, inode for
short, or branch node) is any node of a tree that has child nodes.
Similarly, an external node (also known as anouter node, leaf
node, or terminal node) is any node that does not have child
nodes.
The topmost
node in a tree is called the root node. Depending on definition, a
tree may be required to have a root node (in which case all trees are
non-empty), or may be allowed to be empty, in which case it does not
necessarily have a root node. Being the topmost node, the root node will not
have a parent. It is the node at which algorithms on the tree begin, since as a
data structure, one can only pass from parents to children. Note that some
algorithms (such as post-order depth-first search) begin at the root, but first
visit leaf nodes (access the value of leaf nodes), only visit the root last
(i.e., they first access the children of the root, but only access the value of
the root last). 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, the
root node is conventionally 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.
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. The root node has depth zero, leaf nodes have height zero, and a
tree with only a single node (hence both a root and leaf) has depth and height
zero. Conventionally, an empty tree (tree with no nodes, if such are allowed)
has depth and height −1.
A subtree of
a tree T is a tree consisting of a node in T and
all of its descendants in T.[c][1] Nodes thus correspond to
subtrees (each node corresponds to the subtree of itself and all its
descendants) – the subtree corresponding to the root node is the entire tree,
and each node is the root node of the subtree it determines; the subtree
corresponding to any other node is called a proper subtree (by
analogy to a proper subset).
Binary
Trees
The simplest form of tree is a binary tree. A binary tree consists of
- a node (called
the root node) and
- left and right sub-trees.
Both the sub-trees are themselves binary trees.
You now have
a recursively defined data structure. (It is also possible to
define a list recursively: can you see how?)
A binary tree
The nodes at
the lowest levels of the tree (the ones with no sub-trees) are called leaves.
In an ordered
binary tree,
- the keys of all the nodes in
the left sub-tree are less than that of the root,
- the keys of all the nodes in
the right sub-tree are greater than that of the root,
- the left and right sub-trees
are themselves ordered binary trees.
For example,
if you construct a binary tree to store numeric values such that each left
sub-tree contains larger values and each right sub-tree contains smaller values
then it is easy to search the tree for any particular value. The algorithm is
simply a tree search equivalent of a binary search:
start at the root
REPEAT until you reach a terminal node
IF value at the node = search value
THEN found
IF value at node < search value
THEN move to left descendant
ELSE move to right descendant
END REPEAT
REPEAT until you reach a terminal node
IF value at the node = search value
THEN found
IF value at node < search value
THEN move to left descendant
ELSE move to right descendant
END REPEAT
Conclusion
A tree is a data structure made up of
nodes or vertices and edges without having any cycle. And example for The simplest form of tree is a binary tree.
References
http://www.i-programmer.info/babbages-bag/477-trees.html
