- Tree Concept:
A tree is hierarchical collection of nodes. One of the nodes, known as the root, is at the top of the hierarchy. Each node can have at most one link coming into it. The node where the link originates is called the parent node. The root node has no parent. The links leaving a node (any number of links are allowed) point to child nodes. Trees are recursive structures. Each child node is itself the root of a sub tree. At the bottom of the tree are leaf nodes, which have no children.
Trees represent a special case of more general structures known as graphs. In a graph, there is no restrictions on the number of links that can enter or leave a node, and cycles may be present in the graph. The figure shows a tree and a non-tree
In a tree data structure, there is no distinction between the various children of a node i.e., none is the "first child" or "last child". A tree in which such distinctions are made is called an ordered tree, and data structures built on them are called ordered tree data structures. Ordered trees are by far the commonest form of tree data structure.
Why Use Trees?
You may want to know, why to use a tree? Usually because it combines the advantages of two other structures: an ordered array and a linked list. You can search a tree quickly, as you can an ordered array, and you can also insert and delete items quickly, as you can with a linked list.
Let’s see HOW?
- A fast searching but slow insertion and Deletion in an Ordered Array
Imagine an array in which all the elements are arranged in order; that is, an ordered array. it’s quick to search such an array for a particular value, using a binary search. You check in the center of the array. If the object you’re looking for is greater than what you find there, you narrow your search to the top half of the array; if it’s less, you narrow your search to the bottom half. It’s also quick to iterate through an ordered array, visiting each object in sorted order.
On the other hand, if you want to insert a new object into an ordered array, you first must find where the object will go, and then move all the objects with greater keys up one space in the array to make room for it. These multiple moves are time-consuming because they require, on average, moving half the items (N/2 moves). Deletion involves the same multimove operation, and is thus equally slow.
If you’re going to be doing a lot of insertions and deletions, an ordered array is a bad choice
- Slow searching, but fast insertion and deletion in Linked List.
We know that insertions and deletions are quick to perform on a linked list. They are accomplished simply by changing a few pointers. Unfortunately, however, finding a specified element in a linked list is not so easy. You must start at the beginning of the list and visit each element until you find the one you’re looking for. Thus you will need to visit an average of N/2 objects, comparing each one’s position with the desired value.
You might think you could speed things up by using an ordered linked list, in which the elements were arranged in order, but this doesn’t help. You still must start at the beginning and visit the elements in order because there’s no way to access a given element without following the chain of pointers to it. (Of course, in an ordered list it’s much quicker to visit the nodes in order than it is in a non-ordered list, but that doesn’t help to find an arbitrary object.)
It would be nice if there were a data structure with the quick insertion and deletion of a linked list, and also the quick searching of an ordered array.
Trees provide both these characteristics, and are also one of the most interesting data structures.
###########################################################################
- Tree Terminologies
- Tree: Tree is a digraph, which involves for the description of hierarchy. A directed tree is an acyclic digraph which has one node called root with in degree 0, while other nodes have in degree 1. Every directed tree must have at least one node. An isolated node is also called as directed tree. The node without degree as 0 is called as leaf. The length of the path from root to particular node level of the node. If the ordering of the node at each level is prescribed then the tree is called as ordered tree.
- Node: In trees nodes often represent data items in other words, the typical items we store in any kind of data structure. We’ve seen such data items stored in arrays and linked lists; now we’ll see them stored in the nodes of trees.
- Edges: The edges (lines) between the nodes represent the way the nodes are related. Roughly speaking, the lines represent convenience.
- Path: It is a number of successive edges from source to destination. Think of someone walking from node to node along the edges that connect them. The resulting sequence of nodes is called a path.
- Root: The node at the top of the tree is called the root. There is only one root in a tree.
- Parent: It is immediate predecessor of a node is its parent. Any node (except the root) has exactly one edge running upward to another node. The node above it is called the parent of the node.
- Child: All
immediate predecessor of a node are called its children. Any node can have one
or more lines running downward to other nodes. These nodes below a given node
are called its children.
- Siblings: Nodes with same parent are called
siblings.
- Leaf Node: A
node that has no children is called a leaf node or simply a leaf. There can be
only one root in a tree, but there can be many leaves. A node with zero degree
is called leaf node.
- Non-Leaf Node: Any node with nonzero degree is called as non leaf node. Or any node with at least one sub-tree is a non-leaf node.
Parents : A, B, C, G
Children : B, F, G, C, H, I, J, D, E
Siblings : { B, F, G }, { D, E }, { H, I, J }
Leaves : F, D, E, H, I, J
- Ancestor
and Descendant: If
there is a path from node A to node B, then A is called an ancestor of B and B
is called a descendant of A.
- Degree of Node: The degree of a node is the number of children of a node. Or Degree of node is the count of number of sub-trees originated from that node.
- Degree of Tree: The
degree of tree is the maximum degree of any node in the tree. The having
maximum degree is representing the degree of tree.
- Sub-tree: Any
node of a tree, with all of its descendants is a sub-tree. Any
node can be considered to be the root of a sub-tree, which consists of its
children, and its children’s children, and so on. If you think in terms of
families, a node’s sub-tree contains all its descendants.
- Visiting: A
node is visited when program control arrives at the node, usually for the
purpose of carrying out some operation on the node, such as checking the value
of one of its data members, or displaying it. Merely passing over a node on the
path from one node to another is not considered to be visiting the node.
- Traversing: To
traverse a tree means to visit all the nodes in some specified order. For
example, you might visit all the nodes in order of ascending data value.
- Levels: The
level of a particular node refers to how many generations the node is from the
root. If
we assume the root is Level 0, its children will be Level 1, its grandchildren will
be Level 2, and so on.
- Height of Tree: The
height of tree is the maximum level of any node in the tree. The node having
maximum level is going to represent the height of the tree. The height of a
node in a tree is the length of a longest path from the node to a leaf. The
term depth is also used to denote height of the tree.
- Forest of Tree: The
set of trees is called the forest of tree. If remove root of the tree then
resultant set of sub-trees represents forest of tree.
- Unary Tree (Skewed tree): A tree in which each node has at most of one child, then such tree is called as Unary tree.
- N-ary Tree :A tree in which each node has at most of ‘n’ children, then such tree is called as N-ary tree. Where n is finite number.
0 Comments:
Post a Comment