AVL & B Tree

AVL TREE

AVL TREE is balance binary search tree, so the difference height of left subtree and right subtree is 0 or 1.

4 case of unbalance:

·       Case 1 : (L-L) the deepest node is located at the left sub tree of the left child of T.

·       Case 2 : (L-R) the deepest node is located at the right sub tree of the right child of T.

·       Case 3 : (R-L) the deepest node is located at the right sub tree of the left child of T.

·       Case 4 : (L-R) the deepest node is located at the left sub tree of the right child of T.

Inserting and Deleting in AVL Tree is the same as normal Binary tree but if the tree is not balance after insert or delete we need to rebalance it.

Rebalance AVL TREE

1. · Single Rotation Case 1 & 2

1. · Double Rotation to fix case 3 & 4

Example for fixing case 3:

                                                First rotation: node R and S.

First rotation: node R and S.

Second rotation: node R and T

B-Tree

Property of B-Tree of order m:

·       Every node has at most m children.

·       Every node (except root) has at least m/2 children.

·       The root has at least 2 children if it is not a leaf.

·       A non leaf node with k children contain k-1 keys.

·       All data are kept in sorted order.

·       All leaves are at the same level (the bottom level).

B-Tree with order m of: 3 is also called as 2-3 Tree, which satisfies the following property:

·       Each internal node (non leaf) is either a 2-node or a 3-node.

o   2-node    : has one data and two children (left and middle child)

o   3-node    : has two data and three children (left, middle and right child)

·       All data are kept in sorted order.

o   Let A be the data stored in a 2-node. Left sub-tree should contain data less than A, middle sub-tree should contain data greater than A.

o   Let A and B the data stored in a 3-node. Left sub-tree should contain data less than A, middle sub-tree should contain data greater than A and less than B, right sub-tree should contain data greater than B.

·       All leaves are at the same level (the bottom level).

Insert in B-tree:

·       Supposed we want to insert a new data key.

·       First we should find where key should be placed in 2-3 tree using search algorithm, it will be in one of the leaf.

·       If the leaf is 2-node then simply put the new key there (so it’s become a 3-node).

·       If the leaf is already a 3-node push the middle data between A, B and key (A and B are two data in that 3-node) to its parent and split the two remaining data into two 2-node. Recursively fix the parent.

Example for 2-3 tree:

Insert (45). The leaf is a 2-node, just put (45) there.

Insert (75). The leaf is a 3-node.

Push the middle value (80) to its parent and split 75 with 90

Add caption

2-3 tree after insertion of (75)

Insert (24). The leaf is 3-node. Push the middle value (24) to its parent.

Its parent is also a 3-node. Push the middle value (24) to its parent.

2-3 tree after insertion of (24)

Insert (95). The leaf is a 3-node. Push the middle value (95) to its parent.

Its parent is also a 3-node. Push the middle value (80) to its parent.

2-3 tree after insertion of (95)

Delete in B-Tree:

•    Supposed we want to delete a key from 2-3 tree.
• ·       Like in BST, we should find a leaf key which can replace key we want to delete. It means deletion always occurs in a leaf node.
• If the leaf is a 3-node, then delete the key so it becomes a 2-node.
• If the leaf is a 2-node:

1.              If parent is 3-node, get one value from it. If sibling is a 3-node, push one value of its sibling to the parent (to make the parent 3-node again). If the sibling is a 2-node, make the parent a 2-node and merge current node with its sibling.
2.    If parent is 2-node. If sibling is a 3-node then get one value from parent and push one value from sibling to its parent. Else merge parent with sibling.

•   Fix parent recursively.

       Example of 2-3 Tree:

Delete (23). The node is at leaf and the leaf is 3-node. Just delete it.

Delete (50). Replace (50) with (40), and delete (40) at the leaf (a 2-node).

Parent is a 3-node but sibling is 2-node. Merge (25) and (30).

2-3 tree after deletion of (50)

2-3 tree after deletion of (30) and (15)

Searching in B-Tree:

   Because all data in 2-3 tree are stored in sorted order, searching in 2-3 tree is easy. We can extend the search algorithm for binary search tree to obtain the search algorithm in 2-3 tree.

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)

AVL & B-TREE ANSWER FOR QUESTIONS