AVL Tree and B-Tree

AVL Tree and B-Tree

AVL Tree

·       Introduction

Before we dive into the AVL tree, we should review Binary Tree. The binary tree is one of the data structures, it features sorting, ease insertion and deletion, and searching, although being able to search at a fast rate, the binary tree has a weakness. The quickness of the methods in a binary tree depends on the height of the tree, moreover it can be as large as n-1 when it's skewed, furthermore, if this happens the searching, deletion, and insertion method’s rate will be comparable to linear search. The AVL Tree takes to resolve the weakness of the binary tree by commencing rotation’s when the tree is Imbalance. The goal of this balancing is to rotate the binary tree until it has the minimum height and.

·       Balance Factor

Balance Factor is a method to adjust the balance of an AVL Tree from an imbalance state. The formula is as stated below:

Balance factor = height of the left subtree – height of right subtree = {-1,0,1}

|bf| = |hl – hr| <= 1

·       Operations

o   Rotation

Before we dive into Insertion there are types of rotation:

1.     LL Rotation: the new node is inserted in the left sub-tree of the left sub-tree of the critical node

2.     RR Rotation: the new node is inserted in the right sub-tree of the right sub-tree of the critical node.

3.     LR Rotation: the new node is inserted in the right sub-tree of the left sub-tree of the critical node

4.     RL Rotation: the new node is inserted in the left sub-tree of the right sub-tree of the critical node

o   Insertion

The insertion process on the AVL Tree is the same with the process on binary tree. The difference is, AVL tree has a feature that balances the tree and by adding a node to the tree can cause the tree to become imbalance, to avoid this the tree automatically balances itself by doing rotation.

There are 4 cases that need attention:

1.     the deepest node is located at the left subtree of the left child of T.

2.     the deepest node is located at the right subtree of the right child of T.

3.     the deepest node is located at the right subtree of the left child of T.

4.     the deepest node is located at the left subtree of the right child of T.

The violation to case 1 and 2, can be fixed by single rotation on the other hand the violation of case 3 and 4 can be fixed by double rotation.

Single Rotation

Double Rotation

o   Deletion

The deletion process in the AVL Tree is almost the same with the binary tree. Its the difference is only located on the balance checking feature that must occur after there is a change in the tree.

                        Exercise:

                                                                                                            

B-Tree

B-Tree is a kind of data structure that facilitates fast access to data stored within the secondary memory by using indexes, moreover the method of this structured data is like using indices in a book to perform a rapid search. B-Tree is suitable for making dictionary and records. Moreover, a B-Tree is also called 2-3 Tree which is caused by the internal node to be label either 2-node or 3-node. 2-node is a leaf that has one data and two children (left and right), and 3-node is a leaf that has 3 children (left, middle right).

The B-Tree is very similar to the M-way tree. It shares the same characteristics as that tree, but the concept of difference between both is very similar to Binary Tree and AVL Tree in which the binary tree cannot handle keys that are inserted in order (1,2,3,4,5… or 10,20,30…), because by doing so the height of the tree will continue to increase.

·       Operations

o   Search

One of the main features of B-Tree is its ability to search very quickly, because the data is sorted already. Below are codes for the searching mechanism:

find(ptr, x)

If ptr

      is NULL then not found

      If x = A then found

      If x < A then find(ptr->left, x)

      If ptr is 3-node

           If x = B then found

           If A < x and x < B then find(ptr->middle, x)

           If B < x then find(ptr->right,x)

o   Insertion

To do insertion the we need to find the place to put it using the search algorithm. If the leaf is 2-node then put the key, there to make it into 3-node. If the leave is already a 3-node put the key into the middle and split the two-remaining data into two 2-node and you must not forget to balance the tree.

o   Deletion

The deletion process in this tree is like BST, where we should find the replacement for the key we want to delete. If the leaf is a 3-node, then delete the key to turn it into a 2-node. If the leaf is a 2-node there will be 2 cases, if the parent of the key is a 3-node, get one value from it. If the sibling is a 2-node turn the parent into a 2-node and merges the current node with its sibling. If the sibling is a 3-node take one of the values on the sibling and put it into the parent to make the parent a 3-node. The second case is when the parent is a 2-node. If the sibling is a 3-node take one of the values on the sibling and put it into the parent to make the parent. Else than that, merge the parent with the sibling, and don’t forget to fix the tree’s balance.

Exercise: