06 - AVL

AVL is another version of Binary Search Tree. The concept of AVL is still the same with binary search tree, but this time they limit to the size of the binary search tree to log(n). How did they do this?

for example you have 7 input, 5 6 7 0 4 3 8.

The tree will look like this:

5

0 6

4 7

3 8

If you see 3 is the very furthest level(imagine a pyramid, 5 is the top level 1, 0 and 6 level 2 and so on). If we want to search 3, it will took us 3 step to find it. Using AVL we can reduce this time to only 2 step. By moving 2 to upper level and making 3 go down 1 level, it will make 2 step. The new AVL tree will look like this:

4

0 6

3 5 7

8

If we look 4 is move to level 1 and 5 go to level 3, by using AVL it will make the furthest note will only 1 or 0 to the other lane. We can clearly see that 8 is different 2 level than 0, well there's nothing lower than 0 so this is a special case.

Well the technique is more or less the same with BST, but there's 4 new technique to make AVL work, it's called L, R, LR, RL. R= Right, L= Left.

Left means that it will take data from the root's right side and save the left side of the new root's left side. then make the root's right side become the root, the main root make it to the left side and the left side connect it to the root's right. Confusing ? yes

z=root

x=root's right side

y=root's right side's left side

Normal BST:

z

x

y

now transform it to like this

x

z y

simple right basically imagine a triangle, and the tip is at x. Just turn it sideways done.

Right side is the same except you flip it. Left become right, right becomes left.

LR and RL is basicly left then right and the other way.

Well you can see the code at https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

If you want to delete it will find the node and take the left side if there's none take the right side. Then check again whether it has fulfill all requirement if not runt left or right side again.

if you delete 3, 4, 8

6

0 7

5

Well Good luck.

B-Tree

Another version of BST, This time you need to determine how many max one node can have.