Define tree
A tree is a non-linear hierarchical data structure that consists of nodes connected by edges. Each node of the tree stores a value and a list of references to other nodes. The tree exhibits the following components like- a root node, a left child and a right child. Generally, A node or the root can exhibit a maximum of two children or subtree.
Basic Terminology
The basic terminology of the tree are :
Node :- node is an entity that contains data or value and pointers to its child nodes.
Edge:-It is the link between any two nodes.
Root:- It is the topmost node of a tree.
Height of a Node:-The height of a node is the number of edges from the node to the deepest leaf.
Depth of a Node:- The depth of a node is the number of edges from the root to the node.
Height of a Tree:-The height of a Tree is the height of the root node or the depth of the deepest node.
Degree of a Node:-The degree of a node is the total number of branches of that node.
Forest:- A collection of disjoint trees is called a forest.
Application of tree:
There are many search application of tree in which few are listed below:-
A branch of tree is used in routers in storing routing information.
Tree are used to store data in hierarchical structure.
Insertion deletion and searching is very efficient and faster in tree as compared to other linear data structure
Types of tree:
Binary tree.
Binary search tree.
AVL tree.
B tree.
Binary tree :- Binary tree in a type of tree in data structure where each node can have atmost of two children. Every node in a binary tree consist of three things .The left pointer which points towards the left sub tree, the right pointer which points towards the right sub tree and the data element . The node at the top of the hierarchy of a tree is called the root node.
Binary search tree :- Binary search is a tree in data structure where each node can have atmost of two children. Binary search tree has a property that if the value of node is lesser than node will be in the lft subtree and the value greater than the node will be there in the right sub tree.
AVL tree :- Avl tree is a type of binary tree which can exhibit maximum of two child.when the balancing factor i.e difference of the height of left subtree and right subtree having the value 0,1 or -1 then it is a type of AVL tree. But if the balancing factor does not satisfy this value then we need to undergo some avl rotations .
There are total four type of rotations :-
Left Left rotation.
Right Right rotation.
Left Right rotation.
Right Left rotation
Rotations will be done depending upon the structure of the tree as well as the balancing factor of the node.
B tree :- Like in other tree they have maximum of two children and one main key node and node can have maximum of two child but B tree is slightly different from rest of these trees , B tree can exhibit more than one key node and can have more than two children.
Traversal in a tree:
Pre ordered traversal :- In preordered traversal , we will firstly traverse through the root, then the left subtree and then comes the right subtree.
Post ordered traversal :- In postordered traversal, we will firstly traverse through the left subtree, then the right subtree and lastly the root node.
Inordered traversal :- In Inordered traversal, we will firsly traverse through the left subtree, then the root node and lastly through the right subtree.