Question 86
What is the worst-case time complexity of inserting a key into an AVL tree?
AVL height is O(log n), so insertion searches down a logarithmic path and performs at most a constant number of rotations to restore balance.
What is the worst-case time complexity of inserting a key into an AVL tree?
AVL height is O(log n), so insertion searches down a logarithmic path and performs at most a constant number of rotations to restore balance.
Which property of a Red-Black Tree prevents a red node from having a red child?
The red-black invariant prohibits a red node from having a red child. Together with equal black height, this constrains the tree height to O(log n).
In a B-tree of minimum degree t, what is the minimum number of keys in a non-root node?
A B-tree with minimum degree t requires every non-root node to contain at least t-1 keys and at most 2t-1 keys.
Where are actual records stored in a typical B+ tree?
B+ trees store record pointers or records at the leaves, while internal nodes primarily guide searches using separator keys. Leaf links support efficient range scans.
Which tree is used by Huffman coding to generate an optimal prefix code from symbol frequencies?
Huffman coding repeatedly combines the two least-frequent nodes to construct a binary tree. The code for each symbol is the root-to-leaf path, producing an optimal prefix code for the given frequencies.