Python program to find an element into AVL tree

Article Creation Date : 18-Jun-2021 06:58:29 AM

Description:
   Searching operation is similar to as that of Bst but searching in AVL 
is more efficient than BST as AVL is self balanced BST.


In BST, the time complexity of search operation (average case) is taken to be O(log n). But in the worst case, i.e the degenerate trees/skewed trees time complexity of search operation is O(n) which can also be attained using array or linked list. So, in order to remove this problem, balanced binary search tree (AVL tree) was introduced in which the time complexity of search operation remains O(log n).

Program:

class TreeNode(object): 
    def __init__(self,_val): 
        self.val = _val 
        self.left = None
        self.right = None
        self.height = 1
        
class AVL_Tree(object): 
    #steps:
    # 1)perform simple BST insertion
    # 2)modify the height 
    # 3)Get the Balancing Factor
    # 4)Balance The tree using required set of rotation to get balanced binary search tree,ie. AVL
    def insert(self, root, val): 
               
        #Simple Bst Insertion:
        if not root: 
            return TreeNode(val) 
        elif val < root.val: 
            root.left = self.insert(root.left, val) 
        else: 
            root.right = self.insert(root.right, val)
       
        # 2)modify the height      
        root.height = 1 + max(self.Height(root.left), self.Height(root.right)) 
        # 3)Get the Balancing Factor
        balance = self.check_Avl(root) 
        # 4)Balance The tree using required set of rotation
        
        #RR Rotation as tree is Left Skewed
        if balance > 1 and val < root.left.val: 
            return self.RR(root) 

        #LL Rotation as tree is Right Skewed
        if balance < -1 and val > root.right.val: 
            return self.LL(root) 
        #RL Rotation as tree is Left then Right Skewed
        if balance > 1 and val > root.left.val: 
            root.left = self.LL(root.left) 
            return self.RR(root) 
        #LR Rotation as tree is Right then Left Skewed
        if balance < -1 and val < root.right.val: 
            root.right = self.RR(root.right) 
            return self.LL(root) 
  
        return root 
     #LL Rotation
    def LL(self, node): 
       
        p = node.right 
        t = p.left
        #Rotations:
        p.left = node 
        node.right = t 
        #modify the heights: 
        node.height = 1 + max(self.Height(node.left), self.Height(node.right)) 
        p.height = 1 + max(self.Height(p.left), self.Height(p.right)) 
   
        return p 
    #LL Rotation
    def RR(self, node): 
  
        p = node.left 
        t = p.right
        #Rotations:
        p.right = node
        node.left = t 
        #modify the heights:
        node.height = 1 + max(self.Height(node.left), self.Height(node.right)) 
        p.height = 1 + max(self.Height(p.left), self.Height(p.right)) 
        return p 
    #Getting the Height
    def Height(self, root): 
        if not root: 
            return 0
  
        return root.height 
    #Getting the Balancing Factor
    def check_Avl(self, root): 
        if not root: 
            return 0
  
        return self.Height(root.left) - self.Height(root.right) 
  
    def preOrder(self, root): 
  
        if not root: 
            return
  
        print("{0} ".format(root.val), end="") 
        self.preOrder(root.left) 
        self.preOrder(root.right) 


def insert_data(_data):
        mytree = AVL_Tree()
        root = None
        for i in _data:
            root = mytree.insert(root,i)
        print("Preorder Traversal of constructed AVL tree is:")
        mytree.preOrder(root)
        print()
        return root
def Search(root,val):
    if (root is None):
        return False
    elif (root.val == val):
        return True
    elif(root.val < val):
        return Search(root.right,val)
    return Search(root.left,val)
    return False

def main():
    root = insert_data([10,8,15,7,9,12,17,16,18,6,4])
    t = int(input('Enter the key to be searched:\t'))
    if(Search(root,t)):
        print()
        print('"Element found in AVL Tree"')
    else:
        print()
        print('"Element not found in AVL Tree"')
if __name__ == "__main__":
    main()
else:
    pass

Output:
Preorder Traversal of constructed AVL tree is:
10 8 6 4 7 9 15 12 17 16 18 
Enter the key to be searched:	23

"Element not found in AVL Tree"

Views : 3658

ABOUT THE AUTHOR

Photo Credit : Designed by Freepik

Bhumika Makwana

India

View Profile

More Articles of Bhumika Makwana:

Name	Views	Likes
Python program to find largest value in each level of binary tree	1713	19
Python program to convert a given binary tree to a tree that holds logical and property	561	12
Python Program to Insert into AVL tree	3449	24
Python program to print the nodes at odd levels of a tree	670	20
Python program to check if a binary tree is binary search tree or not	1640	19
Python program to find smallest value in each level of binary tree	906	15
Implement A Queue With Two Stacks	603	19
Introduction to Python DeepLearning Library (Keras)	748	20
python program to remove duplicate elements from the binary search tree	2164	18
Python program to find largest subtree sum in a tree	988	22
Python program to find an element into binary search tree	611	21
Python program to check if two nodes are cousins in a binary tree	976	18
Python height of the binary search tree	2022	14
Python program to find averages of levels in binary tree	663	18
Python program to understand Red-Black trees and insert nodes to it	698	16
Python program to check if a given graph is tree or not	1641	17
Python program to find depth of the deepest odd level leaf node	696	26
Python program to delete leaf nodes with value as x	1058	28
Python program to find maximum level sum in binary tree	1238	19
Python Program to Calculate Size of a Tree using Recursion	2619	13
Python program to check if an array represents Inorder of Binary Search tree or not	799	29
Print cousins of a given node in Binary Tree	1329	25
Python program to find all duplicate subtrees	931	14
Python program to find lowest Common Ancestor in a binary search tree	565	16
Python program to check if removing an edge can divide a binary tree in two halves	773	15
Python Hands on Deep Learning with Keras	753	19
Python program to find largest subtree having identical left and right subtrees	863	19
Python program to find the given level order traversal of a binary tree, check if the tree is a min-heap	668	18
Python program to check if two trees are mirror	654	22
Python program to check if a given binary tree is sumtree	1079	27
Python program to find distance between two nodes of a binary search tree	1474	12
Python program to convert a binary tree into its mirror tree	915	17
Python program to find an element into AVL tree	3658	11
Python program to check if given preorder, inorder and postorder traversals are of same tree	980	18
Python program to check if leaf traversal of two binary trees is same?	707	20
Python program to check whether a binary tree is a full binary tree or not using recursion	1161	22
Python Program for Deletion into Avl	671	25
Python program to construct tree from given inorder and preorder traversals	1699	27
Python program to convert a binary search tree into a Min-Heap	898	13
Python program to convert ternary expression to a binary tree	903	13
* Python program to insert an element into AVL tree	13	12
Python program to find a pair with given sum in binary search tree	1096	27
Python program to diagonal sum of a binary tree	671	12
Python program to convert an arbitrary binary tree to a tree that holds children sum property	644	15
Python program to find an element into red black tree	1490	25

Python program to find an element into AVL tree

More Articles of Bhumika Makwana:

Comments

Brilliantly

Content & Links

Articles

Quick Links