AVL Tree

Preview

1. What is an AVL tree and how does it differ from a regular binary search tree?
2. Why is it important for an AVL tree to maintain a balance factor of -1, 0, or 1?
3. How is the balance factor of an AVL tree calculated and how does it affect tree operations?
4. Can an AVL tree be constructed recursively or iteratively? Which is preferred and why?
5. How does an AVL tree perform in terms of time complexity for search, insertion, and deletion compared to other tree structures such as a red-black tree or a B-tree?

Explain

An AVL tree is a balanced binary search tree where the height of the left and right sub-tree of every node differs by at most one. It was named after the inventors Adelson-Velsky and Landis.

When a node is inserted or deleted from an AVL tree, the tree is rebalanced by performing rotations. A rotation is a tree operation that preserves the BST property and balances the height of the tree.

Here’s an example of an AVL tree:

     10
   /    \
  6      15
 / \     /
4   8  12
      /  \
     11  14

This tree is balanced because the height of the left sub-tree is 2 and the height of the right sub-tree is 3, which differs by at most 1.

If a new node is inserted with value 7, the tree would be rebalanced by performing a left rotation at node 6:

     10
   /    \
  8      15
 / \     /
6   9  12

/
4 7

8

After the rotation, the tree is still balanced with the height of the left sub-tree at 2 and the height of the right sub-tree at 3.

Keypoint

1. An AVL tree is a type of self-balancing binary search tree.
2. It maintains a balance factor which determines if a subtree is balanced or not.
3. The balance factor is calculated by subtracting the height of the right subtree from the height of the left subtree.
4. The AVL tree performs rotations (left rotation and right rotation) to balance the tree.
5. A left rotation is performed when the balance factor is greater than 1 on the right of a node.
6. A right rotation is performed when the balance factor is less than -1 on the left of a node.
7. The time complexity of AVL tree operations like insertion, deletion, and search is O(logn) on average and worst case.

Review

1. What is an AVL tree?
   Answer: AVL tree is a self-balancing binary search tree that maintains the balance factor between -1 to +1 in each node.

2. How does AVL tree maintain its balance?
   Answer: AVL tree maintains its balance by performing rotation operations when the balance factor is greater than 1 or less than -1 in any node.

3. What is the time complexity of inserting a node in AVL tree?
   Answer: The time complexity of inserting a node in an AVL tree is O(log n), where n is the total number of nodes in the tree.

4. Can two AVL trees have the same set of elements but different structures?
   Answer: Yes, two AVL trees can have the same set of elements but different structures.

5. What is the height of an AVL tree with n nodes?
   Answer: The height of an AVL tree with n nodes is O(log n).