1. An in-order traversal of a binary search tree produces a list of keys in ascending order. Which traversal produces a list of keys in descending order?

   ---

   An in-order traversal produces a ascending list of keys if it visits the left child before the right child. Visiting the right child before the left child would produce a descending list of keys.

   ---

2. Given an arbitrary binary tree T with n nodes, describe an algorithm to transform T into a right-linear tree using at most n right rotations.

   ---

   Given a binary tree T, call the sequence of right children starting from the root the right spine of T. If the root exists, it will always be a part of the right spine. If a node n in the right spine contains a left child c, performing a right rotation on n brings c into the spine as n's parent; note that, after rotation, c's right child becomes n's left child.

   The algorithm to form a right-linear tree follows from the previous paragraph:

   make-rlt(r)
     do r != nil
       do r->left != nil
         r <- right-rotate(r)
       od
       r <- r->right
     od
   

   The function right-rotate(r) rotates the node r so r's left child becomes r's parent and returns a pointer to the new parent.

   Each right rotation of a node on the right spine brings a new node into the spine (assuming the node rotated has a left child, a condition for which right-rotate() checks), and once in the right spine, a node remains there. Because T has n nodes, and because T is connected, at most n right rotations need to be performed before all nodes in T are in the right spine. In fact, at most n - r right rotations are needed when r nodes are already in the right spine of T; because the root is always in the right spine, r >= 1.

   ---

3. A colleague of yours is using a B-tree to store n keys. Because the measured performance for searching the B-tree is O(n), your colleague comes to your for help in improving search performance. Explain what you expect the likely problem to be, and what kinds of changes would you recommend to your colleague to improve search performance. You may ignore the cost of accessing B-tree nodes in your analysis.

   ---

   It seems most likely that your colleague is using a B-tree in which the degree t is larger than n, the number of keys being stored in the tree. The search for any particular key becomes a linear search through the keys stored in the root of the B-tree, giving O(n) search performance.

   Two immediate recommendations for improving search performance come to mind. First, change the B-tree search algorithm to use a binary search instead of a linear search when looking through a node's keys for a match. The second recommendation would be to use a B-tree with a degree t smaller than n, preferably much smaller than n.

   ---

4. Starting from an empty B-tree, what is the longest sequence of insertions possible before the first node split occurs. The shortest? What is the longest sequence of insertions before the second node split occurs? The shortest? Explain your answers.

   ---

   Starting from an empty B-tree, the first node to be split would be the root, which will be split when it contains 2t - 1 keys; the next key to be inserted will split the root. Because nodes are only split when they contain 2t - 1 keys, the shortest sequence of insertions before the first node splits also contains 2t - 1 insertions.

   Once the root is split, the B-tree contains two leaf nodes, each of which contains t - 1 keys. Keys are always inserted into leaves, so t keys can be inserted into each leaf before one of the two leaves gets split by the next key. On the other hand, once a leaf contains 2t - 1 keys, the next key inserted into that leaf will split it, so the shortest sequence of insertions before the second split would be t.

   ---

This page last modified on 23 February 2000.