Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

avl
data structures

What is an AVL tree?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.

RELATED TAGS

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

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring