Balanced Trees

Balanced trees are wildly used but rarely asked during the job interview due to the complexity to implement them. However we still need to have a basic understanding of them.

Two most popular balanced trees are:


From the above reference:

The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree.