Introduction To Tree

A binary tree is a tree which has one root (parent) and its two edge branches connecting to its child (node) and in successive manner each child may have another two nodes. The term indegree refers to the number of connecting edge branches merging into a node and the term outdegree refers to the number of edge branches emerging from a node. Usually all nodes have an indegree of 1 and outdegree of 1 or 2 except the root which has an indegree of 0. The node which has an outdegree of 0 is called the leaf node. A root has a height of 1 and its height increases as when the node has a outdegree . A tree which has all nodes skewed in one direction is called a skew tree. A right skew tree is a binary tree in which all the left child will be null and in a left skew tree all the right child will be null. The two types of traversals that can be done on a tree are:

               1. Breadth first traversal or level order traversal
               2. Depth first traversal

A Binary Search Tree (BST) is a tree in which the left child node holds a number lesser than its parent node‘s number and the right child node holds a number greater than its parents node’s number. This method helps in search operation on a binary search tree and its time complexity is log₂N where N represents the number of nodes in a tree.

A AVL tree is a tree which has a property of balancing factor (BF) i.e B_f= H_L – H_R
where H_L - height of left sub tree
                  H_R- height of right sub tree

The balancing factor must be in a range of -1, 0 or +1 and if not so then some of the required rotations can be done according to the unbalanced way of tree . Some of the rotations are:

               1. Left of left rotation ( L of L )
               2. Right of right rotation ( R of R)
               3. Left of right rotation ( L of R )
               4. Right of left rotation ( R of L )

A B - tree is a tree which is perfectly balanced and all its leaf nodes are at the same level. The root of its tree should either be a leaf node or it must contain almost m sub trees where m represents the order of a tree .

TECH

Introduction To Tree