AVL Trees

Data Structures and Algorithms with Python is a course that provides an in-depth look at the different types of data structures and algorithms used in programming. One of the key data structures covered in this course is the AVL Tree. An AVL tree is a self-balancing binary search tree, which means that it is a type of tree that is used to store data in an organized and efficient manner. In this article, we will discuss the time and space complexity of AVL trees, as well as provide examples of Python code to help illustrate the concepts. We will also provide five coding exercises with solutions at the end of the article to help test the reader’s understanding of the material.

What is an AVL Tree?

An AVL tree is a self-balancing binary search tree. This means that it is a type of tree that is used to store data in an organized and efficient manner. It is named after its inventors, Adelson-Velskii and Landis, who first published their algorithm in 1962. An AVL tree is similar to a regular binary search tree, but it has a few additional features that make it more efficient.

The most important feature of an AVL tree is that it is self-balancing. This means that when new data is inserted or deleted from the tree, it will automatically balance itself to ensure that the tree remains as balanced and efficient as possible. This is done by comparing the heights of the left and right subtrees of each node in the tree and ensuring that the difference between them is not greater than one. If it is, then the tree is rebalanced to restore the balance.

How does AVL Trees Work?

In an AVL tree, each node stores a key and the associated data. Each node also has a balance factor, which is the difference between the heights of the left and right subtrees. The balance factor can be either -1, 0, or 1. If the balance factor is negative, the node is considered left-heavy; if it is positive, the node is considered right-heavy; and if it is 0, the node is balanced.

The AVL tree works by maintaining the balance factor of each node. When a node is inserted or deleted, the balance factor of the node and its children is recalculated. If the balance factor of any node is greater than 1 (right-heavy) or less than -1 (left-heavy), the tree is considered unbalanced and needs to be rebalanced.

To rebalance the tree, the AVL tree rotates the subtrees around the node with the unbalanced balance factor. This ensures that the balance factor of each node is always between -1 and 1.

AVL trees are used in a variety of applications, including databases, file systems, and search engines. They are a popular choice for data structures because they can provide quick access to data and can quickly be rebalanced when needed.

Time Complexity

Now that we have discussed what an AVL tree is, let’s look at the time complexity of access, search, insertion, and deletion in an AVL tree.

Access

Accessing an element in an AVL tree has an average time complexity of O(log n) and a worst-case time complexity of O(n). This is because the tree is self-balancing and it takes time to traverse the tree in order to find the desired element.

Search

Searching for an element in an AVL tree has an average time complexity of O(log n) and a worst-case time complexity of O(n). This is because the tree is self-balancing and it takes time to traverse the tree in order to find the desired element.

Insertion

Inserting an element into an AVL tree has an average time complexity of O(log n) and a worst-case time complexity of O(n). This is because the tree is self-balancing and it takes time to traverse the tree in order to find the correct position for the new element.

Deletion

Deleting an element from an AVL tree has an average time complexity of O(log n) and a worst-case time complexity of O(n). This is because the tree is self-balancing and it takes time to traverse the tree in order to find the desired element and then delete it.

Space Complexity

The space complexity of an AVL tree is O(n), which means that it requires O(n) memory to store all the elements in the tree. This is because each node in the tree requires a certain amount of memory in order to store the data and the pointers to its left and right subtrees.

Examples of Python Code

Now that we have discussed the time and space complexity of AVL trees, let’s look at some examples of Python code to help illustrate these concepts.

Inserting an Element

The following code shows how to insert an element into an AVL tree.

def insert(self, key): 
  self.root = self._insert_helper(self.root, key)

def _insert_helper(self, root, key): 
  if root is None: 
    return Node(key) 

  if key < root.data: 
    root.left = self._insert_helper(root.left, key) 
  else: 
    root.right = self._insert_helper(root.right, key) 

  root.height = 1 + max(self.get_height(root.left), 
                        self.get_height(root.right)) 

  balance = self.get_balance(root) 

  # Case 1: Left Left 
  if balance > 1 and key < root.left.data: 
    return self._right_rotate(root) 

  # Case 2: Right Right 
  if balance < -1 and key > root.right.data: 
    return self._left_rotate(root) 

  # Case 3: Left Right 
  if balance > 1 and key > root.left.data: 
    root.left = self._left_rotate(root.left) 
    return self._right_rotate(root) 

  # Case 4: Right Left 
  if balance < -1 and key < root.right.data: 
    root.right = self._right_rotate(root.right) 
    return self._left_rotate(root) 

  return root 

Deleting an Element

The following code shows how to delete an element from an AVL tree.

