Consider a B-tree of height h and minimum degree t ≥ 2 that contains n keys, n ≥ 1. Which of the following is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. h ≤ logt((n + 1)/2)
Explanation
The minimum key count is n ≥ 1 + 2(t − 1)(1 + t + … + th−1) = 2th − 1, so h ≤ logt((n + 1)/2).More Data Structures and Algorithms questions
- Which algorithm design approach is used in the quick sort algorithm?
- Consider a hash table of size 11 that uses open addressing with linear probing, with h(k) = k mod 11. Records with keys 43, 36, 92, 87, 11,…
- Consider the traversals of a tree: Preorder → ABCEIFJDGHKL Inorder → EICFJBGDKHLA Which of the following is the correct postorder traversal?
- How many rotations are required during the construction of an AVL tree if the following elements are inserted in the given sequence? 35, 50…
- Consider the following undirected graph with vertices a, b, c, f, g, h and edges: a–b, a–c, a–f, b–c, b–f, b–h, c–g, f–g, f–h, g–h The foll…
- Consider the following algorithms and their running times. Which one of the following is correct?List I List II A. Breadth-first search I.…