Summary

AVL TREE

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

This tree beside is a normal BST (Skewed BST) where all the nodes are on the right side because 2>5>7>9>11. Suppose now we want to search for node 11. This search will take O(n) time to do the searching. This is very time consuming and has no difference with Linked Lists. But if we use the concepts of AVL tree it's gonna cost us O(log n) time. Let's look at an example:

We are gonna insert 2, 5, 7, 9, and 11 as the nodes.

First, when we insert 2 the tree us going to look like this:

Next, the tree will look like this when we insert 5:

Now, when we insert 7 this is how the tree will look:

Here the tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation. We make 2 the left subtree of 5. Same goes with right rotation.

Double Rotation

Suppose we have a tree which looks like this :

First, we perform the right rotation along 5 node, making 5 the right subtree of its own left subtree 3. Now, 3 becomes the right subtree of 2. Node 2 is still unbalanced because of the right subtree of its right subtree and requires a left rotation. Left rotation is performed by making 3 the new root node of the subtree. 2 becomes the left subtree of its right subtree 3. It looks like this:

HEAP & TRIES

Heap

Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly.

1. Min Heap

-Each node’s element is smaller than its children’s element.

-It implies that the smallest element is located at the root of the tree.

-The largest element is located somewhere at one of the leaves node.

-Heap can be implemented using linked-list, but it is much easier to implement heap using array.

2. Max Heap

-Each node’s element is larger than its children’s element.

-It implies that the largest element is located at the root of the tree.

-Max-heap holds the same principle as min-heap and can be used to create priority queue which need to find the largest element instead of the smallest one.

3. Min Max Heap

-The heap condition alternates between minimum and maximum level to level

-Each element on even/odd level are smaller than all its children (min-level).

-Each element on odd/even level are larger than all its children (max-level).

-The purpose of min-max heap is to allow us to find both the smallest and the largest element of the heap at the same time.

In Min Max Heap,

-The smallest element is located at the root.

-The largest element is located in one of the root’s child (either left/right child).

Tries

-Tries (prefix tree) is an ordered tree data structure that is used to store an associative array (usually strings)

-The term TRIE comes from word RETRIEVAL, because tries can find a single word in a dictionary with only a prefix of the word.