Which data structure generally provides O(log n) average search time when it is balanced and maintains its ordering property?

Options

  • A. Balanced Binary Search Tree
  • B. Stack
  • C. Queue
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Balanced Binary Search Tree

Detailed Explanation

A balanced Binary Search Tree (BST) can provide O(log n) search, insertion, and deletion in typical balanced implementations. The BST ordering rule places smaller keys in the left subtree and larger keys in the right subtree. Examples of self-balancing trees include AVL Trees and Red-Black Trees. If an ordinary BST becomes highly skewed, its height can become O(n), causing search, insertion, and deletion to degrade to O(n).
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts