Binary Search Tree (BST)

Left child < Root < Right Child
Recursion of left child from the root gives the minimum element and Recursion of right child from the root gives the maximum element.
Inorder traversal of BST is called "Binary Sort".Sorted order of data resulting in ascending order.

"Deletion of a node" in BST :-
   (i) If node has no child,simply delete that node.
   (ii) If node has 1 child, delete that node and replace it with child.
   (iii) If node has 2 children,delete that node and replace it with inorder successor or predecessor of that node.

HEAP TREE

Heap tree is a complete binary tree with heap property (min heap/max heap)
There are two types of heap trees:-
  (i) Min heap : At any sub-tree the root value always smaller than its children.
  (ii) Max heap : At any subtree the root value always greater than its children.

Heap Sort: By deleting the root node from heap tree and placing the deleted node in output , until all nodes are deleted.
It gives either ascending order (min heap) or descending order (max heap)


AVL Search Tree

Devised by Adelson Velski Landis
Height balanced binary search tree
Balance factor (B_f) is:

|b_f| = |h_L – h_R| =< 1

B_f = -1 or 0 or 1

Rotation is a technique used in the AVL tree to balance the height.

Four types of rotations are:

(i) Right - Right [RR] Rotation (Single Rotation):

(ii) Left - Left [LL] Rotation ( Single Rotation):

(iii) Left - Right [LR] Rotation ( Double Rotation):

(iv) Right - Left [LR] Rotation (Double Rotation):

Minimum number of nodes in a AVL tree of height 'h'