Interview Questions and Answers :: HCL Technologies
Home > Experience Archives > HCL Technologies > Interview Question Set 6 > Discussion
3. Which is efficient in respect to searching AVL tree or RED BLACK tree.
Answer:
RB-Trees are, as well as AVL trees, self-balancing. Both of them provide O(log n) lookup and insertion performance.
In respect to searching AVL tree is efficient then Red-Black Tree because they are more rigidly balanced.. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2), while in red black trees it's at most ~2 lg (n+1).
But if your application required frequent insertions and deletions, then Red Black trees should be preferred over AVL tree.
Balaji.M
30 Nov, 2016 1:14 PM
RB-Trees are, as well as AVL trees, self-balancing. Both of them provide O(log n) lookup and insertion performance.
In respect to searching AVL tree is efficient then Red-Black Tree because they are more rigidly balanced.. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2), while in red black trees it's at most ~2 lg (n+1).
But if your application required frequent insertions and deletions, then Red Black trees should be preferred over AVL tree.
In respect to searching AVL tree is efficient then Red-Black Tree because they are more rigidly balanced.. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2), while in red black trees it's at most ~2 lg (n+1).
But if your application required frequent insertions and deletions, then Red Black trees should be preferred over AVL tree.
Report Error
Report Error
Please Login First Click Here