Explain AVL Tree. Insert the following elements in AVL Tree and show the AVL Search Algorithm. <br>[8, 5, 10, 2, 13, 4]

An AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

Insertion in AVL Tree

Let's insert the given elements [8, 5, 10, 2, 13, 4] in an AVL tree.

1. Start by inserting the first element 8. This will be the root of the tree.
2. Next, insert 5. Since 5 is less than 8, it becomes the left child of 8.
3. Insert 10. Since 10 is greater than 8, it becomes the right child of 8.
4. Insert 2. Since 2 is less than 8 and also less than 5, it becomes the left child of 5.
5. Insert 13. Since 13 is greater than 8 and also greater than 10, it becomes the right child of 10.
6. Insert 4. Since 4 is less than 8, less than 5 but greater than 2, it becomes the right child of 2.

After these insertions, the tree becomes unbalanced and needs to be balanced.

Balancing AVL Tree

The balance factor of a node in an AVL tree is the difference between the height of the left child and the height of the right child. If this balance factor becomes more than 1 or less than -1, the tree needs to be balanced.

After inserting the elements, the tree looks like this:

        8
       / \
      5   10
     /     \
    2       13
     \
      4

The balance factor for each node is:

Node	Balance Factor
2	-1
5	2
8	1
10	-1
13	0

Node 5 has a balance factor of 2, which means the tree is unbalanced and needs to be balanced. This can be done by performing a right rotation on node 5.

After the right rotation, the tree becomes:

        8
       / \
      2   10
     / \    \
    4   5    13

Now, the balance factor for each node is:

Node	Balance Factor
2	0
4	0
5	0
8	0
10	-1
13	0

Now, the tree is balanced.

AVL Search Algorithm

The AVL search algorithm is similar to the binary search tree search algorithm. It starts at the root and moves to the left or right child depending on whether the value to be searched is less or greater than the current node.

Let's search for the value 13 in the AVL tree.

1. Start at the root, which is 8.
2. Since 13 is greater than 8, move to the right child, which is 10.
3. Since 13 is greater than 10, move to the right child, which is 13.
4. The value 13 is found.

The AVL search algorithm is efficient because it takes O(log n) time, where n is the number of nodes in the tree. This is because the height of the AVL tree is always log n.