Data Structure Notes --> Trees
- Trees are very flexible, versatile and powerful non-liner data structure that can be used to represent data items possessing hierarchical relationship between the grand father and his children and grand children as so on.
- A tree is an ideal data structure for representing hierarchical data. A tree can be theoretically defined as a finite set of one or more data items (or nodes) such that:
1. There is a special node called the root of the tree.
2. Removing nodes (or data item) are partitioned into number of mutually exclusive (i.e., disjoined) subsets each of which is itself a tree, are called sub tree. i.e. the remaining nodes are partitioned into n>=0 disjoint sets T1, ..., Tn, where each of these sets is a tree. We call T1, ..., Tn the subtrees of the root.
- So we can define it as “ A tree T is a finite non empty set of elements. One of these element is called the root, and the remaining elements if any, are partitioned into trees, which are called the subtrees of T.” A tree is a non-linear data structure. here each element may have a single predecessor but may have two or more successors.
- Root : The topmost node of the tree is called the root of the tree. This node has no parent. Root is a specially designed node (or data items) in a tree. It is the first node in the hierarchical arrangement of the data items. ‘A’ is a root node in the Fig.
- Node: Each data item in a tree is called a node. It specifies the data information and links (branches) to other data items. A node is a key component of the tree data structure that stores the data element and may contain zero, one or more links to other successor nodes for connectivity. A tree consists of a finite set of nodes. Various nodes in the above figure are A,B,C,D etc.
- Edge or Link: a directed line from one node to the other successor node is called edge of a tree. It is also known as link, arc, or branch of a tree. A tree consists of a finite set of edges that connect nodes.
- Parent: The immediate predecessor of a node is called its parent. All the nodes except the root node have exactly one parent. In the above figure A is the parent of B, C, D. whereas B is parent of E & F.
- Child: All the immediate successors of a node are known as its child. Each node in a tree can have 0 or more child nodes. If a node has two child then one on the left is called the left child and other on the right is called right child. In the above figure B, C, D, are childs of A and E, F are childs of B.
- Sibling: Two or more nodes with same parent are called siblings. Here B, C, D are siblings in the above tree. Similarly E and F are siblings.
- Leaf : The node that does not have any child is called the leaf node also called as terminal nodes. Also the nodes with degree 0 are called as leaf nodes. A tree may have many leaf nodes. In the above tree L,M,N,O,H,I,P,Q,R,S,K all are leaf nodes.
- Level of an element : The tree is structured in Different levels. The entire tree is leveled in such a way that root is always at level 0, its children if any are at level 1, their children if any will be at level 2 and so on up to terminal nodes. Also the level of a node is an integer value that measures the distance of a node from the root. As root is at zero distance from itself so it is at level 0. if a node is at level n then its parent is at level n-1 and child at a level n+1. All the siblings are at same level but the reverse is not true.
- Degree of an element: The degree of an element is the number of children it have. The node with degree 0 is a leaf or terminal node. For example in the above tree M,N,O are leaf node because their degree is 0.
- Degree of a Tree: The degree of a tree is the maximum degree of a node in a given tree. In the above tree degree of node J is 4. All the other nodes have less or equal degree. So degree of above tree is 4.
- Height of a node: The height of a node is the length (number of edges) of the path from the node under consideration to its furthest leaf. Depth of a node: The depth of a node is the length i.e. no. of edges of the path from the root to the node of the tree. The root is at depth 0 and child of the root node is at depth 1 and so on.
- Height/Depth of a tree: Height or Depth of a tree is the maximum level of any node in a given tree. That is a number of level one can descend the tree from its root node to the terminal nodes. If level of the root is denoted by 1, then the maximum level number(-1) of tree is known as its height or depth.
- Path: a path is a resulting sequence of nodes when we traverse from a node to a node along the edges that connect them. There is always a unique path from the root to any other node in a tree. All the nodes that lie on the unique upward path from a given node to root node are ancestors of that node. And all nodes from a given node to a leaf node in given path are the descendents of that node.
- Length of a PathThe length of a path is the number of branches on the path.
- Forest: A set of trees is called a forest.