AVL TREES & B-TREES

AVL TREE

DEFINITION

AVL trees is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes. To ensure that this property is fulfilled, each node will have a variable called the balance factor which is calculated by (height of left subtree - height of right subtree). The node is said to be balanced if and only if the balance factor is = {-1,0,1}. With this condition, the property of the AVL tree will be fulfilled.

BENEFITS

The obvious benefit of an AVL tree when compared with a BST is the worst case time complexity of a search in an AVL tree is O(log n) compared to the O(n) worst case time complexity of a BST. This is simply because an AVL tree will always have the height of O(log n) due to its property.

BALANCING

What happens if we insert a new node or delete a current node (NOTE: insertion and deletion follows the same algorithm as BST's, but is only added with the balancing algorithm which will be discussed) which caused a node to be unbalanced? We will have to do rotations with the unbalanced node. However, we will have to first identify the unbalanced node. When we insert / delete a node, check the balance factor of its parent node, and keep doing this recursively upwards. If there is a case where the node is unbalanced or the balance factor is not {-1,0,1}, we do rotations on that unbalanced node. There are 2 types of rotations: left and right rotate.

* let u be the node which caused the pivot node to be unbalanced

There are 4 possible cases which needs to be handled when a node becomes unbalanced:

1. LEFT LEFT: pivot is left heavy and u->data is less than pivot->data

2. LEFT RIGHT: pivot is left heavy and u->data is greater than pivot->data

3. RIGHT RIGHT: pivot is right heavy and u->data is greater than pivot->data

4. RIGHT LEFT: pivot is right heavy and u->data is less than pivot->data

HANDLING THE CASES

1. LEFT LEFT: do a right rotation on the pivot node

2. RIGHT RIGHT: do a left rotation on the pivot node

3. LEFT RIGHT: do a left rotation on the pivot->left node and then a right rotation on the pivot node

4. RIGHT LEFT: do a right rotation on the pivot->right node and then a left rotation on the pivot node

B-TREE

DEFINITION

A B-tree a self-balancing tree, however it does not implement the properties of a binary search tree. Each node can have more than 2 children and therefore can also contain more than 1 keys. The maximum possible amount of the number of children that each node has is constant throughout the tree and is denoted by M, and we therefore we call it a B-tree with order M. However, we will be only using a B-tree of order 3 for this explanation

PROPERTIES

1. Every node has at most m children.
2. Every node (except root) has at least m/2 children.
3. The root has at least 2 children if it is not a leaf.
4. A non leaf node with k children contain k-1 keys.
5. All data are kept in sorted order.
6. All leaves are at the same level (the bottom level).

SEARCHING ALGORITHM

Let node be the current node we are in and k1, and k2 as its keys. Node will have a left, middle, and right pointer. Node will be a 2-node if it only contains 1 key and a 3-node if it contains 2 keys.

1 IF node == NULL THEN not found

2 IF find == node->k1 THEN found

3 IF find < node->k1 THEN search(node->left, find)

4 IF node is a 3-node:
5 IF find == node->k2 THEN found
6 IF (find > k1 && find < k2) THEN search(node->mid, find)
7 IF find > k2 THEN search(node->right, find)

INSERTION ALGORITHM

1. Find the position of the newly inserted key with the searching algorithm

2. If it is a 2-node, just insert

3. If it is a 3-node, push the median of the 3 data (k1, k2, and the new key) to its parent and split the 2 remaining keys into two 2-nodes. Keep doing this recursively if the parent is a 3-node.

DELETION ALGORITHM

1. Find the key that wants to be deleted and follow the principle of deletion in a BST (if the deleted note is in the leaf node, then we need to find the replacement of the node) which means that deletion always occurs in a leaf node.
2. If the leaf is a 3-node, just delete the key so it becomes a 2-node
3. If the leaf is a 2 node, there are 2 conditions:
1. If the parent is a 3-node, get one value from it. If the sibling is a 3-node, push one of the sibling keys to the parents). If the the sibling is a 2-node, make the parent a 2-node and merge the current node with the sibling.
2. If the parent is a 2-node, we cannot get one value from it. If the sibling is a 3-node, get one value from the parent and push one value from sibling to its parent. else, merge parent with sibling
4. Fix the parents recursively