AVL Tree & B-Tree

AVL Tree

What is AVL Tree?

AVL Tree is a self-balancing Binary Search Tree (BST), link to learn about BST where the difference between the depth of left and right sub-trees cannot be more than one for all nodes. To get the balance factor we get the longest depth of each left  and right of the node. Then using this formula to get the balance, balance = depth of left - depth of right.

 This is an example of a balanced tree:

 This is an example of a unbalanced tree:

As shown, there are 2 node that violates the balance because there are nodes with balance more than one. If this happens we will choose the deepest node that violates the balance factor to be fixed.

Why AVL Trees?

Most of the BST operations take O(h) time where h is the height of BST. Worst cast senario may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(log n) after every insertion or deletion, then we can guarantee an upper bound of O(log n) for all BST operations. The height of AVL tree is always O(log n) for n is the number of nodes in the tree.

How to perform AVL Tree?

To make sure the tree remains balanced after every insertion or deletion, we will enhance or augment the standard BST insert and delete operation to have a method of re-balancing and right and left rotation function. To re-balance a tree, we will need to perform appropriate rotations on the tree. There can be 4 possible cases: 
1. (Left-Left Case) if y is left child of z and x is left child of y, left skewed tree.
2. (Left-Right Case) if y is left child of z and x is right child of y.
3. (Right-Right Case) if y is right child of z and x is right child of y, right skewed tree.
4. (Right-Left Case) y is right child of z and x is left child of y.

Left-Left Case
Left-Right Case
Right-Right Case
Right-Left Case
To imply AVL we need to augment our BST codes by adding height in our struct.
Function for right-rotate, left-rotate and get balance:
Augmented insertion.
Augmented deletion.


B-Tree

What is B-Tree?

B-Tree is a self-balancing search tree. But it is different from BST or AVL tree as it has more than 2 sub-trees and more than 1 keys. B-Tree has a maximum number of children is according to the order, m. The order of the tree is equal to the order. To understand B-Tree we will use B-Tree with the order of 3.

Properties

1. All leaves are at same level.
2. A B-Tree is defined by the term minimum degree ‘t’.
3. Every node except root must contain at least t-1 keys.
4. All nodes (including root) may contain at most 2t – 1 keys.
5. Number of children of a node is equal to the number of keys + 1.
6. All keys of a node are sorted in increasing order.
7. B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.

Search

Search is similar to the search in Binary Search Tree. Let the key to be searched be k. We start from the root and recursively traverse down. For every visited non-leaf node, if the node has the key, we simply return the node. Otherwise, we recur down to the appropriate child (The child which is just before the first greater key) of the node. If we reach a leaf node and don’t find k in the leaf node, we return NULL.

Insertion

1. Insert like a normal BST algorithm.
2. If the space is still enough (< 2) than just insert it without any split.
3. else if the space is (3) then, insertion will cause a split. The middle key will go up to the parent and split to 2 seperate node.

Deletion

1. delete like a normal BST algorithm.
2. If the key k is in node x and x is an internal node, then,
  • If the child y that precedes k in node x has at least t keys, then find the predecessor k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k by k0 in x.
  • If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k0 of k in the subtree rooted at z. Recursively delete k0, and replace k by k0 in x.
  • Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.
3. If the key k is not present in internal node x, determine the root x.c(i) of the appropriate subtree that must contain k, if k is in the tree at all. 
4. If x.c(i) has only t-1 keys, then,
  • If x.c(i) has only t-1 keys but has an immediate sibling with at least t keys, give x.c(i) an extra key by moving a key from x down into x.c(i), moving a key from x.c(i) ’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.c(i).
  • If x.c(i) and both of x.c(i)’s immediate siblings have t-1 keys, merge x.c(i) with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node.
source: GeeksforGeeks/introduction of B-Tree.

AVL Simulation
Insert 5, 6, 7, 0, 4, 3, 8
Delete 3, 4, 8

 B-Tree Simulation
Insert 5, 6, 7, 0, 4, 3, 8
Delete 3, 4, 8

Comments

Post a Comment

Popular posts from this blog

Mid - Sem 2 - Summary

Linked List Linked List is a linear data structure, list of elements are stored randomly at a contagious memory location. Which the elements are accessible using pointers. Unlike array, data's are stored linearly or side by side in a memory and size of memory are limited. A Linked List consist of node, we can insert data inside the node. The node also consist of a 'next' pointer which will point to the next node in the linked list. This next pointer are what connects the linked list together. We also have 'head' this is to mark the beginning or the first node. we can also use 'tail' to mark the last node. The last node will not point anything or pointer a 'NULL'. There are 2 ways of linked list, namely, single linked list and doubly linked list. In doubly linked list, the only different is that, they have a 'prev' pointer. This pointer is use to point the previous node in the linked list. A linked list has a couple important functi...
Read more