Midterm review: sorting, trees, BST, AVL, heap

Midterm week. This page does not teach a new topic; it collects the first eight weeks in one place. First look at the summary table, then read the “how to solve it in the exam” pattern for each topic, and finally solve the questions with pen and paper. Do not open the answer to a question before working out your own trace.

The question types you will meet in the midterm are almost fixed:

1. Big-O: best, average and worst time for a structure or algorithm.
2. Tracing: “insert in this order, draw the tree/array”.
3. Writing a method: recursive tree methods: height, leaf count, sum, search.

The big table

Sorting: what to remember

The lower bound. An algorithm that only makes comparisons is a decision tree. Each of the $n!$ different orderings must end in a separate leaf. Since a binary tree of height h has at most $2^h$ leaves:

$h \ge \lceil \log_2 n! \rceil = \Omega(n \log n)$

n   n!      minimum comparisons
3   6       3
4   24      5
5   120     7
6   720     10
8   40320   16

Why do counting and radix get past this bound? Because they make no comparisons. They use the value itself as an array index. The price: the values must be small integers (or fixed-length keys).

An LSD radix trace. In each pass, distribute stably (stable) by one digit and collect the buckets in order:

start      512  34 208  71 645  93 160
ones       160  71 512  93  34 645 208
tens       208 512  34 645 160  71  93
hundreds    34  71  93 160 208 512 645

PITFALL · stability in radix. In the tens pass 208 and 512 go to different buckets, but numbers that fall in the same bucket must keep the order of the previous pass. If you break stability, the work of the previous pass is lost.

Trees and traversals

You should be able to solve this tree from memory:

        A
       / \
      B   C
     / \   \
    D   E   F
       /
      G

preorder   A B D E G C F    (root, left, right)
inorder    D B G E A C F    (left, root, right)
postorder  D G E B F C A    (left, right, root)
level      A B C D E F G    (with a queue)
height 3, leaf count 3 (D, G, F)

Building a tree from preorder + inorder. The first element of the preorder is the root. Find the root in the inorder: what is to its left is the left subtree, and what is to its right is the right subtree. The next element in the preorder is the root of the left subtree. Continue recursively.

pre: 5 9 1 3 7 2 8     in: 1 9 7 3 5 2 8

root 5: in -> [1 9 7 3] 5 [2 8]
left root 9: in -> [1] 9 [7 3]
  right of 9, root 3: in -> [7] 3
right root 2: in -> 2 [8]

          5
        /   \
       9     2
      / \     \
     1   3     8
        /
       7
post: 1 7 3 9 8 2 5

With only preorder + postorder the tree is not unique (it is unknown whether the child of a single-child node is on the left or the right). The inorder is required.

BST: insertion and deletion

Insert 45, 20, 60, 10, 30, 50, 70, 25, 35:

           45
         /    \
       20      60
      /  \    /  \
    10    30 50   70
         /  \
        25   35

The three cases of deletion: if it is a leaf, delete it directly. If there is one child, link the child to the parent. If there are two children, replace its value with the inorder successor (the leftmost of the right subtree), then delete the successor from the right subtree (it has at most one child).

Delete 20: the successor is 25.

           45
         /    \
       25      60
      /  \    /  \
    10    30 50   70
            \
             35

Preorder: 45 25 10 30 35 60 50 70. If you then delete 45, the successor is 50: 50 25 10 30 35 60 70.

AVL: choosing the rotation

Going up the insertion path from the bottom, the first node whose BF is +2 or -2 is the rotation point. Choose the case by looking from there, according to which grandchild the insertion was made in:

Insert 40, 20, 60, 10, 30, then insert 25:

before (25 inserted)       after (LR at 40)
       40                        30
      /  \                     /    \
    20    60                 20      40
   /  \                     /  \       \
  10   30                  10   25      60
      /
    25

The BF of 40 is 2 - 0 = 2, and the insertion went to the right of the left child (20): LR. The median value (30) moves up.

Heap: buildHeap and heapsort

buildHeap sinks every node from the last internal node of the array (n/2) toward the root. Most nodes are on the lower levels and sink only a little; the total work is $O(n)$.

[9, 4, 7, 1, 8, 2, 6]   n=7, i=3..1
i=3  7 <-> 2           [9, 4, 2, 1, 8, 7, 6]
i=2  4 <-> 1           [9, 1, 2, 4, 8, 7, 6]
i=1  9 -> 1 -> 4       [1, 4, 2, 9, 8, 7, 6]

Heapsort builds a max-heap for ascending order (0-indexed: children 2i+1, 2i+2). Then at each step it places the root (the largest) at the end of the active part of the array and shrinks the heap by one.

[3, 8, 5, 1, 9, 6]
buildHeap   [9, 8, 6, 1, 3, 5]
step 1      [8, 5, 6, 1, 3 | 9]
step 2      [6, 5, 3, 1 | 8, 9]
step 3      [5, 1, 3 | 6, 8, 9]
step 4      [3, 1 | 5, 6, 8, 9]
step 5      [1 | 3, 5, 6, 8, 9]

For priority queues and java.util.PriorityQueue, see the other page of this week.

Common mistakes

        A
       / \
      B   C
     / \   \
    D   E   F
       /
      G

static int height(Node t) {
    if (t == null) return -1;
    return 1 + Math.max(height(t.left), height(t.right));
}