11/05/2016 – Data Structure

Last time we learned about: Binary tree and Binary Search Tree

New topic is BST  (Balance)

Most common Balanced BST is AVL.

AVL is founded by Georgy Adelson-Velsky and Evgenii Landis in 1962. It is the first self-balancing binary search tree. In Binary search tree there is a height. empty sub-tree = 0 and leaf = 1. If the height is > 1, then the tree is overloaded, and needs balancing. There is two condition on balancing tree:

lecture-10-data-structures-and-algorithms-17-638 lecture-10-data-structures-and-algorithms-29-638

A key word from the BULE MALAYSIA:

If L – L / R -R = Cut the middle part, push it to the top, then balance it.

If L – R / R – L = Child becomes parent, parent becomes child

Leave a Reply

Your email address will not be published. Required fields are marked *