What is the time complexity of avl tree?

Best case O(log n). Average case O(log n). Worst case O(log n). Space complexity is O(n). Balance factors are held in {−1, 0, +1}, which bounds the height.

AVL tree

hard

One number per node - the balance factor - decides everything. Feed it sorted keys and watch it rotate after almost every insert, keeping the height under 1.44 log n forever.

Best O(log n)Average O(log n)Worst O(log n)Space O(n)

Loading the avl tree engine…

Where to go next

Binary search tree

medium

Insert, search and the three cases of deletion.

Binary heap

medium

An array pretending to be a tree.

Segment tree

hard

Range queries and point updates, both O(log n).