Balanced Trees and AVL Questions and Answers

Answer: C

Both (i) and (ii) are correct.

In a B tree, keys and their data (or record pointers) are stored in internal nodes as well as leaves. In a B⁺ tree, internal nodes hold only keys to guide the search, and all data lives in the leaves (i).

The leaves of a B⁺ tree are also linked together in key order, so after reaching the left-most leaf one can scan sequentially to the right-most, which makes range queries efficient (ii). So neither statement alone is the full picture.

Answer: C

An AVL tree is used to avoid formation of skew trees.

An ordinary binary search tree can become skewed, degenerating into a linked list when keys arrive in sorted order, so search takes O(n) time. An AVL tree keeps the balance factor (height of left subtree minus height of right) of every node at -1, 0 or +1, restoring it with rotations after each insertion or deletion, so its height stays O(log n).

It does not save memory (each node stores extra balance information), does not speed up memory access itself, and does not simplify storage, since rotations make insertion more complex.

Answer: A

B⁺ trees are balanced because the lengths of the paths from the root to all leaf nodes are all equal.

A B⁺ tree grows and shrinks only at the root: inserts split nodes upwards and deletes merge them, so all leaves always stay at the same depth. That guarantees every search, from root to leaf, takes the same number of steps, logarithmic in the number of keys.

Paths differing by at most 1 is the AVL tree's notion of balance, not the B⁺ tree's. B⁺ tree nodes only need to be at least half full, so sibling nodes can differ in their number of children or records by more than 1.

Answer: C

A B-tree of order m has at most m children per node.

In the usual (Knuth) definition, the order is the maximum number of children. Each node then holds at most m - 1 keys, and every internal node other than the root has at least \(\lceil m/2 \rceil\) children.

m - 1 is the maximum number of keys, not children. m + 1 and 2m exceed the definition, though 2m appears in the older convention in which 'order' means the minimum degree.

Answer: B

The operation that benefits most is successor lookup.

In a B+ tree all keys sit in the leaves, and the leaves are chained by pointers in key order. Once a key has been found, its successor (the next larger key) is either next in the same leaf or the first key of the next leaf, reached in one step through the link instead of a new walk from the root. That is why range scans and ordered traversal are fast in B+ trees.

An exact key search still goes from the root to a leaf, so the links do not help it. Parent node splitting and structural rebalancing are insertion and deletion mechanics on the internal levels and do not use the leaf chain.

Answer: B

The reason is that internal nodes store only keys, allowing higher fan-out.

In a B-tree, every node holds keys together with their records or record pointers. In a B+ tree, the internal nodes hold only keys and child pointers, and all data lives in the leaves. A disk block of fixed size can therefore hold many more entries in a B+ tree internal node, so each node has more children, and a tree with a higher fan-out reaches the same number of keys in fewer levels.

B+ trees do not use hashing. Sequentially linked leaves speed up range scans but do not reduce height. Whether duplicates are allowed has no effect on the height.

Answer: B

Minimal disk accesses come from a large fan-out (order).

A B-tree node is usually sized to fill one disk block, and each node visited costs one disk access. A search reads one node per level, so the number of accesses equals the tree's height. Giving each node a large order, hundreds of keys and children per block, makes the tree very shallow: a B-tree of order 200 can index millions of keys in three or four levels.

Low height is the result of the large fan-out, not a separate mechanism. Root splitting is simply how a B-tree grows by one level, and B-tree nodes are fixed-size blocks, not variable-sized.

Answer: C

In a B+ tree, actual data is stored in the leaf nodes.

A B+ tree keeps all records, or pointers to them, in its leaves, and links the leaves together in key order. The internal nodes hold only copies of keys to guide the search, so every search ends at a leaf, and a range of keys can be read by walking along the leaf chain.

This is the main difference from a B-tree, where data can sit in any node. The root, internal and parent nodes of a B+ tree are all index levels that hold keys and child pointers only.

Answer: C

The maximum height is 3.

The tallest AVL tree with a given number of nodes is the sparsest one, in which the two subtrees of every node differ in height by exactly one. The minimum number of nodes \(N(h)\) in an AVL tree of height \(h\) is

\[ \begin{aligned} N(h) &= N(h-1) + N(h-2) + 1 \\ N(0) = 1,\ N(1) &= 2,\ N(2) = 4 \\ N(3) &= 7,\ N(4) = 12 \end{aligned} \]

A height of 4 needs at least 12 nodes, so 7 nodes can reach height 3 but not 4. Heights 4 and 5 are impossible with 7 nodes, and 2 is not the maximum.