Introduction to the AVL tree.














































Introduction to the AVL tree.



Description: 
An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.

Def: An AVL tree is a binary search tree with a balance condition i.e the difference between left subtree height and right subtree height is at most 1.


As an Example, among the above binary search trees, the left one is not an AVL tree, whereas the right binary seacrh tree is an AVL tree.  

Properties of AVL Tree:-
A binary tree is said to be an AVL tree, if:
1)It is a binary search tree, and
2)For any node X, the height of left subtree of X and height of right subtree of X differ by at most 1.
3) Every sub-tree is an AVL tree

AVL Tree Declaration :
Since AVL tree is a BST, the declaration of AVL is similar to that of BST. But just to simplify the operations, I also include the height as part of the declaration.
class AVLNode: def _init_ (self,data,balanccFactor,left,right): self.data= data self. balanceFactor = 0 self.left = left self.right= right def height(self): return self.recHeight(self.root) def recHeight(self,root): if root == None: return 0 else: leftH = self.recHeight(r.left) rightH = self. recHeight(r.right) if leftH>rightH: return 1 +leftH else: return 1 +rightH

Minimum/Maximum Number of Nodes in AVL Tree:

For simplicity let us assume that the height of an AVL tree is h and N(h) indicates the number of nodes in AVL tree with height h. To get the minimum number of nodes with height h, we should fill the tree with the minimum
number of nodes possible. That means if we fill the left subtree with height h-1 then we should fill the right subtree with height h - 2. As a result, the minimum number of nodes with height h is:
N(h) = N(h - 1) + N(h - 2) + 1

In the above equation:
%u2022 N(h - 1) indicates the minimum number of nodes with height h - 1.
%u2022 N(h - 2) indicates the minimum number of nodes with height h - 2.
%u2022 ln the above expression, "1" indicates the current node.
We can give N(h -1) either for left subtree or right subtree

AVL tree property is ensuring that the height of an AVL tree with n nodes is O(logn).

More Articles of Khushboo Singh:

Name Views Likes
Python program to insert an element in binary tree. 820 20
Tokenize text using NLTK in Python. 1198 12
Python Remove multiple elements from list while Iterating. 731 22
Python How to Check if an item exists in list ? 4267 14
Python How to remove multiple elements from list ? 737 26
Python program to check if two trees are mirror of each other without using recursion. 660 19
Python program to find maximum in Binary tree. 929 19
Python Check if all elements are same using Set 709 15
Python program to find diameter of a binary tree. 1081 20
Python program to print root to leaf paths without using recursion. 840 20
Python program to find root of the tree where children id sum for every node is given. 669 23
Introduction of Python NLTK library 1355 25
Categorizing and Tagging Sentences using NLTK in Python . 999 19
Python program to find height of a tree without using recursion. 662 16
Python program to find sum of all nodes of the given perfect binary tree. 656 19
Python program to find minimum in binary tree. 821 23
Python Check if element exist in list using list.count() function. 690 13
Python program to convert a given binary tree to doubly linked list. 883 20
Python program to find distance between two nodes of a binary tree. 1521 20
NLTK stop Words 1134 13
Python program to find largest binary search tree in a Binary Tree. 934 20
Python program to find inorder successor in binary search tree with recursion. 1201 18
Python program to convert a binary tree into doubly linked list in spiral fashion. 794 15
Python List check if element are same using all() 667 12
Python program to check if two trees are identical using recursion. 706 30
Python Find the occurrence count of an element in the tuple using count() 964 23
Python Convert two lists to a dictionary 723 19
Python program to construct a complete binary tree from given array. 1426 14
Python program to find diameter of binary tree in O(n). 870 17
Introduction to the AVL tree. 740 15
Python program to check if two trees are identical without using recursion 660 17
Python Convert a list of tuples to dictionary. 1077 24
Python program to convert a binary tree to a circular doubly link list. 645 21
Python Check if element exist in list based on own logic. 737 23
Python program to merge two binary trees by doing node sum using recursion 999 27
Python program to check whether a given binary tree is perfect or not. 675 17
Python Check if all elements are same using list.count(). 1083 28
Python program to find an element into binary tree 627 12
Python program to find lowest common ancestor in a binary tree 1209 24

Comments