7. AVL Tree

AVL Tree¶

• It is a Binary Search Tree(BST) with Balance Factor for every node. #### Rules

• Rotations

  • Left-Left Insertion: 1 Right Rotation
  • Right-Right Insertion: 1 Left Rotation
  • Left-Right Insertion: 1 Left Rotation, 1 Right Rotation
  • Right-Left Insertion: 1 Right Rotation, 1 Left Rotation

• The portion of tree(3 nodes) which disturbs the balance, select the median element and make it root during rotations

Operations¶

• Insertion Rules:

  • Step-1 Perform normal BST insertion
  • Step-2 Update the height of ancestor node
  • Step-3 Calculate the balance factor

  • Step-4 If node is unbalanced then check for the following cases and balance the tree

    • Case - 1: Left Left Insertion
      • Rotate Right
    • Case - 2: Right Right Insertion
      • Rotate Left
    • Case - 3: Left Right Insertion
      • Rotate Left, then Rotate Right
    • Case - 4: Right Left Insertion
      • Rotate Right, then Rotate Left

• Deletion:

  • Step-1 Perform BST Deletion
  • Step-2 If the tree is left with only one node, return the node
  • Step-3 Update the height of ancestor node
  • Step-4 Get balance factor

  • Step-5 If the node is unbalanced then check for the following cases and balance the tree

    • Case - 1: Left Left Insertion
      • Rotate Right
    • Case - 2: Right Right Insertion
      • Rotate Left
    • Case - 3: Left Right Insertion
      • Rotate Left, then Rotate Right
    • Case - 4: Right Left Insertion
      • Rotate Right, then Rotate Left

References¶

1. https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
2. https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

In [9]:

from utils.nodes import AVLTreeNode as Node
from utils.tree_traversal import TreeTraversal as tt

from utils.nodes import AVLTreeNode as Node from utils.tree_traversal import TreeTraversal as tt

In [10]:

class AVLTree:
    def get_balance_factor(self, node):
        if node is None:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def get_height(self, node):
        if node is None:
            return 0
        return node.height

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

        # rotation
        y.left = z
        z.right = T2

        # update height
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        # rotate
        y.right = z
        z.left = T3

        # update height
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def insert_node(self, root, data):

        # Step-1 - Perform normal BST insertion
        if root is None:
            root = Node(data)
            return root

        if data == root.data:
            return root
        elif data < root.data:
            root.left = self.insert_node(root.left, data)
        else:
            root.right = self.insert_node(root.right, data)

        # Step-2 - Get height of the ancestor node
        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        # Step-3 - Get balance factor
        balance_factor = self.get_balance_factor(root)

        # Step-4 - If the node is unbalanced
        # then check these 4 cases and balance the tree
        # Case - 1: Left Left
        if balance_factor > 1 and data < root.left.data:
            return self.right_rotate(root)

        # Case - 2: Right Right
        if balance_factor < -1 and data > root.right.data:
            return self.left_rotate(root)

        # Case - 3: Left Right
        if balance_factor > 1 and data > root.left.data:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # Case - 4: Right Left
        if balance_factor < -1 and data < root.right.data:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def delete_node(self, root, key, successor_tree=True):

        # Step-1 Perform BST deletion
        if root is None:
            return root

        if key < root.data:
            root.left = self.delete_node(root.left, key)
        elif key > root.data:
            root.right = self.delete_node(root.right, key)
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
        # BST deletion over

        # Step-2 Check again if tree is left with only one node
        if root is None:
            return root

        # Step-3 Update ancestor node height
        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        # Step-4 Calculate balance factor
        balance_factor = self.get_balance_factor(root)

        # Step-5 If the node is unbalanced, balance the tree
        # considering the same 4 cases
        # Case - 1: Left Left
        if balance_factor > 1 and self.get_balance_factor(root.left) >= 0:
            return self.right_rotate(root)

        # Case - 2: Right Right
        if balance_factor < -1 and self.get_balance_factor(root.right) <= 0:
            return self.left_rotate(root)

        # Case - 3: Left Right
        if balance_factor > 1 and self.get_balance_factor(root.left) < 0:
            # balance the left subtree
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # Case - 4: Right Left
        if balance_factor < -1 and self.get_balance_factor(root.right) > 0:
            # balance the right sub tree
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

