Table of Contents
hide
Introduction of Tree
- Tree is also known as General Tree.
Terminology
Root:
- Nodes that have no parent is called Root Node.
- They are at the top position in the tree.
Parent Node :
- Nodes that are represented at the tail of an arrow is called Parent Node.
Child Node :
- Nodes that are represented at the head of an arrow is called Child Node.
Internal Node :
- A Node with at least one children in a tree is called Internal nodes.
- All the nodes except leaf nodes in a tree are known as internal nodes.
External/Leaf Node :
- A Node with no children in a tree is called External or leaf nodes.
Siblings :
- Nodes that are derived from same parent are collectively known as Sibling node or child.
Ancestors:
- The node itself, its parent, its parent of parent etc. are considered as ancestors in a tree.
Descendent:
- The node itself, its child, its child of child etc. are considered as descendent in a tree.
Subtree:
Path:
- The set of edges from a root to a particular node in sequence in a tree is called path of that node.
Path Length:
- The total no. of edges used in a path is called the length of the path.
Level of tree:
- The longest path length from the root.
- The root is considered as level 0.
Level of node:
- The path length from the root to that node is called Level of node in the tree.
Depth of tree:
- The depth of a tree is equal to the length of the longest leaf node.
Depth of a node:
- The length of the unique path from the root to that node is the depth of a node.
- Number of ancestors of that node is called depth of a node.
Height of tree:
- The longest path length from root to a leaf node is called Height of tree.
- The maximum depth of any node in a tree is called height of the tree.
- All leaves are considered as at height 0.
- The height of a tree is equal to the height of the root.
Degree of node:
- The maximum number of possible children/child nodes of individual node in the tree is called the degree of that node.
Degree of tree:
- The maximum number of possible children/child nodes of a node in the tree is called the degree of tree.
Definition of Tree
- The tree is a non-linear, non-contiguous, acyclic, and hierarchical data structure in which a huge amount of data is stored in the form of root nodes, parent nodes, and child nodes.
- A tree (upside down) is an abstract model of a hierarchical structure.
Properties of Tree
- Usually a tree consists of single or multiple nodes with a parent-child relation but it may be empty.
- Each element/node of the tree (except Root – the single top & a special element/node that may have zero or more nodes/subtrees and also without any parent) has a parent and zero or more children elements.
- A tree may be empty or having no nodes i.e. an empty tree is also a tree.
- Every node in a tree/general tree can have any number of sub-trees and there is no maximum limit nodes.
- The number of nodes may be different for each node in the tree.
- Every edge of the tree is directly or indirectly originated from the root.
- Every child in a tree has only one parent.
- A parent may have no or single or any number of children.
Types of Tree
There are following types of tree –
- Binary Tree
- Binary Search Tree(BST)
- AVL Tree
- Heap
- B and B+ Tree
- Red-Black Tree
- Splay Tree
- AA Tree
- 2-3 Tree
- Huffman Tree
Use/Application of Tree
- General tree structure is used to store hierarchical data/information such as in folder/directory structures of a hard disk drive.
- In XML parser that uses tree data structure.
- The decision tree concept are used in machine learning algorithm.
- Tree data structure concept is used in DNS structure.
- Normally a database uses tree data structure for indexing.
- The internal architecture of social networking sites use the concept of tree data structure.
0 Comments