Data structure and Algorithms(QUIZ 2)

A Binary Tree is defined as a tree in which each node has:

• At least two children

• At most two children

• Exactly two children

• No children

Insertion in a Binary Search Tree (BST) always places the new key:

• At the root

• In the leftmost leaf

• According to the BST property

• At the rightmost leaf

In BST deletion, deleting a node with two children uses which replacement?

• Replace with inorder successor or predecessor

• Replace with parent

• Replace with root

• Replace with first leaf

The height of a BST becomes greater than O(log n) when:

• Keys are inserted randomly

• Keys follow sorted order

• Keys follow reverse order

• Both B and C

Height balance in AVL trees ensures height O(log n) because:

• Every subtree has exactly two children

• Balance factor is always 0

• Height difference between subtrees is at most 1

• Rotations occur after every insertion

AVL rotations restore balance by:

• Rebuilding the entire tree

• Adjusting structure locally around imbalance

• Swapping node values

• Deleting nodes

A Red-Black Tree ensures balance using:

• Heights of subtrees

• Colors and structural properties

• Level-order rotation

• Strict height difference of 1

Which of the following is NOT a property of Red-Black Trees?

• Root is always black

• Every path from root to leaf has same number of black nodes

• No two red nodes appear consecutively

• All leaves are non-null nodes

A Splay Tree performs splaying to:

• Move the accessed node to the root

• Delete the last inserted node

• Reduce height strictly

• Remove duplicate nodes

The major advantage of Splay Trees is:

• Worst-case time is constant

• They strongly enforce height balance

• Frequently accessed elements become faster to access

• They need no rotations