AVL Tree & B - Tree

AVL Tree

AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.

AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis. Since AVL trees are height balance trees, operations like insertion and deletion have low time complexity.

AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor.

Balance Factor

• Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node

• Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree)

• The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.

• If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using some rotation techniques.

We can see that the balance factor associated with each node is in between -1 and +1. Therefore, it is an example of AVL tree. (https://www.javatpoint.com/avl-tree)

Rotation Techniques

(Taken from https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm)

• Left rotation (Single rotation)

If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation −

In our example, node A has become unbalanced as a node is inserted in the right subtree of A's right subtree. We perform the left rotation by making A the left-subtree of B.

• Right rotation (Single rotation)

AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right rotation.

As depicted, the unbalanced node becomes the right child of its left child by performing a right rotation.

• Left-Right rotation (Double rotation)

Double rotations are slightly complex version of already explained versions of rotations. To understand them better, we should take note of each action performed while rotation. Let's first check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation followed by right rotation.

State	Action
	A node has been inserted into the right subtree of the left subtree. This makes C an unbalanced node. These scenarios cause AVL tree to perform left-right rotation.
	We first perform the left rotation on the left subtree of C. This makes A, the left subtree of B.
	Node C is still unbalanced, however now, it is because of the left-subtree of the left-subtree.
	We shall now right-rotate the tree, making B the new root node of this subtree. C now becomes the right subtree of its own left subtree.
	The tree is now balanced.

• Right-Left rotation (Double rotation)

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed by left rotation.

State	Action
	A node has been inserted into the left subtree of the right subtree. This makes A, an unbalanced node with balance factor 2.
	First, we perform the right rotation along C node, making C the right subtree of its own left subtree B. Now, B becomes the right subtree of A.
	Node A is still unbalanced because of the right subtree of its right subtree and requires a left rotation.
	A left rotation is performed by making B the new root node of the subtree. A becomes the left subtree of its right subtree B.
	The tree is now balanced.

Operations

Insertion

An insertion in AVL tree is similar to a normal Binary Search Tree insertion. After inserting, we need to fix the AVL  tree using the learned rotations.

• If there is an imbalance in left child of right subtree, then you perform a left-right rotation.
• If there is an imbalance in left child of left subtree, then you perform a right rotation.
• If there is an imbalance in right child of right subtree, then you perform a left rotation.
• If there is an imbalance in right child of left subtree, then you perform a right-left rotation.

Deletion

Deletion can also be performed in the same way as it is performed in a binary search tree. Deletion may also disturb the balance of the tree therefore, various types of rotations are used to rebalance the 

Examples

 B Tree

B Tree is another type of a self-balancing tree.We can represent sample B-tree as follows.

B-Tree is a self-balanced search tree in which every node contains multiple keys and has more than two children.

B-Tree of Order m has the following properties...

Property #1 - All leaf nodes must be at same level.

Property #2 - All nodes except root must have at least [m/2]-1 keys and maximum of m-1 keys.

Property #3 - All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.

Property #4 - If the root node is a non leaf node, then it must have at least 2 children.

Property #5 - A non leaf node with n-1 keys must have n number of children.

Property #6 - All the key values in a node must be in Ascending Order.

For example, B-Tree of Order 4 contains a maximum of 3 key values in a node and maximum of 4 children for a node.

Operations

1. 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.

2. Insertion

In a B-Tree, a new element must be added only at the leaf node. That means, the new key Value is always attached to the leaf node only. The insertion operation is performed as follows...

Step 1 - Check whether tree is Empty.

Step 2 - If tree is Empty, then create a new node with new key value and insert it into the tree as a root node.

Step 3 - If tree is Not Empty, then find the suitable leaf node to which the new key value is added using Binary Search Tree logic.

Step 4 - If that leaf node has empty position, add the new key value to that leaf node in ascending order of key value within the node.

Step 5 - If that leaf node is already full, split that leaf node by sending middle value to its parent node. Repeat the same until the sending value is fixed into a node.

Step 6 - If the splitting is performed at root node then the middle value becomes new root node for the tree and the height of the tree is increased by one.