Ray's Blog

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:

Red Black Tree: Reference for Red Black Tree.
AVL Tree: Reference for AVL Tree

Comparison

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.

Ray's Blog

Other articles

Interval Trees and Segment Trees

Other articles

links

social