A binary tree is Balanced if height of the tree is O(Log n) where n is number of nodes.

Balanced Binary Search trees are performance wise good as they provide O(log n) time for search, insert and delete.

binary tree is balanced if, for every vertex, the number of vertices in its left and right subtrees differs by at most one.

Examples:

  • AVL Tree
  • Red-Black trees

 

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)