Explain the properties of B-tree? Write the algorithm for insertion in a B-tree.

Answer: – Two Russian mathematician, G.M. ADEL’SON-VEL’SKII and E.M. LANDIS, give at technique in 1962. It feasible to balance the bit of binary tree using this technique and resulting tree is called AVL tree in there owner. With the help of AVL tree searching, insertion of an AVL tree with a node can never Exide even in the worst case and thus behavior of an AVL tree could not be much below that of a random binary search tree. A tree is called AVL tree or balanced binary tree if each node possesses on of the fallowing properties.

  1. A node is called left heavy, if the longest path. In its left sub tree is one longer than the longest path of its right sub tree.
  2. A node is called right heavy, if the longest path in the right sub tree is one longer than the longer path of its left sub tree.
  3. A node is called balanced, if the longest paths in both right and left sub tree are equal.

We can insert a new node into a AVL tree by first using the usual binary tree insertion technique, comparing the key of new node with that in the root node and inserting the new node into the left and right sub tree accurately. If offend turns out that the new node can be inserted without changing the height of the sub tree, in that case neither the height nor the balance factor of the root is changed. Even when the height a sub tree increases, it may be sorter sub tree that has grown up, show that only the balance factor of the root will be changed. The only case that can Couse difficulty occurs when the new node is added to a sub tree of the root that is strictly Toller than the other sub tree and height is increased. This would cause one sub tree to have height 2 more the other whereas AVL conditions restrict one height difference to be never more than one. An algorithm of insertion algorithm AVL tree as fallows

Step 1:                  if this is the first insertion then allocate a node, set its fields and return.
Step 2:                  if the information we want to insert is not already present in the tree then link the new node to the existing tree else discard the new information and return.
Step 3:                  Search for an unbalanced node.
Step 4:                  Adjust the balance factors if there is no critical node return.
Step 5:                  if the node was balanced and then becomes heavy or the node was heavy and now becomes balanced then adjust the balanced factors and return.
Step 6:                  Rebalance the tree and return.
Advertisements