Today topic is divided by 2 topic the first topic is AVL Tree lectured by Pa Sky and the second is lectured by Selvakumar Manickam
Before we know what AVL tree is first we have to know what is balanced binary search tree.
First Topic
Balanced Binary Search Tree
A self-balancing binary search tree or height-balanced binary search tree is a binary search tree (BST) that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically.
example:
Why do we have to learn Balanced Binary Tree?
Most operations on a BST take time proportional to the height of the tree, so it is desirable to keep the height small.
Self-balancing binary trees solve this problem by performing transformations on the tree at key times, in order to reduce the height. Although a certain overhead is involved, it is justified in the long run by ensuring fast execution of later operations.
AVL Tree
AVL tree (Georgy Adelson-Velsky and Evgenii Landis’ tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented.[2] 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.
well to put it simple on how to use a avl tree is to compare the nodes that we want to input and put it in the left side or the right side depends of it’s value of input nodes.
Class AVL Tree supports the following functionality:
1.insertion of a new entry in the tree.
2.removal of any entry in the tree.
3.search for any entry in the tree.
4.”sanity check” for the tree (sanity check is a basic test to quickly evaluate whether a claim or the result of a calculation can possibly be true)
5. 4 various tree traversals
– preorder
– inorder
– postorder
– inorder non-recursive.
How to make a unbalanced BST into Balance BST(AVL)
the main point to make a AVL Tree is to minimum the height of the BST and make the BST stabilize own it self .
1.Calculate the height
-Max (HeightLeft , HeightRight)+1
-Leaf that doesn’t have anymore branch = NULL or 0
2.Balance factor
-Balance factor = HeightLeft – HeightRight
Note:
– if the balance factor is equal to (-1) that means your balance tree is advancing to the right.
-if the balance factor is equal to (+1) that means that your balance factor is advancing to the left.
-if the balance factor is equal to (0) that means that your balance factor is in balance position
*to be categorized on balance factor the calculation has to be at a number of (-1,0,1)
3.Rotation
Rotation is needed if the total of balance factor is not equal to (-1,0,1)
example
from this picture we know that after we insert the number 7 on the BST the tree becomes unbalanced.
To properly rotate a BST Tree in to a Balanced Tree(AVL) we hav to the these two rotations :
1.Single Rotation
A single rotation is required when the node just added is on the right sub-tree of the right node of the unbalanced node or the left sub-tree of the left node of the unbalanced node.
2.Double Rotation
A double rotation is required when the node just added is on the right sub-tree of the left node of the unbalanced node or the left sub-tree of the right node of the unbalanced node.
4.Delete
to delete a AVL tree is a little similar like deleting a BST Tree but after you delete your nodes make sure you balance the tree again so the tree stays AVL not BST
Thing you have to watch when you delete a node on AVL tree
-Check the height and the balance factor.
-do a rotation if necessary
These examples have been greatly simplified from the actual amount of work required. All of these examples could have more children on almost every node, which would require a greater deal of reassigning pointers.
For more understanding how these concept that i have shown you open here
->AVL Tree Visualzation
Second Topic
As for the second topic the lesson is about the general meaning of data structure , introduction of tree , and discuss about binary tree. These topics is lectured by a guest lecture named Selvakumar Manickam .
for these materials it generally talks about the point of studying data structure as the basic for studying Tree and the principal of studying all kind of tree in programming for more detailed information you can see my older post below:
Summary Session 1 Data Structures
(The general meaning of Data Structures in computer Programming)
Summary Session 4 Data Structures
(Tree indroduction)
Summary Session 5 Data Structures
(More information about tree)