Write short notes on:

  1. Divide and Conquer sorting
  2. AVL Tree

This answer is restricted. Please login to view the answer of this question.

Login Now

a) Divide and Conquer Sorting:

Divide and Conquer is an  important problem-solving technique that makes use of recursion. It is an effective recursive algorithm that consists of two parts:

  1. Divide:- In which smaller problems are solved recursively.
  2. Conquer:- In which the solution to the original problem is then formed from the solutions to the sub-problems.

Traditionally, routines in which the algoritm contains at least two recursive calls are called divide-and-conquer algoritms whereas the recursives routines presented so far in this section are not divide-and-conquer algorithms. Also, the sub-problems usually must be disjoint (i.e. essentially no overlapping), so as to avoid the excessive oosts seen in the sample recursive computation of the Fibonacci numbers.

Following are the divide-and-conquer algorithms:

  1. Quick Sort
  2. Merge Sort
  3. Heap Sort

b) AVL Tree

The first balanced binary tree is the AVL tree. AVL tree checks the height of the left and right sub-trees and assures that the difference is not more than 1. The difference is called the balance factor. An AVL tree is a binary search tree where the balance number at each node is -1, 0, or 1. For an AVL tree of height H, we find that it must contain at least FH+3 – 1 nodes.

Example:

AVL Tree example | Hamro CSIT

The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1.

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .