Description
1. True or False:
(a) BST operations (search, predecessor, successor, minimum, insert, delete) are O(h), where h is height
of the tree.
(b) The height of a binary search tree with n elements is Θ(log(n)).
(c) In-order tree walk of a binary search tree outputs an unsorted sequence.
(d) When deleting node z with 2 children, we cannot replace z by its predecessor.
(e) In an AVL tree, the right subtree and the left subtree of any node have the same height.
(f) Worst-case tree height for AVL tree with n nodes is Θ(log(n)).
2. Build an AVL Tree out of the BST according to the rotation operations in the lecture with one rotation
operation. The pre-order traversal sequence of the BST is {10, 5, 3, 7, 6, 9, 8, 13, 11, 14}. First draw the
BST, then do the rotation. Also answer the type of this rotation (Single or Double).
3. Build an AVL tree step by step. The keys are inserted in the order of:{31, 20, 12, 26, 28, 27}.
Please draw the tree after each key is inserted, and mark the type of rotation taken, if any, at each step.
4. (Radix trees) Given two strings, a = a0a1a2 . . . ap and b = b0b1b2 . . . bq, where each ai and each bj
belongs to some ordered set of characters, we say that string a is lexicographically less than string b if
either
i there exists an integer j, where 0 ≤ j ≤ min{p, q}, such that ai = bi for all i = 0, 1, . . . , j − 1 and
aj < bj , or
ii p < q and ai = bi for all i = 0, 1, 2, . . . p.
For example, if a and b are bit strings, we can verify that 10100 < 10110 and 10100 < 101000 following
the above rules. This ordering is similar to that used in English-language dictionaries.
The radix tree data structure shown in Figure 12.5 (a.k.a. trie) stores the bit strings 1011, 10, 011, 100
and 0. When searching for a key a = a0a1a2 . . . ap, go left at a node of depth i if ai = 0 and right if
ai = 1.
(a) Let S be a set of distinct bit strings whose lengths sum to n. Show how to use a radix tree to sort
S lexicographically in Θ(n) time.
(b) Now consider that the ordered set of characters have a size of k > 2 (for lower-case alphabetic
letters, k = 26). Let S be a set of distinct strings whose lengths sum to n. Will lexicographically
sorting still cost Θ(n) time? Why, or why not?