class AVLTree: def get_balance_factor(self, node): if node is None: return 0 return self.get_height(node.left) - self.get_height(node.right) def get_height(self, node): if node is None: return 0 return node.height def left_rotate(self, z): y = z.right T2 = y.left # rotation y.left = z z.right = T2 # update height z.height = 1 + max(self.get_height(z.left), self.get_height(z.right)) y.height = 1 + max(self.get_height(y.left), self.get_height(y.right)) return y def right_rotate(self, z): y = z.left T3 = y.right # rotate y.right = z z.left = T3 # update height z.height = 1 + max(self.get_height(z.left), self.get_height(z.right)) y.height = 1 + max(self.get_height(y.left), self.get_height(y.right)) return y def insert_node(self, root, data): # Step-1 - Perform normal BST insertion if root is None: root = Node(data) return root if data == root.data: return root elif data < root.data: root.left = self.insert_node(root.left, data) else: root.right = self.insert_node(root.right, data) # Step-2 - Get height of the ancestor node root.height = 1 + max(self.get_height(root.left), self.get_height(root.right)) # Step-3 - Get balance factor balance_factor = self.get_balance_factor(root) # Step-4 - If the node is unbalanced # then check these 4 cases and balance the tree # Case - 1: Left Left if balance_factor > 1 and data < root.left.data: return self.right_rotate(root) # Case - 2: Right Right if balance_factor < -1 and data > root.right.data: return self.left_rotate(root) # Case - 3: Left Right if balance_factor > 1 and data > root.left.data: root.left = self.left_rotate(root.left) return self.right_rotate(root) # Case - 4: Right Left if balance_factor < -1 and data < root.right.data: root.right = self.right_rotate(root.right) return self.left_rotate(root) return root def delete_node(self, root, key, successor_tree=True): # Step-1 Perform BST deletion if root is None: return root if key < root.data: root.left = self.delete_node(root.left, key) elif key > root.data: root.right = self.delete_node(root.right, key) else: if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # BST deletion over # Step-2 Check again if tree is left with only one node if root is None: return root # Step-3 Update ancestor node height root.height = 1 + max(self.get_height(root.left), self.get_height(root.right)) # Step-4 Calculate balance factor balance_factor = self.get_balance_factor(root) # Step-5 If the node is unbalanced, balance the tree # considering the same 4 cases # Case - 1: Left Left if balance_factor > 1 and self.get_balance_factor(root.left) >= 0: return self.right_rotate(root) # Case - 2: Right Right if balance_factor < -1 and self.get_balance_factor(root.right) <= 0: return self.left_rotate(root) # Case - 3: Left Right if balance_factor > 1 and self.get_balance_factor(root.left) < 0: # balance the left subtree root.left = self.left_rotate(root.left) return self.right_rotate(root) # Case - 4: Right Left if balance_factor < -1 and self.get_balance_factor(root.right) > 0: # balance the right sub tree root.right = self.right_rotate(root.right) return self.left_rotate(root) return root

In [11]:

avl = AVLTree()

avl = AVLTree()

In [12]:

root = None
root = avl.insert_node(root, 14)
root = avl.insert_node(root, 17)
root = avl.insert_node(root, 11)
root = avl.insert_node(root, 7)
root = avl.insert_node(root, 53)
root = avl.insert_node(root, 4)
root = avl.insert_node(root, 13)
root = avl.insert_node(root, 12)
root = avl.insert_node(root, 8)
root = avl.insert_node(root, 60)
root = avl.insert_node(root, 19)
root = avl.insert_node(root, 16)
root = avl.insert_node(root, 20)

root = None root = avl.insert_node(root, 14) root = avl.insert_node(root, 17) root = avl.insert_node(root, 11) root = avl.insert_node(root, 7) root = avl.insert_node(root, 53) root = avl.insert_node(root, 4) root = avl.insert_node(root, 13) root = avl.insert_node(root, 12) root = avl.insert_node(root, 8) root = avl.insert_node(root, 60) root = avl.insert_node(root, 19) root = avl.insert_node(root, 16) root = avl.insert_node(root, 20)

In [13]:

tt.traverse_inorder(root)

tt.traverse_inorder(root)

4
7
8
11
12
13
14
16
17
19
20
53
60

In [15]:

root = avl.delete_node(root, key=16)

root = avl.delete_node(root, key=16)

In [16]:

tt.traverse_inorder(root)

tt.traverse_inorder(root)

4
7
8
11
12
13
14
17
19
20
53
60

In [ ]: