Page 68 - Data Structures Interactive Book

7.8 Exercise

Essay Questions

1. Define a binary search tree (BST) and explain its ordering property.
2. Write a program to insert and delete nodes in a BST.

3. Explain the three cases of deletion in a BST with examples.

4. Describe how AVL trees maintain balance and why rotations are necessary.

5. Discuss the role of B-trees in database indexing and file systems.

6. Construct an expression tree for ( + ) × ( − )and explain its evaluation.
7. Compare the efficiency of binary trees, AVL trees, and B-trees in terms of height

and performance.

Multiple Choice Questions (MCQ)
Q1. What is the property of a Binary Search Tree (BST)?

a) All nodes have equal values b) Left child < Parent < Right child

c) Parent < Left child < Right child d) Nodes are stored in random order

Q2. Which of the following is NOT a valid case of deletion in a BST?

a) Deleting a leaf node b) Deleting a node with one child
c) Deleting a node with two children

d) Deleting the root only when it has no children

Q3. What is the main purpose of rotations in AVL trees?
a) To increase the height of the tree b) To maintain balance and reduce height

c) To delete nodes faster d) To convert the tree into a linked list

Q4. Which of the following is TRUE about B-trees?

a) They are used mainly in recursion

b) They are efficient for database indexing and file systems
c) They cannot store multiple keys in a node

d) They are always binary trees

Q5. What is the height complexity of an AVL tree compared to a normal BST?
a) AVL trees always have greater height

b) AVL trees maintain logarithmic height (log )

c) AVL trees have linear height ( )

d) AVL trees cannot guarantee balanced height

68