Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures

What is an AVL tree?

Educative Answers Team

AVL, named after inventors Adelson-Velsky and Landis, is a binary tree that​ self-balances by keeping a check on the balance factor of every node.

Balance Factor

The balance factor of a node is the difference in the heights of the left and right subtrees. The balance factor of every node in the AVL tree should be either +1, 0 or -1.

svg viewer

After each insertion or deletion, if the balance factor of any node does not follow the AVL balance property, the AVL tree balances itself through the following rotation techniques:

  • Left Rotation
  • Right Rotation
  • Left-Right Rotation
  • Right-Left Rotation

Time Complexity

Due to the balancing property, the insertion, deletion and search operations take O(logn)O(log n) in both the average and the worst cases. Therefore, AVL trees give us an edge over Binary Search Trees which have an O(n)O(n) time complexity in the worst case scenario.

Space Complexity

The space complexity of an AVL tree is O(n)O(n) in both the average and the worst case.


data structures
Copyright ©2022 Educative, Inc. All rights reserved

View all Courses

Keep Exploring