def delete(self, key): 
  self.root = self._delete_helper(self.root, key)

def _delete_helper(self, root, key): 
  if root is None: 
    return root 

  if key < root.data: 
    root.left = self._delete_helper(root.left, key) 
  elif key > root.data: 
    root.right = self._delete_helper(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 

    temp = self.get_min_value_node(root.right) 
    root.data = temp.data 
    root.right = self._delete_helper(root.right, temp.data) 

  if root is None: 
    return root 

  root.height = 1 + max(self.get_height(root.left), 
                      self.get_height(root.right)) 

  balance = self.get_balance(root) 

  # Case 1: Left Left 
  if balance > 1 and self.get_balance(root.left) >= 0: 
    return self._right_rotate(root) 

  # Case 2: Right Right 
  if balance < -1 and self.get_balance(root.right) <= 0: 
    return self._left_rotate(root) 

  # Case 3: Left Right 
  if balance > 1 and self.get_balance(root.left) < 0: 
    root.left = self._left_rotate(root.left) 
    return self._right_rotate(root) 

  # Case 4: Right Left 
  if balance < -1 and self.get_balance(root.right) > 0: 
    root.right = self._right_rotate(root.right) 
    return self._left_rotate(root) 

  return root 

Conclusion

In conclusion, an AVL tree is a self-balancing binary search tree that is used to store data in an organized and efficient manner. It has an average time complexity of O(log n) for access, search, insertion, and deletion, and a worst-case time complexity of O(n). It also has a space complexity of O(n). We have provided examples of Python code to help illustrate the concepts discussed in this article. Finally, we have provided five coding exercises with solutions at the end of the article to help test the reader’s understanding of the material.

Exercises

def insert(self, key): 
  self.root = self._insert_helper(self.root, key)

def _insert_helper(self, root, key): 
  if root is None: 
    return Node(key) 

  if key < root.data: 
    root.left = self._insert_helper(root.left, key) 
  else: 
    root.right = self._insert_helper(root.right, key) 

  root.height = 1 + max(self.get_height(root.left), 
                        self.get_height(root.right)) 

  balance = self.get_balance(root) 

  # Case 1: Left Left 
  if balance > 1 and key < root.left.data: 
    return self._right_rotate(root) 

  # Case 2: Right Right 
  if balance < -1 and key > root.right.data: 
    return self._left_rotate(root) 

  # Case 3: Left Right 
  if balance > 1 and key > root.left.data: 
    root.left = self._left_rotate(root.left) 
    return self._right_rotate(root) 

  # Case 4: Right Left 
  if balance < -1 and key < root.right.data: 
    root.right = self._right_rotate(root.right) 
    return self._left_rotate(root) 

  return root 

def delete(self, key): 
  self.root = self._delete_helper(self.root, key)

def _delete_helper(self, root, key): 
  if root is None: 
    return root 

  if key < root.data: 
    root.left = self._delete_helper(root.left, key) 
  elif key > root.data: 
    root.right = self._delete_helper(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 

    temp = self.get_min_value_node(root.right) 
    root.data = temp.data 
    root.right = self._delete_helper(root.right, temp.data) 

  if root is None: 
    return root 

  root.height = 1 + max(self.get_height(root.left), 
                      self.get_height(root.right)) 

  balance = self.get_balance(root) 

  # Case 1: Left Left 
  if balance > 1 and self.get_balance(root.left) >= 0: 
    return self._right_rotate(root) 

  # Case 2: Right Right 
  if balance < -1 and self.get_balance(root.right) <= 0: 
    return self._left_rotate(root) 

  # Case 3: Left Right 
  if balance > 1 and self.get_balance(root.left) < 0: 
    root.left = self._left_rotate(root.left) 
    return self._right_rotate(root) 

  # Case 4: Right Left 
  if balance < -1 and self.get_balance(root.right) > 0: 
    root.right = self._right_rotate(root.right) 
    return self._left_rotate(root) 

  return root 

def search(self, key):
  return self._search_helper(self.root, key)

def _search_helper(self, root, key):
  if root is None or root.data == key:
    return root

  if key < root.data:
    return self._search_helper(root.left, key)
  else:
    return self._search_helper(root.right, key)

def access(self, key):
  return self._access_helper(self.root, key)

def _access_helper(self, root, key):
  if root is None or root.data == key:
    return root.data

  if key < root.data:
    return self._access_helper(root.left, key)
  else:
    return self._access_helper(root.right, key)

def get_height(self, root): 
  if root is None: 
    return -1 

  return root.height