Question 3226 – Teaching Aptitude
November 15, 2023Artificial-Intelligence
November 15, 2023NTA UGC NET JUNE-2023 Paper-2
| Question 18 |
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
| Both A and R are correct and R is the correct explanation of A | |
| Both A and R are correct and R is the NOT correct explanation of A
| |
| A is true but R is false
| |
| A is false but R is true
|
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.
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.