Question 3226 – Teaching Aptitude
November 15, 2023Question 7707 – Artificial-Intelligence
November 15, 2023Question 17093 – NTA UGC NET JUNE-2023 Paper-2
Given below are two statements: one is labeled as Assertion A and the other is labeled as Reason R
Assertion A: The AVL tree are more balanced as compared to Red black trees, but they may cause more rotations during insertions and deletion
Reason R: A Red Black tree with n nodes has height that is greater than 2 log2(n+1) and the AVL tree with n nodes has height less than log∅(√5(n+2))-2 (where ∅ is golden ratio)
In the light of the above statements, choose the correct answer from the options given below
Correct Answer: C
Assertion A: This statement is correct. AVL trees are generally more balanced than Red-Black trees, which means their heights are closer to logarithmic. However, the insertion and deletion operations in AVL trees may cause more rotations compared to Red-Black trees.
Red-Black Tree Height: In a Red-Black tree, the height is guaranteed to be at most approximately 2 * log₂(n+1), where “n” is the number of nodes in the tree. It can be at most twice the height of a balanced tree, which is log₂(n+1). So, the statement correctly indicates that the height is “greater than 2 * log₂(n+1).”
AVL Tree Height: In an AVL tree, the height is guaranteed to be at most log∅(√5(n+2)) – 2, where “n” is the number of nodes in the tree. The golden ratio (∅) is approximately 1.618. So, the height of an AVL tree is less than log∅(√5(n+2)) – 2.