Data Structures and Algorithms with C · Lecture Notes

Chapter 11: Search Trees

In a sorted array, binary search discards half of the remaining range at every step and finds the target in O(lg n) steps. But inserting a new element into a sorted array means shifting all the elements behind it by one cell. In a linked list, insertion is cheap, but now the middle element cannot be reached directly and search stays linear. The binary search tree combines the good sides of these two structures. Every node is larger than all the values to its left and smaller than all the values to its right, so each comparison, starting at the root, eliminates one side of the tree. Insertion and deletion change only a few pointers. These notes first define the binary search tree. They then write the insertion, search, depth, and deletion procedures in C and trace each one step by step. The last sections are about balance. We show that sorted input turns a tree into a list; the rotations of the AVL tree, which prevent this, are treated in detail, and the red-black tree and the B-tree more briefly.

Learning outcomes

Applying the definition
Check the four properties of a binary search tree on a given tree and explain why inorder traversal produces the values in sorted order.
Insertion and search
Write bst_insert and bst_search both iteratively and recursively; explain why the root pointer is passed by address when inserting into an empty tree.
Computing the depth
Write the depth function recursively, avoiding global variables, unnecessary extra parameters, and the double-evaluation trap of macros.
Deleting
Delete a node with no children, one child, or two children using a pointer to a pointer; compare the effect of four deletion methods on tree depth.
Keeping balance
Compute the cost of imbalance; recognize the LL, RR, LR, and RL cases in an AVL tree and apply single and double rotations.
Choosing a structure
Tell the binary search tree, the AVL tree, the red-black tree, and the B-tree apart by where each is used.

11.1The binary search tree

A tree is a hierarchical structure in which every node has a parent and zero or more children. The one node with no parent is the root, and the nodes with no children are leaves. In a binary tree every node has at most two children, distinguished as the left child and the right child. A node together with all the nodes below it forms a subtree. In these notes the depth of a tree is the number of nodes on the path from the root to the farthest leaf. A tree with a single node has depth 1, and the empty tree has depth 0. Three orders are used to traverse a tree. In preorder traversal the root is visited first, then the left and right subtrees. In inorder traversal the order is left subtree, root, right subtree. In postorder traversal the root comes last. These notions are known from the chapter on trees; they are repeated here only as a reminder.

11.1.1Why a new structure?

Consider a student records system. Every day it looks up records by student number thousands of times. New students enroll, and graduates leave the system. If the records are kept in an unsorted array, the whole array is scanned for a search, and the cost is O(n). If the records are kept sorted by number, binary search answers in O(lg n). But now every insertion and deletion shifts elements to keep the order, which means O(n) work. In a linked list, insertion and deletion take a few pointer changes. But one cannot jump directly to the middle of the list; binary search cannot be used, and search is again O(n).

The binary search tree carries the idea of binary search over to a linked structure. In a sorted array, binary search first looks at the middle element. If the target is smaller, it continues in the left half; if larger, in the right half. The root of a binary search tree acts like this "middle element". The left subtree takes the place of the left half and the right subtree the place of the right half. The difference is that the halves are not consecutive cells of an array but nodes linked by pointers. To insert a new element, no element is shifted; only a NULL pointer at the right place is changed to point to the new node.

11.1.2Definition and inorder traversal

Definition 11.1

A binary search tree (BST) is a binary tree that may be empty and, if it is not empty, has the following four properties:

  1. Every element has a distinct value; the values are unique.
  2. All values in a non-empty left subtree are smaller than the value at the root.
  3. All values in a non-empty right subtree are larger than the value at the root.
  4. The left and right subtrees are also binary search trees.

The fourth property makes the definition recursive: the same condition holds at every node, for the subtree rooted at that node. The word "all" in the second and third properties is important. The condition covers not only the children of a node but also the deepest elements of the subtree. Even the rightmost element at the very bottom of the root's left subtree must be smaller than the root.

The first property uses the tree like a set. The same value does not enter the tree twice. In practice the value is often the key of a record: a student number, a national ID number, or a word. The other fields of the record sit in the node together with the key. If duplicate keys must be allowed, either a counter is added to the node or equal keys are always placed on the same side by a rule (for example, to the right). In these notes the definition is followed: if an equal value arrives, no insertion is made.

The definition makes the binary search tree a subset of binary trees. Every binary search tree is a binary tree; the traversal, copy, and equality procedures written for trees apply to it as well. The converse is not true. In an ordinary binary tree the values may appear in any order. The most important consequence of the order in the definition is the following theorem.

Theorem 11.1 (Inorder traversal is sorted)

A binary tree is a binary search tree if and only if its inorder traversal lists the values in strictly increasing order.

Proof. First suppose the tree is a binary search tree, and use induction on the number of nodes. For the empty tree and the one-node tree the claim is clear. In a larger tree, inorder traversal writes the left subtree first, then the root, then the right subtree. The left and right subtrees are also binary search trees; by the induction hypothesis each is written in increasing order. All values in the left subtree are smaller than the root and all in the right subtree are larger. So when the three parts are put one after another, the sequence is increasing from beginning to end. For the converse, suppose the inorder sequence is strictly increasing. Every value of the left subtree is written before the root and every value of the right subtree after it. Since the sequence is increasing, the left values are smaller than the root and the right values larger. The values are also distinct. The inorder sequences of the subtrees are consecutive pieces of this sequence, and they are increasing too. By induction the subtrees are binary search trees as well. ∎

The theorem has a practical consequence. To sort a set of values, insert the values one by one into an empty binary search tree, then traverse the tree in inorder. This method is called tree sort. If the tree stays balanced, the total cost is O(n lg n). The theorem is useful in a second way: whether a tree is a binary search tree can be checked in O(n) time by traversing it in inorder and verifying that every value is larger than the previous one.

11.1.3Checking the definition

Figure 11.1 shows three binary trees. If each node in the left tree is compared only with its own children, no problem appears. The left child of 15 is 9 and the right child is 22, and 9 < 15 < 22. The children of 20 are 19 and 21; they are in the right places too. But 22 lies in the left subtree of the tree whose root is 18. The second property of the definition requires all values in the left subtree to be smaller than 18. 22 violates this condition; the tree is not a binary search tree. If 22 is searched for in this tree, the comparison 22 > 18 at the root sends the search to the right, and 22 is never found.

The tree in the middle looks unbalanced, but it is valid. Every value to the left of 95 (80, 50, 2) is smaller than 95; the left of 80 is 50, the left of 50 is 2, and the order is broken nowhere. The definition says nothing about the shape of the tree; it only restricts the arrangement of the values. In the tree on the right, every value to the right of the root is larger than 35. To the left of 40 stands 38, and to its right stands 39. Both are smaller than 40 and larger than 35. These values satisfy the condition of every node on the path from the root to them; the tree is valid.

1815922201921NOT a binary search tree958050297binary search tree3540383953binary search tree
Figure 11.1: Which is a binary search tree? In the left tree, 22 is larger than 15 because it is to the right of 15; but it sits in the left subtree of 18 and is larger than 18 as well, which violates the definition. The middle and right trees are valid: each value satisfies the condition of all the nodes on the path from the root to it.

The examples also show how the check should be done. Every node's value has a lower and an upper bound. The root has no bounds. When we go left from a node, the upper bound becomes the value of that node; when we go right, the lower bound does. In the left tree, 22 is reached from the root by going left and then right. The lower bound is 15 and the upper bound is 18; 22 does not fall in this range. A C implementation of this idea is given in the exercises section.

Common mistake

Checking a binary search tree by comparing each node only with its children. This check accepts the left tree in Figure 11.1 as valid. A correct check either verifies that inorder traversal is increasing or carries to each node the (lo, hi) range that comes down from the root.

11.1.4The node structure in C

Each node of the tree is represented by a struct. The node holds a data field and two pointers. One pointer points to the left child and the other to the right child. If there is no child, the value of the pointer is NULL. The definition from the slides is below.

typedef enum { FALSE, TRUE } boolean;
typedef struct node *tree_ptr;
struct node {
    tree_ptr left;
    int       data;
    tree_ptr right;
};
/* get_node(): malloc + NULL check,
sets both children to NULL */

The first line builds the logical type, which C does not have, with an enumeration (enum): FALSE gets the value 0 and TRUE gets 1. The second line defines the name tree_ptr to mean "pointer to struct node". This definition comes before the structure itself. In C it is allowed to declare a pointer to a structure that has not been defined yet; the only thing the compiler needs to know is the size of a pointer. This way a pointer to the structure's own type can be used inside the structure. Such structures are called self-referential structures.

On a 64-bit machine every pointer is 8 bytes and an int is 4 bytes. The compiler leaves a 4-byte gap after data, because right must start at an address that is a multiple of 8. For this reason sizeof(struct node) is 24 bytes; the value was verified by measuring on x86-64 with zig cc. So each node carries 20 bytes of overhead for 4 bytes of data. This is the price of the flexibility of linked structures.

The slides give the procedure get_node(), which allocates a node, only by its description: it allocates space with malloc, checks for NULL, and sets the children to NULL. An implementation that matches this description follows. All the driver programs for these notes used this procedure.

tree_ptr get_node(void) {
  tree_ptr r = malloc(sizeof *r);   /* 24 bytes */
  if (!r) {
    fprintf(stderr, "Out of memory\n");
    exit(EXIT_FAILURE);
  }
  r->left = r->right = NULL;
  return r;
}

Writing malloc(sizeof *r) takes the allocated size from the object the pointer points to rather than from the name of the type. Even if the name of the structure changes, the line stays correct. If malloc cannot find memory, it returns NULL. Writing to r->left in that case would be undefined behavior; the procedure therefore reports the error and ends the program. The two assignments in the last line are very important. malloc does not clear memory; the child pointers may hold a random address. Tree procedures recognize the end of a branch by NULL. A leaf whose children have not been cleared sends the procedures to a random place in memory.

Table 11.1 shows the memory view of a small tree with root 47, with sample addresses. The nodes of a tree do not have to sit next to each other in memory; each is in a separate place found by malloc. The shape of the tree is determined only by the addresses in the pointer fields.

Table 11.1: Memory view of a three-node tree with root 47, 26 on its left and 55 on its right. The addresses are only illustrative; each node is 24 bytes.
Addressleft (8 bytes)data (4 + 4 padding)right (8 bytes)
0x1A40 (root)0x1B10470x1A70
0x1A70NULL55NULL
0x1B10NULL26NULL

In the table the value of the root pointer L is 0x1A40. L->data gives 47, and L->left->data gives 26. 26 sits after 55 in memory, but in the tree it is to the left of 55. There is no relation between the memory order of the nodes and their place in the tree.

11.2Insertion

Insertion into a binary search tree is more restricted than insertion into a linked list. In a list a new element can go at the front, at the end, or in the middle. In a binary search tree the place of a new value is unique and is determined by the contents of the tree. This section first explains how this place is found, then how insertion order changes the shape of the tree. Then the insertion procedure is written in C and traced step by step.

11.2.1The tree decides the place

In the slides the instructor makes this point with a classroom anecdote. A student is asked to name a value. The student also points out a place: "insert it to the right of 15." The instructor says that the place is the tree's business, not the student's. Indeed the signature of the insertion procedure takes only the value to insert and the tree; it takes no position information. The procedure searches for the new value starting at the root and inserts it where the search fails. If the value is not in the tree, the search ends at a NULL pointer. That NULL is the only place where the new value can sit without breaking the definition.

Although the place is unique, the same set of values can be represented by different trees. The shape of the tree depends on the order in which the values are inserted. The question in the slides asks about this with a small example.

Example 11.1

Question. Draw binary search trees of depth 3, 4, and 5 with the values 3, 5, 7, 9, 11. Can a tree of depth 2 be drawn?

Solution. The tree of depth 5 is the easiest: insert the values in increasing order. Each new value is larger than all the previous ones and is placed to the right of the rightmost node. The result is a chain extending to the right: 3 → 5 → 7 → 9 → 11. For depth 4 the order 5, 3, 7, 9, 11 can be used: 5 is the root, 3 goes to its left and 7 to its right; 9 and 11 again extend to the right. For depth 3 the order 9, 5, 3, 7, 11 is enough. The root is 9; 5 and 11 are its children; 3 and 7 are the children of 5. In preorder this tree is 9 5 3 7 11, and in parenthesized notation it is 9(5(3, 7), 11). The inorder traversal of all three trees is the same: 3 5 7 9 11.

A tree of depth 2 cannot be drawn. A binary tree of depth 2 has a root and at most two children of it; at most 3 nodes fit in total. Five values do not fit in this tree.

953711537911357911depth 3depth 4depth 5
Figure 11.2: Three binary search trees of depth 3, 4, and 5 built with the values 3, 5, 7, 9, 11. The inorder traversal of all three is 3 5 7 9 11; only the insertion order differs.

The count in the last step of the example gives a general bound.

Theorem 11.2 (Depth and number of nodes)

A binary tree of depth k has at most 2k − 1 nodes. Accordingly, a binary tree with n nodes has depth at least ⌈lg(n + 1)⌉ and at most n.

Proof. The root is at level 1. Since every node has at most two children, level i has at most 2i−1 nodes. In a tree of depth k the levels run from 1 to k. The total is at most 1 + 2 + 4 + … + 2k−1 = 2k − 1. For n nodes to fit we need 2k − 1 ≥ n, that is, k ≥ lg(n + 1); since k is an integer, k ≥ ⌈lg(n + 1)⌉. For the upper bound it is enough that every level has at least one node: k levels need at least k nodes, so k ≤ n. ∎

For n = 5 the lower bound is ⌈lg 6⌉ = 3 and the upper bound is 5. Figure 11.2 shows these two ends and the depth in between. The meaning of the bounds is clear. In the worst case, a search in a tree looks at as many nodes as the depth. A tree whose depth is close to ⌈lg(n + 1)⌉ is as fast as binary search. A tree whose depth is close to n is no different from a linked list.

11.2.2Insertion order changes the shape of the tree

The slides insert the same nine values into two empty trees in two different orders. The values are 17, 26, 34, 47, 49, 52, 55, 84, 93. The insertion order for the left tree is 47, 55, 49, 26, 34, 17, 52, 84, 93. The right tree gets the order 26, 17, 47, 93, 84, 52, 34, 55, 49. At every step the rule is the same: start at the root, go left if the new value is smaller than the one in the node and right if it is larger, and place it at the first NULL.

In the left tree the first value, 47, becomes the root. 55 is larger and goes to its right. 49 is larger than 47, so it goes right; there it is smaller than 55, so it is placed to the left of 55. 26 and 34 settle to the left of the root; 17 takes the left of 26. 52 follows the path 47 → 55 → 49 and goes to the right of 49; 84 goes to the right of 55, and 93 to the right of 84. The longest path in the end is 47 → 55 → 49 → 52, and the depth of the tree is 4.

In the right tree the root is 26. 17 goes to its left and 47 to its right. The next, 93, goes to the right of 47; 84 to the left of 93; and 52 to the left of 84. Since each new value is added below the previous one, the tree grows downward. 34 settles to the left of 47. 55 passes along the path 26 → 47 → 93 → 84 → 52 and is placed to the right of 52, and 49 to the left of 52. The longest path is 26 → 47 → 93 → 84 → 52 → 55 and the depth is 6. Figure 11.3 shows the state after the first four insertions and the final state.

4726554947 55 49 26depth 32617479326 17 47 93depth 3 47261734554952849347 55 49 26 34 17 52 84 93depth 426174734938452495526 17 47 93 84 52 34 55 49depth 6
Figure 11.3: The same nine values are inserted into two empty trees in two different orders. Top: the first four values of each sequence have been inserted. Bottom: all values have been inserted; the depth of the left tree is 4 and that of the right tree is 6. The inorder traversal of both trees is the same: 17 26 34 47 49 52 55 84 93.

The two trees hold the same set and both satisfy the definition. By Theorem 11.1, their inorder traversals give the same sorted sequence. But their search costs differ. In the left tree the worst search looks at 4 nodes, in the right at 6. The insertion order determines the shape of the tree, and the shape determines the running time of all operations. In the words of the slides, the order in which data are inserted matters.

11.2.3Skew and balanced trees

The worst insertion order is sorted input. When 1, 2, 3, …, n are inserted in this order, every value is larger than all the previous ones, and each goes to the right of the rightmost node. The tree turns into a chain extending to the right. Data arriving in reverse order also builds a chain extending to the left. Trees whose nodes all extend in one direction are called skewed trees. The depth of a skewed tree is n, and every operation takes as long as in a linked list. Sorted data is more common in real life than one might think. Records arriving by date, student numbers given in increasing order, or a pre-sorted file are examples.

A tree whose depth stays around lg n is called a balanced tree. In a balanced binary search tree, insertion, deletion, and search take O(lg n). The problem is that balance is not maintained automatically. Two kinds of solutions have been developed for this problem.

  • Self-balancing trees rebalance the tree with local changes after every insertion and deletion. The AVL tree and the red-black tree are of this kind. The depth always stays O(lg n).
  • Trees that move frequently used nodes toward the root aim not at balance but at access speed. Each time a node is accessed, it is moved to the root by rotations. Frequently searched values thus gather near the root. This structure, called "zig-zag" in the slides, is known in the literature as the splay tree. It was proposed by D. Sleator and R. Tarjan in 1985. A single operation can be expensive, but over a long sequence of operations the average cost per operation is O(lg n).

The instructor says this on the subject: if it is very important for the tree to be balanced, algorithms that build the tree in a balanced way should be used. These algorithms are not very hard, only a little longer. The last major section of these notes treats the best known of them, the AVL tree, in detail.

11.2.4From tree to insertion order, from traversal to tree

At this point the slides ask two thought-provoking questions, marked with three question marks. The first is this: can the insertion order of the data be recovered from the picture of the tree? Is the tree formed from the incoming data unique?

The answer to the second half of the question is yes. The insertion procedure contains no randomness; when the same values arrive in the same order, the same tree is built every time. But the reverse direction is not unique. The order 2, 1, 3 builds the tree with root 2, left child 1, and right child 3. The order 2, 3, 1 builds the same tree, because 1 and 3 are not in each other's way and it does not matter which comes first. For an insertion order to build a given tree there is only one condition: every node must be inserted before its descendants. If an ancestor comes after a node among its descendants, that node settles somewhere else. Preorder always satisfies this condition, because it writes a node before all the nodes in its subtrees. So the preorder traversal of a tree is always a valid insertion order.

The second question is this: can the picture of the tree be recovered from the preorder, inorder, and postorder traversal sequences? In a general binary tree a single traversal sequence is not enough. For example, there are two trees with preorder A B: B can be the left child of A or the right child. If the inorder sequence is given together with the preorder (or postorder) sequence, the tree is determined uniquely. The first element of the preorder sequence is the root. In the inorder sequence, the elements to the left of the root form the left subtree and those to the right form the right subtree. The same step is applied recursively to the subtrees.

In a binary search tree the job is easier. The inorder sequence is already known: it is the increasing order of the values. So the preorder sequence alone (or the postorder sequence alone) is enough to determine the tree. Even more briefly, the values in preorder are inserted in that order into an empty tree, and the tree is rebuilt.

Example 11.2

Question. The preorder traversal of a binary search tree is 30 20 10 25 40 35 50. What is the tree? What is its postorder traversal?

Solution. The first value, 30, is the root. Of the remaining values, those smaller than 30 (20, 10, 25) form the left subtree and those larger (40, 35, 50) form the right subtree. They also come in this order in the preorder sequence. The root of the left subtree is 20; 10 goes to its left and 25 to its right. The root of the right subtree is 40; 35 goes to its left and 50 to its right. The tree is 30(20(10, 25), 40(35, 50)) and its depth is 3. The postorder traversal writes the left subtree first (10 25 20), then the right subtree (35 50 40), and the root last: 10 25 20 35 50 40 30. Inserting the values in the same order into an empty tree gives the same tree; the result was verified with a driver program.

In the slides the instructor adds an observation on this subject. Before, binary tree procedures could not be tried by running code, because there was no real tree in the background. Once the insertion procedure is written, this obstacle disappears. Sample trees are built in a few lines; the traversal, copy, and equality procedures are really run on these trees. All the driver programs for these notes also built their trees this way.

11.2.5The insertion procedure

The insertion algorithm rests on four observations. First, nothing can be inserted at a node that has both children; the new element goes into the empty place of a node that is missing at least one child. Second, the incoming value is searched for starting at the root. If the value in the node is larger than the new value, we move left; if smaller, right. Third, if the same value is found, no insertion is made, because the definition would be broken. Fourth, the new element is put in place of the first NULL that the search pointer meets. But when we reach NULL, the search pointer no longer points to any node. To remember the parent to which the new node will be attached, a second pointer trailing one step behind is needed. In the code this pointer is called q.

boolean bst_insert(int x, tree_ptr *L) {
  tree_ptr q = NULL, p = *L, r; // q trails p
  while (p) {                    // down to NULL
    q = p;                       // q follows p
    if (x < p->data) p = p->left;
    else if (x > p->data) p = p->right;
    else { printf("Duplicate key.\n");
           return FALSE; }
  }
  r = get_node();                   // children NULL
  r->data = x;
  if (*L == NULL) *L = r;        // empty: root
  else if (x < q->data) q->left = r;
  else q->right = r;
  return TRUE;
}

The lines of the code work as follows.

  • Line 2. Three local pointers are defined. p starts from the root of the tree; *L is the value of the caller's root pointer. q stays one step behind p and is NULL at first. r will hold the new node.
  • Lines 3–9. The loop continues until p is NULL. On each iteration the trailing pointer is first updated with q = p, and then p descends one level. If x is smaller than the value in the node, we move to the left child; if larger, to the right child. If it is neither, the values are equal: the procedure prints a warning and returns FALSE. In this case nothing in the tree changes and no memory is allocated.
  • Lines 10–11. When the loop ends, p is NULL and q points to the node that will become the parent of the new node. The new node is allocated with get_node(); its children are NULL. x is written into the data field.
  • Line 12. If the tree is empty, the loop never ran and q is still NULL. The new node becomes the root: *L = r. This assignment changes the caller's root variable.
  • Lines 13–14. If the tree is not empty, x is compared once more with the parent's value, and the new node is attached to the parent's left or right pointer.

In the loop it is known which direction p went, but this information is lost when the loop ends. The second comparison in line 13 reproduces it. It would also be possible to keep a direction variable in the loop. The code chooses brevity. Only one extra comparison is made and the cost does not change.

11.2.6Code trace: inserting 50

The slides trace the insertion of 50 into the left tree (47, 55, 49, 26, 34, 17, 52, 84, 93). Table 11.2 gives the state of the variables at each step.

Table 11.2: Trace of the call bst_insert(50, &L). The values name the nodes; "47" is written instead of "node(47)".
StepLineqpExplanation
02NULL47p is at the root; q does not point to any node yet.
14–6475550 > 47: its place is in the right subtree.
24–5554950 < 55: descend into the left subtree.
34–6495250 > 49: descend to the right.
44–552NULL50 < 52: the left of 52 is empty; the loop ends.
510–1152NULLThe new node r is allocated; r->data = 50.
61352NULLThe tree is not empty and 50 < 52: q->left = r.
715——TRUE is returned.

The four comparisons in the table correspond to the four nodes on the path from the root to 52. Before the insertion the depth of the tree is 4; 50 enters at the fifth level, below the path 47 → 55 → 49 → 52, and the depth becomes 5. The insertion changed a single pointer: the left child of 52. The rest of the tree was not touched. Figure 11.4 shows four frames of the trace.

472617345549528493px = 50 472617345549528493p,qx = 50 472617345549528493qNULLx = 50 47261734554952508493qx = 50
Figure 11.4: Four frames from the trace of bst_insert(50, &L). Left to right and top to bottom: p at the root and q NULL; p has descended to 52 and q is at 49; p has become NULL and q points to 52; the new node r has been attached to the left of 52.

If the same call had been made with 47, equality would have been found on the first iteration of the loop. The procedure would print "Duplicate key." and return FALSE. These two cases were tried in the driver program: the return value is 1 for 50 and 0 for 47. After the insertion, the preorder traversal of the tree is 47 26 17 34 55 49 52 50 84 93.

11.2.7Why tree_ptr *L?

The insertion procedure takes the tree not as tree_ptr L but as tree_ptr *L. That is, it asks for the address of the root pointer, not its value. The reason is the empty tree. If the tree is empty (*L == NULL), the inserted element becomes the root, and the caller's root variable must point to this new node. In C all parameters are passed by value. If the procedure took tree_ptr L, the assignment L = r would change only the procedure's local copy. The caller's root variable would stay NULL, and the allocated node would leak, since nothing points to it.

To let a procedure change a variable, the address of the variable is passed. This technique is called call by reference. Since the root variable is already a pointer, its address is a pointer to a pointer. The call is written bst_insert(x, &root). Inside the procedure, *L is the caller's root variable itself; *L = r writes to that variable.

There is a second solution to the same problem: the procedure gives the new root of the tree as its return value. The slides show this recursive version as well.

/* Recursive version: returns the new root */
tree_ptr insert(tree_ptr L, int x) {
  if (!L) {
    L = get_node();
    L->data = x;
  } else if (x < L->data)
    L->left = insert(L->left, x);
  else if (x > L->data)
    L->right = insert(L->right, x);
  return L;        /* root = insert(root, x); */
}

When the procedure reaches an empty subtree, it allocates the new node and returns it. At a non-empty node, it inserts into the left or right subtree according to the value. It assigns the result of the recursive call back to the corresponding child pointer. If the subtree is not empty, the recursive call returns the same pointer and the assignment changes nothing. If the subtree is empty, the recursive call returns the new node and the assignment attaches it to the tree. If the values are equal, both branches are skipped and the node is returned as it is. The usage is root = insert(root, x);. If the caller forgets to assign the return value, the first insertion into an empty tree is lost. This version has no error report either: an equal value is silently rejected. In the driver program, nine values were inserted with each of the two procedures separately; the preorder traversals of the two trees gave the same output.

The cost of the insertion procedure is the length of the path the new value descends. At each level one node is examined and a constant amount of work is done. If the depth of the tree is h, insertion takes O(h). In a balanced tree h = O(lg n), and in a skewed tree h = n. The slides write this range as Ω(lg n) – O(n). The lower bound comes from the fact that no tree can have depth smaller than ⌈lg(n + 1)⌉. For example, in a tree with all levels full, all the null pointers are below the last level; every insertion examines lg(n + 1) nodes. The iterative version uses only three pointers of extra memory, that is, O(1). The recursive version opens a call frame for each level and needs O(h) extra memory. On a skewed tree built from 2000 sorted values the iterative procedure ran without trouble. The recursive procedure makes 2000 nested calls at this depth. The default 1 MB call stack of Windows even held a chain of 30,000 nodes. But the call depth grows with n; for a long enough chain the stack overflows.

The slides have one more detail, called the "C99 fix". In the original code in the book, q is not given an initial value. When the tree is empty the loop never runs and q stays with an undefined value. The code avoids using this value through the check *L == NULL. Even so, compilers give a "may be used uninitialized" warning. The code in the slides starts with q = NULL; this removes the warning and makes the code safe.

11.3Search

Search is the reason the binary search tree exists. Insertion and deletion also start with a search: insertion looks for the place of the new value, deletion looks for the node to be deleted. This section writes search first with a loop and then with recursion. It then treats a subtle point in recursive search and search in a general, unsorted binary tree.

11.3.1Iterative search

The sought value x is first compared with the value at the root. If they are equal, the search ends. If x is smaller, the sought value, if present, is in the left subtree; by definition every value in the right subtree is larger than the root and therefore larger than x. If x is larger, the same reasoning points to the right subtree. The same step is repeated in the chosen subtree. If a NULL pointer is reached, the value is not in the tree.

tree_ptr bst_search(int x, tree_ptr L) {
  while (L) {           // pick a subtree
    if (x == L->data) return L;
    if (x < L->data) L = L->left;
    else             L = L->right;
  }
  return NULL;          // not found
}

The procedure uses the pointer L, which it receives by value, as a traveler through the tree. The loop in line 2 continues as long as L is not NULL. Line 3 checks equality and returns the address of the node found. Lines 4 and 5 move L down to the appropriate child. If the loop is left (line 7), the value is absent and NULL is returned. Changing L here does not affect the caller; the caller's root pointer stays where it is. Unlike insertion, search does not need the address to be passed, because search does not change the tree.

The address of the node is chosen as the return value. This way the caller learns both whether the value exists and gets access to the other fields in the node. When a record is searched for by key, it is usually these other fields that are really wanted.

Example 11.3

Question. In the tree before 50 is inserted (47, 55, 49, 26, 34, 17, 52, 84, 93), which nodes does bst_search(52, L) examine?

Solution. At the root 52 > 47 and L goes right, to 55. The entire left subtree (26, 17, 34) is eliminated. At 55, 52 < 55 and L goes left, to 49. 84 and 93 are never examined. At 49, 52 > 49 and L goes right, to 52. At 52 equality is found and the address of the node is returned. Four nodes were examined. In the C code, equality is checked first at each node, then less-than. At the first three nodes two checks are made, at the last one check; in all, that is seven comparison operations. In the analysis each node visit is counted as a single three-way comparison: less, equal, or greater.

472617345549528493Lsearching for x = 52comparisons: 1 472617345549528493Lsearching for x = 52comparisons: 4
Figure 11.5: The first and last frames of the trace of bst_search(52, L). Top: at the root the comparison 52 > 47 eliminates the left subtree (faded nodes). Bottom: the path has advanced along 47 → 55 → 49 → 52 and the value has been found with four comparisons; the right subtree of 55 was never examined.

Figure 11.5 shows the power of search visually: each comparison eliminates an entire subtree. If the tree is balanced, each elimination discards about half of the remaining nodes. This is the behavior of binary search in a sorted array. When a value that is not in the tree is searched for, the same path is followed. For example, if 60 is searched for, the path 47 → 55 → 84 is examined. Since the left child of 84 is NULL, the search returns NULL after three nodes.

The cost of search is the length of the path examined and is bounded by the depth h of the tree: O(h). In a balanced tree this is O(lg n), and in a skewed tree O(n). The iterative procedure uses only L as extra memory: O(1).

Next to this procedure in the slides there is an analogy by the instructor. When a manager defines a task for a clerk, he must speak very clearly; the clerk should not have to knock on the door afterwards to ask questions. The definition of a procedure is like that. The contract of bst_search is clear: it returns the address of the node if the value exists and NULL if not. It works correctly on the empty tree, does not change the tree, and does not touch a global variable. Whoever uses the procedure can use it correctly without looking inside.

11.3.2Recursive search

Since the definition is recursive, search is naturally written recursively too. In the empty tree the value is absent. If the value is found at the root, the job is done. Otherwise the same question is asked of the appropriate subtree and its answer is passed up unchanged.

tree_ptr search(int x, tree_ptr L) {
  if (!L) return NULL;          // not found
  if (x == L->data) return L;   // found
  if (x < L->data)
    return search(x, L->left);
  return search(x, L->right);
}

The first two lines are the base cases. If the tree is empty (line 2), NULL is returned; if the value is at the root (line 3), the address of the root is returned. Lines 4–6 are the recursive step. Both calls are preceded by return. Whatever the recursive call returns, this frame returns as well, and it does no other work. When the last thing a procedure does is call itself, the call is called tail recursion. Such a procedure is easily turned into a loop: the parameter is updated with its new value and control returns to the top. Iterative search is exactly this procedure obtained by that transformation. Compilers that optimize well can make this transformation themselves.

Table 11.3: Frame trace of the call search(34, L). Each row is a call frame; the last column is the value the frame returns.
FrameLComparisonWhat it doesReturns
14734 < 47return search(x, L->left)&node(34)
22634 > 26return search(x, L->right)&node(34)
33434 = 34return L&node(34)

Table 11.3 summarizes the descent and the return of the calls. Three frames go down, the bottom frame finds the node and returns its address. On the way back the frames do no computation; they pass the address they receive unchanged to the frame above. Figure 11.6 shows three moments: the middle of the descent, the moment of finding, and the moment the result reaches the root.

472617345549528493x = 34 472617345549528493x = 34returns: &node(34) 472617345549528493x = 34returns: &node(34)
Figure 11.6: Recursive search(34, L). Top: the frames for 47 and 26 wait on the stack; at 26 34 > 26, so the call goes right. Middle: 34 is found. Bottom: the address has been carried up unchanged through two frames and has reached the root.

The time cost is the same as the iterative version: O(h). The memory cost is different. Each call opens a frame, and at the deepest point h frames sit on the stack at the same time. The extra memory is O(h). In a balanced tree this is a few dozen frames and is negligible. In a skewed tree the call depth reaches n.

11.3.3A trap in recursive search

The slides show the body below, written by a student, and ask "Does this example work?"

if (L) {
  if (x == L->data) return L;
  if (x <  L->data) return search(x, L->left);
  return search(x, L->right);
}
return NULL;   /* L == NULL: empty (sub)tree */

The real question the code asks is in line 3. If x is smaller than the root, the if block in line 3 is entered and the search is made in the left subtree. Whatever the recursive call returns, the procedure returns. The search of the right subtree in line 4 is never done in this case. If the value is not found in the left subtree, NULL is returned and the procedure ends without looking right at all.

In a binary search tree this behavior is exactly what is wanted. If x is smaller than the root it cannot be in the right subtree; looking there is wasted work. The code is correct and O(h). In a general, unsorted binary tree the situation is different. x may be in the right subtree even though it is smaller than the root; this code misses it. In the driver program, 2 was searched for in a tree whose root is 5, left child 9, and right child 2. Because 2 < 5, the search went left, reached NULL at the left of 9, and answered "not found".

The return NULL in the last line also needs attention. In the original version of the slides there was a comment next to this line: "It never gets here, but whatever, let's write it anyway…". The comment was wrong and was corrected in the slides. When L is NULL, the if block is skipped and the procedure arrives exactly at this line. This happens in the last call of every unsuccessful search. If the line is deleted, the procedure ends on the empty tree without returning a value. Reaching the end of a procedure that must return a value and then using that value is undefined behavior in C. The compiler gives a warning in this case; the caller may get a random address.

The instructor has one more note on this example: when writing recursive code, sometimes work is also done after the return line, as in the example. This recalls two separate forms of recursion. In search, the result of the recursive call is passed on unchanged and no work remains after the call. When the depth or the number of nodes is computed, the results of the recursive calls are combined and the computation is done on the way back. Which form is needed depends on whether the problem needs both subtrees.

Common mistake

Not writing return in front of the recursive call in recursive search: if (x < L->data) search(x, L->left);. The recursive call finds the node and returns its address, but the calling frame discards this value without using it. The procedure then moves on to the next line and returns a wrong value. The code usually compiles; the compiler gives only a "not every path returns a value" warning. Warnings should be turned on and taken seriously.

11.3.4Searching any binary tree

In a binary tree whose values are not sorted, search cannot know which direction to go. Both subtrees must be examined. The sample solution in the slides first looks at the left subtree; if it does not find the value there, it moves on to the right.

tree_ptr search_rec(int data, tree_ptr L) {
  if (!L) return NULL;              /* empty tree?   */
  if (L->data == data) return L;    /* key found     */
  tree_ptr T = search_rec(data, L->left);
  return T ? T : search_rec(data, L->right);
}

The first two lines of the procedure are the same as in recursive search. Line 4 searches the left subtree and stores the result in T. The conditional expression in line 5 returns T if it is not NULL. If the value was found on the left, the right is not looked at. If it was not found on the left, the result of the search of the right subtree is returned. If it is not on the right either, this result is NULL.

The procedure does not use the ordering information of the tree. If the value is not in the tree or is at the last node visited, all nodes are examined; the worst case is O(n). This procedure also works correctly on a binary search tree, but it is needlessly slow. In the driver program, 2, 1, and 7 were searched for in a general tree with root 5, left child 9, right child 1 of 9, and right child 2 of the root. The procedure found 2 and 1 and returned NULL for 7. In the same tree, the binary search tree procedures could not find 2.

The memory cost of this procedure is the call depth: O(h). The procedure is also used in the solution of the exam question on finding a weight. The instructor says something ambitious about these procedures: everyone in the class should be able to write them with eyes closed. Then he softens it: "All right, at least with one eye open." What is meant is this: the search, insertion, and depth procedures are the alphabet of trees. Every bigger problem is solved by combining them.

11.4Depth

The depth of a tree determines the cost of all operations. The procedure that computes it is small but an instructive example. The problem needs the answers from both subtrees and gives one of the cleanest examples of recursive thinking. This section first treats an iterative solution, then the recursive solution and two wrong ways of using it.

11.4.1Iterative depth and a global variable

The slides open this topic with a question: write the depth iteratively. The instructor reacts sharply to the typical solutions seen in class. Those solutions traverse the tree with a stack and keep the largest level seen so far in a global variable. According to the instructor, this code earns no points even if it works. A student asks, "If it works correctly, won't you give even one point?" The answer is firm: not even a quarter of a point. Why he is so strict will be explained shortly. First let us see an iterative solution that uses no global variable.

/* iterative, no globals:
walk level by level, count levels */
int depth_iter(tree_ptr L) {
  tree_ptr k[MAX_SIZE];
  int front = 0, rear = 0, d = 0;
  if (L) k[rear++] = L;
  while (front < rear) {          /* one level */
    int last = rear;
    d++;
    for (; front < last; front++) {
      if (k[front]->left) k[rear++] = k[front]->left;
      if (k[front]->right) k[rear++] = k[front]->right;
    }
  }
  return d;       /* needs MAX_SIZE >= n */
}

The solution traverses the tree in level order. The array k is used like a queue: front is the index of the next element and rear is the index of the first empty cell. The root is put into the queue. Each iteration of the outer loop handles one level. At the start of the iteration the end of that level is marked with last = rear and d is increased by one. The inner loop takes the nodes of that level from the queue in turn and adds their children to the back of the queue. These children are the next level. When the queue is empty, all levels have been counted and d gives the depth. In the empty tree nothing is put into the queue and d = 0 is returned.

An element taken from the queue is not deleted; front only advances. The array therefore has to be large enough to take all the nodes of the tree: MAX_SIZE ≥ n. The comment in the last line of the code recalls this condition. Since each node enters the queue once and leaves once, the time is O(n). The memory is the size of the array and sits in the stack region. In the driver program MAX_SIZE was chosen as 60,000; with 8-byte pointers this is about 470 KB. Since the default call stack on Windows is 1 MB, an array of a few hundred thousand nodes cannot be defined locally. In a real program this array should be allocated with malloc. The procedure gave the same result as the recursive version on the sample trees in the slides and on a tree built from 50,000 random values.

The reason for the instructor's reaction to the global variable is the scale of software. In large companies big jobs are done together. A procedure written by one person is used by someone at the other end. The instructor explains this with an analogy: the person using the procedure does not know the person who wrote it; perhaps he is in another country. He cannot pick up the phone and ask, "You have a variable called max; what is going on?" A procedure that uses a global variable has three problems.

  • Hidden state. The result of the procedure depends not only on its parameters but also on the current value of the global variable. If the variable holds a value left over from a previous call, the second call gives a wrong result. The user has to know that the variable must be reset before every call.
  • Name clashes. If a global variable with the same name is defined in two separate files, the linker reports an error or, worse, silently merges the two variables.
  • Lack of reentrancy. The procedure cannot be run for two trees at the same time. Two threads corrupt the same global variable; the procedure also cannot call itself recursively for another tree.

The slides draw three principles from this discussion. First, a procedure should be complete in itself: it takes its input from parameters, gives its output as a return value, and keeps no hidden state. Second, a local prototype of another procedure can be declared inside a procedure. This only makes the name visible inside that procedure; the definition stays outside. Standard C does not allow nested procedure definitions. This technique is used in the solution of the exam question on finding a weight. Third, in a recursive solution each call has its own local left and right variables; there is no need for a global counter at all.

11.4.2Recursive depth

The recursive definition of depth is a single sentence. The depth of the empty tree is 0. The depth of a non-empty tree is 1 more than the depth of the deeper of its left and right subtrees: depth(L) = MAX(depth(left), depth(right)) + 1. The added 1 is the root itself. The code follows this definition exactly.

int depth(tree_ptr L) {
  int left, right;
  if (L) {                   // pointer NULL?
    left = depth(L->left);
    right = depth(L->right);
    return MAX(left, right) + 1;
  }
  else return 0;             // reached past a leaf
}

The two local variables in line 2 store the depths of the subtrees. Line 3 asks whether the problem has become small enough. The instructor stresses this question in particular: "Has the problem become small enough? NULL may come at the start too!" The NULL check is not only for the empty children below the leaves; in the first call the tree itself may be empty. Lines 4 and 5 compute the depths of the two subtrees. Line 6 takes the larger and adds 1. Line 8 returns 0 for the empty tree.

MAX in the slides is a macro: #define MAX(a,b) ((a) > (b) ? (a) : (b)). The arguments here are just local variables; it does no harm that the macro evaluates an argument twice. Why the same macro is dangerous in the one-line version is the subject of the next subsection.

The slides trace the procedure on a tree with six nodes. A is the root, with B on its left and C on its right. D is on the left of B, E on the left of C, and F on the left of E. Table 11.4 gives the {left, right} values of each frame and its return value.

Table 11.4: Trace of the call depth(A). The rows are given in the order in which the frames finish; calls made with NULL return 0 and are not shown separately in the table.
Finishing orderLleftrightReturns
1D001
2B102
3F001
4E102
5C203
6A234

The calls follow the left branch first. depth(A) calls depth(B), which calls depth(D). Both children of D are NULL; the two recursive calls return 0 and D returns 1. B has no right child; B returns MAX(1, 0) + 1 = 2. The left variable of A becomes 2, and now depth(C) is called for the right subtree. From C we descend to E, and from E to F. F returns 1, E returns 2, and C returns 3. Finally A returns MAX(2, 3) + 1 = 4. The driver program gave the result 4 on the same tree.

A{?,?}B{?,?}D{0,0}CEFrunning nowon the stack {left,right}=returned A{2,?}B=2D=1CEFrunning nowon the stack {left,right}=returned A{2,3}B=2D=1C=3E=2F=1running nowon the stack {left,right}=returned
Figure 11.7: Three frames from the trace of recursive depth. Top: D is running; the frames of A and B wait on the stack with the values {?, ?}. Middle: B has returned 2, the left variable of A has become 2, and it is C's turn. Bottom: all frames have finished and A returns 4.

Figure 11.7 shows a property of the frames. Each node has its own two local variables: the left and right depths. When a frame finishes, its local variables vanish too. Calls made with NULL discard their local variables without ever using them. On the stack at any moment there are only the frames on the path from the root to the current node: at most h + 1 frames.

The cost analysis is as follows. One call is made for each node. In addition, one call is made for each NULL child. A binary tree with n nodes has n + 1 empty child pointers: of the 2n pointers in total, n − 1 point to a node and the rest are NULL. The number of calls is exactly 2n + 1. In the driver program this number was verified with a counter for every chain length from 1 to 24 and for perfect trees up to 262,143 nodes. Since each call does constant work, the time is Θ(n). To find the depth, looking at every node is necessary; no procedure can be faster than this. The memory is the call depth: O(h).

11.4.3The one-line version and the macro trap

The same procedure can also be written as a single expression without local variables. The slides present this version as a "professional" way of writing, and then show the trap inside it.

int depth(tree_ptr L) {    /* one line */
  return !L ? 0 : MAX(depth(L->left),
                      depth(L->right)) + 1;
}

The code is readable and gives the right result. But MAX is not a function but a macro. Before compilation the preprocessor replaces MAX(a, b) textually with ((a) > (b) ? (a) : (b)). Here a and b are procedure calls. The expanded expression first runs both calls for the comparison. Then, to return the larger one, it runs that call once more. At every node one of the subtrees is computed twice.

In a skewed tree the price of this is exponential. In a chain extending to the right, the left child of every node is NULL. Since the depth of the right subtree is larger, the right call is made twice. If the number of calls in a chain of n nodes is T(n), then T(n) = 2T(n − 1) + 2. The 2 here is the node's own call plus the call for the NULL left child. The solution is T(n) = 3 · 2n − 2. The situation is the same in a chain extending to the left. There the right child is NULL, the left call turns out larger and is made twice. In a full, balanced tree the depths of the two subtrees are equal. The comparison comes out false and the right subtree is recomputed. This time T(n) ≈ 3T(n/2) and the solution is Θ(nlg 3) ≈ Θ(n1.585). So even in a balanced tree the time is not linear.

Table 11.5: Call counts of the two depth procedures (measured with a counter). The version with local variables makes 2n + 1 calls on every tree.
TreenWith local variablesOne-line (macro)
chain4946
chain122512.286
chain20413.145.726
chain244950.331.646
full1.0232.04788.573
full65.535131.07164.570.081

Table 11.5 shows the difference in numbers. On a chain of 24 nodes the two procedures give the same result (24). One makes 49 calls, the other more than fifty million. Every new node doubles the number of calls of the macro version. On a chain of 40 nodes the number is 3 · 240 − 2, which exceeds three trillion. All the measured values fit the formula 3 · 2n − 2 exactly. On perfect trees the macro version makes (3k+1 − 1)/2 calls, where k is the number of levels.

The solution is to use a real function instead of a macro. A function evaluates its arguments once before the call and copies the values. The solution of the exam question on finding a weight takes this route:

int max(int a, int b) { return a > b ? a : b; }

The one-line depth procedure written with this function made exactly 2n + 1 calls on every tree in the driver program. The second solution is the version with local variables. The values are first taken into variables; the macro now only compares variables.

Common mistake

Passing an expression with side effects or a cost to a macro as an argument: MAX(depth(...), depth(...)), MAX(i++, j), SWAP(a[i++], b, t). Because the macro copies its argument as text, the expression is executed more than once. With recursive calls the result is exponential time, and with increment operators it is a wrong value. Only simple variables should be given to a macro; otherwise a function should be used.

Next to this subsection in the slides there is one more observation by the instructor. According to him, it is hard to make engineers accept recursive thinking and solving recurrence relations. Someone used to thinking in loops says, "What nice code I'm writing," and resists a new way of thinking. The depth example shows why this resistance is misplaced. The iterative solution needs a queue, a size limit, and two nested loops. The recursive solution is the definition itself and fits in four lines.

11.4.4Adding an extra parameter

The slides open this subsection with a well-known saying of A. J. Perlis. Roughly, it says: if you have a procedure with ten parameters, you have probably forgotten some. The joke says that a bloated parameter list is a sign of a design mistake.

A student asks: would it be all right to add an extra parameter, int depth(tree_ptr L, int a), and call the procedure as depth(L, 0)? The solution the student has in mind is probably this: a carries the level descended so far, a + 1 is passed to each recursive call, and when NULL is reached, a is returned. The code may work. But the instructor does not accept this design. Why is the extra parameter defined, and why is zero passed in the first call? What will we tell the user of the procedure: "Don't you dare forget to pass zero to a!"? The instructor makes this concrete with an example: could there be a sorting procedure that sorts when 0 is passed and fails to sort when 1 is passed?

The problem is that the parameter is not an input but an initial value belonging to the internal workings of the procedure. It puts an obligation on the user, and when the obligation is forgotten the procedure silently gives a wrong result. If necessary, such an extra parameter is kept in a helper procedure that is not exposed. The procedure exposed to the user takes only L and itself calls the helper with the correct initial value.

Not every extra parameter is bad. A sorting procedure can be given a parameter telling whether to sort from small to large or from large to small (−1/+1 or '<'/'>'). A parameter giving the type of the data can also be passed. These parameters select the behavior of the procedure. Each of their values is meaningful, and the user makes the choice knowingly. The principle is this: a parameter should select behavior and should not carry a hidden initial value.

11.5Deletion

Deletion is the most delicate operation of the binary search tree. Insertion is always done in place of a NULL pointer and changes only that pointer. The node to be deleted, however, can be anywhere in the tree, for example at the root. After the node is removed, the remaining nodes must be reconnected and the tree must again satisfy the definition.

11.5.1Three cases

There are three cases, according to the number of children of the node to be deleted.

  • A node with no children (a leaf). The parent's pointer to this node is set to NULL and the node is freed with free. The rest of the tree is not affected.
  • A node with one child. The parent's pointer is changed to point to the only child of the deleted node. The subtree of the child moves up one level as a whole. This does not break the order. If the deleted node is to the left of its parent, every value in its subtree is smaller than the parent. When the subtree moves up, it is still to the left of the parent.
  • A node with two children. The parent's single pointer cannot point to both subtrees at once. In place of the deleted node, a value that fits between the two subtrees must be put. There are different methods for this.

The slides examine the two-children case on a sample tree. The values 40, 20, 60, 10, 30, 50, 70, 42, 55, 65, 73, 52, 57, 66, 56 were inserted into the tree in this order. The depth of the tree is 6; the longest path is 40 → 60 → 50 → 55 → 57 → 56. The node to be deleted is 60. 60 has two children: 50 and 70. Under each of them there is a sizable subtree.

402010306050425552575670656673node to delete: 60
Figure 11.8: The tree used in the deletion examples. It was built by inserting 40, 20, 60, 10, 30, 50, 70, 42, 55, 65, 73, 52, 57, 66, 56 in this order; its depth is 6. The node to be deleted is 60, which has two children.

11.5.2A node with two children: the largest of the left subtree

Which value can take the place of 60? The new value must be larger than every value in the left subtree and smaller than every value in the right subtree. There are two candidates. The first is the largest value of the left subtree. This value comes immediately before 60 in inorder; it is called the predecessor of 60. The second is the smallest value of the right subtree. This value comes immediately after 60 in inorder and is the successor of 60. When either is put in place of 60, the order is preserved. The first method of the slides uses the predecessor.

How is the largest value in the left subtree found? In a subtree every right child is larger than its parent. So the largest value is found by starting at the root of the subtree and moving along right pointers. The first node with no right child is the largest. In the example the root of the left subtree of 60 is 50. From 50 we go right to 55, and from 55 right to 57. 57 has no right child; the largest of the left subtree is 57.

The largest element has no right child, but it may have a left subtree. In the example, 56 stands to the left of 57. When 57 is taken from its place, this left child must not be forgotten. 56 is moved to the right link of 55, the parent of 57. This is safe: 56 was in the right subtree of 55 and is larger than 55.

The move can be done in two ways. In the first way, the node of 57 is physically moved into the place of 60. For this, four links change: the right link of 40 points to 57, the right link of 55 to 56, the left link of 57 to 50, and the right link of 57 to 70. In the second way, the node of 60 is not released with free. Only 57 is written into its data field. Then the old node of 57 is deleted like a node with one child. The right link of 55 is updated to 56, and this single link change is enough. The second way is shorter and the code in the slides follows it. If the node has large fields other than the data, copying data can be expensive. In that case the first way is preferred.

402010306050425552575670656673keep going right in the left subtree: 50 → 55 → 57 40201030605042555257567065667357 has a left child 56! 4020103057504255525670656673data copy: 1 link updated · depth 6 → 5
Figure 11.9: The first method. Top: the largest value is found by going right repeatedly in the left subtree: 50 → 55 → 57. Middle: the left child of 57, which is 56, is seen; 56 must be moved to the right link of 55. Bottom: the data-copy way has been applied: 57 has been written in place of 60 and only the right link of 55 has been updated. The depth of the tree has dropped from 6 to 5.

11.5.3The deletion procedure and the pointer to a pointer

The deletion procedure also takes the tree as tree_ptr *L. If the deleted node is the root, the caller's root pointer must change. But the real subtlety of the procedure is that it uses the same idea not only for the root but for every link of the tree.

void bst_delete(int x, tree_ptr *L) {
  tree_ptr p = *L, *link = L;  // link to p
  while (p && p->data != x) {  // find x
    link = (x < p->data) ? &p->left
                        : &p->right;
    p = *link;
  }
  if (!p) return;              // x absent
  if (p->left && p->right) {  // 2 children
    tree_ptr *b = &p->left;     // left subtree's
    while ((*b)->right)           // largest
      b = &(*b)->right;           // node
    p->data = (*b)->data;      // move the data
    link = b;  p = *b;          // delete it
  }
  *link = p->left ? p->left : p->right;
  free(p);
}

At the center of the procedure stands the variable link. Its type is tree_ptr *, that is, a pointer to a pointer. link holds the address of the pointer that points to the node p currently under examination. This pointer is either the caller's root variable or the left or right field of a parent. Writing to *link changes the link that leads to p. So there is no need to keep separately who the parent is and which of its children p is. The pointer q in the insertion procedure and the "left or right?" question in its last line are merged here in a single variable.

  • Line 2. p holds the root and link holds the address of the root pointer (L). At the start *link == p.
  • Lines 3–7. x is searched for. At each step link is first turned into the address of the left or right field of p. Then we descend one level with p = *link. When the loop ends, either p is NULL or p->data == x. In both cases the equality *link == p is preserved.
  • Line 8. If x is not in the tree, the procedure returns without doing anything.
  • Lines 9–15. If there are two children, the largest of the left subtree is sought. b is also the address of a pointer. At first it points to the left field of 60; it advances along right fields until (*b)->right is NULL. When the loop ends, *b is the largest node and b is the address of the link that points to this node. Line 13 copies the largest value into the data field of the node to be deleted. Line 14 changes the node to be deleted: now the old largest node will be deleted, and the link leading to it is b. Since this node has no right child, it has at most one child.
  • Line 16. At this point p has at most one child. The link is turned to the left child if there is one, otherwise to the right child. If there is no child at all, the right child is NULL and the link becomes NULL. A leaf, a single child, and the second stage of the two-children case are all solved by the same line.
  • Line 17. The node detached from the tree is freed with free.

The order of the last two lines is important. First *link is updated, then p is released. If the order were reversed, line 16 would read the fields of a freed node. Another detail is the notation (*b)->right in line 11. The parentheses are necessary, because the operator -> is applied before *. If *b->right were written, the compiler would take b to be a pointer to a structure and the code would not compile.

If the procedure cannot find the value to be deleted, it returns silently. After a deletion the number of nodes drops by one. This was also checked in the driver program: at every deletion the free counter rose by one and the malloc counter did not change. When all 15 values of the sample tree were deleted one by one, the root pointer became NULL. From a tree of 2000 random values, all the values were deleted in random order. After each deletion it was checked that the tree was still a binary search tree, and in the end the malloc and free counts came out equal.

11.5.4Code trace: deleting 60

Table 11.6 traces the call bst_delete(60, &L) step by step. The addresses link and b are written in the form "&40->right", that is, by the field they point to.

Table 11.6: Trace of the call bst_delete(60, &L).
Lineplinkb / *bExplanation
240L—Start: link is the address of the root pointer.
4–660&40->right—60 > 40: descend to the right; the loop ends at 60.
9–1060&40->right&60->left / 50There are two children: move to the left subtree.
11–1260&40->right&50->right / 5550 has a right child.
11–1260&40->right&55->right / 5755 has a right child.
1160&40->right&55->right / 5757 has no right child: the largest is 57.
1360 (data 57)&40->rightsame57 is written into the data field of 60.
14old 57&55->rightsameThe node to be deleted is now the old 57.
16old 57&55->right—*link = 56: the right of 55 becomes 56.
17———The old node 57 is freed with free.
402010306050425552575670656673p 402010306050425552575670656673p 4020103057504255525670656673 4020103057504255525670656673
Figure 11.10: Four frames from the trace of bst_delete(60, &L). Left to right and top to bottom: link points to the right field of 40 and p is at 60; b has reached the largest of the left subtree (57); the right link of 55 has been turned to 56; the old node has been freed and the depth has dropped to 5.

After the deletion the tree is 40(20(10, 30), 57(50(42, 55(52, 56)), 70(65(−, 66), 73))). The inorder traversal is 10 20 30 40 42 50 52 55 56 57 65 66 70 73 and is still sorted. The driver program verified this tree and that its depth is 5.

The cost of the deletion procedure is the sum of two paths: the path descending to the node to be deleted and the path from there down to the largest element. Together these cannot be longer than a single path from the root to a leaf. The total is O(h): O(lg n) in a balanced tree and O(n) in a skewed tree. The procedure is iterative and uses a few pointers as extra memory: O(1).

Common mistake

Forgetting the left child of the moved element in a two-children deletion. In the example, if the right link of 55 is set to NULL when 57 is taken up, 56 is cut off from the tree. The node is still in memory, but no pointer points to it: the value is lost and memory leaks. The code in the slides prevents this with line 16; it always turns the link to the child of the deleted node, if there is one.

11.5.5Four methods and their effect on depth

The slides compare four methods for deleting a node with two children. The first two put a value in place of the deleted value; the last two move a subtree up.

  1. The largest of the left subtree. This is the method described in the previous subsection. 57 moves up and 56 is attached to the right of 55. The depth drops to 5.
  2. The smallest of the right subtree. This is the mirror method. In the right subtree of 60 we go left repeatedly: 70 → 65. 65 has no left child; the smallest is 65. 65 is written in place of 60. The right child of 65, 66, is attached to the left of 70. Since the long arm under 50 stays in place, the depth remains 6.
  3. The right child moves up. The right child (70) slides into the place of the deleted node. The left subtree (the subtree of 50) needs somewhere to hang. Every value in 50's subtree is smaller than every value in 70's subtree. So the subtree of 50 is hung to the left of the smallest node (65) of 70's subtree. The depth rises to 7.
  4. The left child moves up. This is the mirror of the third. The left child (50) slides into its place. The subtree of 70 is hung to the right of the largest node (57) of 50's subtree. The path 40 → 50 → 55 → 57 → 70 → 65 → 66 is seven nodes long; the depth is 7.
4020103057504255525670656673method 1 (largest of the left subtree): depth 6 → 5 4020103065504255525756706673method 2 (smallest of the right subtree): depth 6 → 6 4020103070655042555257566673method 3 (right child moves up): depth 6 → 7 4020103050425552575670656673method 4 (left child moves up): depth 6 → 7
Figure 11.11: The four methods of deleting 60, from top to bottom. In the first method 57 moves up and the depth drops to 5. In the second method 65 is moved, 66 is attached to the left of 70, and the depth stays 6. In the third method 70 slides up and the subtree of 50 is hung to the left of 65. In the fourth method 50 slides up and the subtree of 70 is hung to the right of 57. In the last two the depth rises to 7.

All four results are valid binary search trees. In the driver program all four were applied separately. In each, the inorder traversal gave the same sorted sequence. The depths came out as 5, 6, 7, and 7 respectively. The difference between them is in the shape of the tree and therefore in the cost of later searches. The last two methods increase the depth because they hang one subtree at the very bottom of another. The first two methods lift only a single node and do not increase the depth. The instructor therefore proposes this principle: the deletion should be done so that the tree rooted at the deleted element stays as balanced as possible. In practice the first two methods are used. Some implementations alternate between the two, so that always using the same side does not make the tree lean to one side over time.

The code for the second method is the mirror image of the first: we move into the right subtree instead of the left and follow left pointers instead of right.

void bst_delete_right(int x, tree_ptr *L) {    /* method 2 */
  tree_ptr p = *L, *link = L;
  while (p && p->data != x) {
    link = (x < p->data) ? &p->left
                        : &p->right;
    p = *link;
  }
  if (!p) return;
  if (p->left && p->right) {    // 2 children
    tree_ptr *b = &p->right;       // right subtree's
    while ((*b)->left)             // largest
      b = &(*b)->left;             // node
    p->data = (*b)->data;
    link = b;  p = *b;
  }
  *link = p->left ? p->left : p->right;
  free(p);
}

The expression in the last line is the same in both methods. The smallest node of the right subtree has no left child. So the expression turns the link to its right child. In the example, the left link of 70 points to 66.

11.6Balanced trees

The cost of every operation in the previous sections was O(h). This section shows in numbers how large h can grow. It then describes in detail the AVL tree, which keeps the height O(lg n) in every case. It also touches briefly on the red-black tree and the B-tree.

11.6.1The cost of imbalance

Table 11.7 compares the best-case and worst-case depth of a tree with n values. The depth of a balanced tree is ⌈lg(n + 1)⌉ and that of a skewed tree is n.

Table 11.7: Worst-case search length (number of nodes examined) in a balanced and a skewed tree.
nBalanced: ⌈lg(n + 1)⌉Skewed: n
1.000101.000
1.000.000201.000.000
2.000.000212.000.000
10930109

The difference in the table is striking. The instructor sums it up in one sentence: the difference between O(n) and O(lg n) is like the difference between 2,000,000 and 21. In an array of a billion records, a balanced tree finds a record in 30 steps. A skewed tree, in the worst case, takes a billion steps.

With data arriving in random order the situation is not that bad. When every order of the values is equally likely, the average depth of a tree with n values is Θ(lg n). The average number of comparisons of a successful search is about 2 ln n ≈ 1.39 lg n. This claim was measured in the driver program. 1000, 10,000, 100,000, and 1,000,000 random values were inserted into empty trees and the average level of the nodes was computed. The results were 12.1, 16.7, 21.0, and 25.2. The exact formula 2(1 + 1/n)Hn − 3 gives 12.0, 16.6, 21.2, and 25.8 for the same sizes. Here Hn is the sum 1 + 1/2 + … + 1/n. The measurements are very close to the formula. The value 1.39 lg n is the leading term of this formula and is about two more than what was measured at every size. The deepest path of the tree was longer: on average 47.7 levels at one million values. This is a little more than twice lg n ≈ 20.

A good average case is no guarantee. The worst case is sorted or nearly sorted data, which in fact is common. For this reason, trees have been developed that keep the depth at O(lg n) through local rotations after every insertion and deletion. The AVL tree, the red-black tree, and the B-tree are the best known of them.

11.6.2The AVL tree

The AVL tree is the first self-balancing binary search tree. Its name comes from the initials of G. M. Adelson-Velsky and E. M. Landis, who published the structure in 1962. In this section the height of a node is the depth of the subtree rooted at that node. The height of a leaf is 1 and that of the empty tree is 0. In the code this value appears under the name ht.

Definition 11.2

The balance factor of a node is found by subtracting the height of its right subtree from the height of its left subtree: ht(left) − ht(right). An AVL tree is a binary search tree in which the balance factor of every node is −1, 0, or +1.

The condition must hold at every node, not only at the root. A node with balance factor +1 is slightly heavy on the left, a node with −1 slightly heavy on the right; a node with 0 is perfectly balanced. The following theorem shows how strong the condition is.

Theorem 11.3 (Height of an AVL tree)

The height of an AVL tree with n nodes does not exceed about 1.44 lg(n + 2). Therefore search, insertion, and deletion in an AVL tree take O(lg n).

Proof sketch. Consider the smallest possible number of nodes of an AVL tree of height h; call it N(h). N(1) = 1 and N(2) = 2. One subtree of the sparsest tree of height h must have height h − 1. The height of the other subtree is at least h − 2 because of the balance condition. If both subtrees are chosen as sparse as possible, we get N(h) = N(h − 1) + N(h − 2) + 1. This recurrence resembles that of the Fibonacci numbers. The values N(h) + 1 follow the Fibonacci sequence: 2, 3, 5, 8, 13, … The Fibonacci numbers grow at the rate φh, where φ = (1 + √5)/2 ≈ 1.618. Hence n ≥ N(h) ≈ φh, that is, h ≤ logφ n = lg n / lg φ ≈ 1.44 lg n. An exact computation, with small corrections, gives the bound 1.44 lg(n + 2). ∎

N(h) was computed in the driver program: N(5) = 12, N(10) = 143, N(20) = 17,710, N(30) = 2,178,308. So an AVL tree of height 30 has more than two million nodes. An AVL tree with two million nodes has 29 levels in the worst case, whereas a skewed tree could have two million levels.

The AVL node in the slides adds a height field to the ordinary node. Two helper procedures shorten the computation of height and balance factor.

typedef struct avl *avl_ptr;
struct avl {
    int      data;
    int      ht;        /* subtree height */
    avl_ptr left, right;
};
int ht(avl_ptr t) { return t ? t->ht : 0; }
int balance(avl_ptr t) {
    return ht(t->left) - ht(t->right);
}

The procedure ht returns 0 for the empty tree. This way the caller does not have to check separately whether the subtree is NULL. The procedure balance computes the difference in the definition; it assumes that t is not empty. Because the height is stored at every node, the balance factor is found in O(1). If the height were not stored, the depth of the subtrees would be recomputed at every check and every operation would be O(n). The node size does not change: the int data and the int height together take 8 bytes, which with two pointers makes 24 bytes in total. The 4 bytes of alignment padding in the ordinary node go to the height field here.

The general plan of insertion is as follows. The insertion is first done as in an ordinary binary search tree. Then the heights and balance factors on the path from the inserted node up to the root are updated. If an ancestor whose factor is ±2 is found, the tree is repaired at that ancestor by a local rotation. There are four cases, according to which grandchild of that ancestor the new node is under: LL, RR, LR, and RL. LL and RR are repaired with a single rotation, LR and RL with a double rotation.

11.6.3Single rotation: LL and RR

A rotation is an operation that changes the local structure of the tree while preserving its order. In the figures of the slides, z is the first ancestor whose balance is broken. y is its child and x is its grandchild. The triangles T1–T4 are subtrees of known heights.

The LL case. The new node has entered the left subtree of the left child (y) of z. The factor of z rises to +2. To repair it, z is rotated to the right. y moves up and z becomes its right child. The right subtree of y, T3, moves to the left of z. This move is safe: the values in T3 are larger than y and smaller than z. The inorder sequence is the same before and after the rotation: T1 x T2 y T3 z T4.

z+2y+1xT1T2T3T4LL: the left of the left of z is heavy y0xz0T1T2T3T4rotate right(z): y becomes the root
Figure 11.12: The LL case and right rotation. Left: the factor of z is +2; the weight is on the left of the left. Right: z has been rotated right, y has become the root of the subtree, and T3 has moved to the left of z.

The RR case is the mirror image of LL. The new node has entered the right subtree of the right child of z, and the factor of z is −2. z is rotated to the left; the left subtree of y, T2, moves to the right of z.

z−2T1y−1T2xT3T4RR: the right of the right of z is heavy y0xz0T1T2T3T4rotate left(z): y becomes the root
Figure 11.13: The RR case and left rotation. Left: the factor of z is −2; the weight is on the right of the right. Right: z has been rotated left, y has become the root, and T2 has moved to the right of z.

In both cases, after the rotation the height of the subtree returns to its value before the insertion. For LL this is shown as follows. Let the height of the subtree of x before the insertion be k. Since z was balanced and the insertion raised it to +2, before the insertion the height of T3 was k, that of y was k + 1, and that of T4 was k. The height of the subtree was k + 2. The insertion raises the subtree of x to k + 1 and y to k + 2. After the rotation the two subtrees of z are T3 and T4. Since both have height k, the height of z becomes k + 1. Under y there are two subtrees of height k + 1: the subtree of x and z. So the height of y becomes k + 2. The height of the subtree is as it was before the insertion. Therefore the factors of the ancestors above do not change, and a single rotation suffices in insertion.

11.6.4Double rotation: LR and RL

The LR case. The new node has entered the right subtree of the left child (y) of z, that is, under x. A single right rotation does not help here. If z were rotated right, the heavy subtree of x would move to the left of z and the imbalance would shift to the other side. The solution takes two steps. First y is rotated left. x takes the place of y, and the case turns into the LL shape. Then z is rotated right. The grandchild x rises above its two ancestors. y sits on its left and z on its right. Of the old subtrees of x, T2 moves to the right of y and T3 to the left of z. This operation, made of two single rotations, is called a double rotation.

z+2y−1T4T1xT2T3LR: the right of the left of z is heavy zxT4yT3T1T21) rotate left(y) → LL shape xyzT1T2T3T42) rotate right(z): x is the root
Figure 11.14: The LR case and double rotation. Top: the factor of z is +2 and that of y is −1; the weight is on the right of the left. Middle: y has been rotated left and the case has reached the LL shape. Bottom: z has been rotated right and x has become the root.

The RL case is the mirror image of LR. The new node is in the left subtree of the right child of z. First the right child is rotated right, then z is rotated left. As a result of LR and RL, x is the median of the three nodes; that is why it rises to the root. In all four cases the result has the same shape: of the three nodes, the one with the median value becomes the root, the smaller becomes the left child and the larger the right child; the four subtrees are distributed below them in order.

11.6.5Rotation code and trace

The right rotation code changes only two pointers and recomputes two heights. The naming in the slides, as in Weiss's book, is k1 and k2: k2 is the node whose balance is broken and k1 is its left child.

avl_ptr rot_right(avl_ptr k2) {  // LL
  avl_ptr k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->ht = 1 + MAX(ht(k2->left), ht(k2->right));
  k1->ht = 1 + MAX(ht(k1->left), k2->ht);
  return k1;                       // new root
}
  • Line 2. k1 is the left child of k2 and will be the new root.
  • Line 3. The right subtree of k1 moves to the left of k2. This is the move of T3 in the figure.
  • Line 4. k2 becomes the right child of k1.
  • Lines 5–6. The heights are updated from the bottom up. First the height of k2 and then that of k1 is computed. The new right child of k1 is k2, and its height was found in the previous line. If the order is reversed, k1 uses an old, wrong value.
  • Line 7. The new root is returned. The caller attaches the parent's pointer to this node.

The slides trace the procedure with a small example. In the tree, 30 is the root, with 20 on its left and 40 on its right. The children of 20 are 10 and 25. When 5 is inserted, it goes to the left of 10. The factor of 30 becomes ht(20) − ht(40) = 3 − 1 = +2. The new value is on the left of the left; the case is LL and rot_right(30) is called.

Table 11.8: Trace of the call rot_right(30) (after 5 has been inserted).
LineOperationResult
2k1 = k2->leftk1 = 20
3k2->left = k1->right25 moves to the left of 30 (20 < 25 < 30); for now two pointers point to 25.
4k1->right = k230 becomes the right child of 20.
5k2->ht1 + MAX(ht(25) = 1, ht(40) = 1) = 2
6k1->ht1 + MAX(ht(10) = 2, 2) = 3
7return k1The new root is 20; the tree is 20(10(5, −), 30(25, 40)).
30height 420height 340height 110height 225height 15height 1k2 30height 420height 340height 110height 225height 15height 1k2k1 20height 310height 230height 25height 125height 140height 1k1
Figure 11.15: Three frames from the rot_right trace. Top: 5 has been inserted and the factor of 30 is +2. Middle: 25 has been moved to the left of 30 and 30 has been attached to the right of 20; the heights have not been updated yet. Bottom: the heights have been corrected and 20 is the root.

After the rotation the height of the subtree is 3; it was 3 before 5 was inserted too. Only two pointers changed. The rotation does a constant amount of work and its cost is O(1). In the driver program the same insertion sequence (30, 20, 40, 10, 25, 5) was applied. The single rotation was rot_right(30) and the resulting tree came out as in the table.

The slides do not give the code of the left rotation, but the AVL insertion code uses it. The left rotation is the mirror image of the right rotation: left and right are exchanged. The version used in the driver programs and the procedure that allocates a new AVL node are below.

avl_ptr rot_left(avl_ptr k1) {  // RR
  avl_ptr k2 = k1->right;
  k1->right = k2->left;
  k2->left = k1;
  k1->ht = 1 + MAX(ht(k1->left), ht(k1->right));
  k2->ht = 1 + MAX(k1->ht, ht(k2->right));
  return k2;                       // new root
}
avl_ptr new_avl(int x) {
  avl_ptr t = malloc(sizeof *t);
  if (!t) { fprintf(stderr, "Out of memory\n"); exit(EXIT_FAILURE); }
  t->data = x;  t->ht = 1;
  t->left = t->right = NULL;
  return t;
}

11.6.6Insertion into an AVL tree

The slides follow the example in Weiss's book. The values 3, 2, 1, 4, 5, 6, 7, 16, 15 are inserted in this order into an empty AVL tree. Table 11.9 gives the state after each insertion.

Table 11.9: Inserting 3, 2, 1, 4, 5, 6, 7, 16, 15 into an empty AVL tree. Trees are written in the form root(left, right); "−" is an empty subtree.
InsertedCaseRotationResult
3—none3
2—none3(2, −)
1LL, +2 at 3right at 32(1, 3)
4—none2(1, 3(−, 4))
5RR, −2 at 3left at 32(1, 4(3, 5))
6RR, −2 at 2left at 24(2(1, 3), 5(−, 6))
7RR, −2 at 5left at 54(2(1, 3), 6(5, 7))
16—none4(2(1, 3), 6(5, 7(−, 16)))
15RL, −2 at 7right at 16, left at 74(2(1, 3), 6(5, 15(7, 16)))

Three steps in the table deserve a separate explanation. When 6 is inserted, the imbalance appears not at the parent of the new node but at the root. The factor of 5 is −1 and that of 4 is −1; but the left subtree of the root 2 has height 1 and the right has height 3. The rotation is done at the root and 4 becomes the new root. When 7 is inserted, the imbalance is at 5 and the root is not affected. When 15 is inserted, the new node goes to the left of the right child (16) of 7. This is the RL case. First 16 is rotated right, then 7 is rotated left, and 15 becomes the parent of 7 and 16.

201030small numbers: balance factor 402010305-160small numbers: balance factor 4-12010306-15015070160small numbers: balance factor
Figure 11.16: Three frames from the AVL insertion example. The small numbers beside the nodes are balance factors. Top: 1 has been inserted and the LL case has been repaired by a right rotation at 3. Middle: 6 has been inserted and an RR rotation has been made at the root. Bottom: 15 has been inserted and the final tree has been obtained by an RL double rotation.

The height of the final tree is 4. If the same sequence had been inserted into an ordinary binary search tree, the chain 3 → 4 → 5 → 6 → 7 → 16 → 15 would have formed and the depth would have been 7. After every insertion the driver program printed the tree, the factors, and the rotations performed. The results came out the same as each row of the table. It was also checked at every step that the stored heights equal the real heights and that all factors stay in the range −1..+1.

The insertion code in the slides adds a balance check to the return path of recursive binary search tree insertion.

avl_ptr avl_insert(avl_ptr t, int x) {
  if (!t) return new_avl(x);              /* malloc, ht = 1         */
  if (x < t->data)      t->left = avl_insert(t->left, x);
  else if (x > t->data) t->right = avl_insert(t->right, x);
  else return t;                           /* no duplicate keys      */
  t->ht = 1 + MAX(ht(t->left), ht(t->right));
  int d = balance(t);
  if (d >  1 && x < t->left->data) return rot_right(t);            /* LL */
  if (d < -1 && x > t->right->data) return rot_left(t);            /* RR */
  if (d >  1) { t->left = rot_left(t->left); return rot_right(t); } /* LR */
  if (d < -1) { t->right = rot_right(t->right); return rot_left(t); } /* RL */
  return t;
}
  • Lines 2–5. This is ordinary recursive insertion. When an empty subtree is reached, a new node is allocated and its height is set to 1. If an equal value arrives, the tree is returned unchanged.
  • Lines 6–7. While returning from the recursion, the height of this node is updated and its balance factor is computed. These lines run in turn at each ancestor on the path from the new node to the root.
  • Line 8 (LL). If the factor is greater than +1, the weight is on the left. If x is smaller than the value of the left child, the new node is on the left of the left; a single right rotation suffices.
  • Line 9 (RR). The mirror: if the factor is less than −1 and x is larger than the right child, a single left rotation is made.
  • Line 10 (LR). The factor is +2 but the new node is on the right of the left. First the left child is rotated left, then the node is rotated right.
  • Line 11 (RL). The mirror.
  • Line 12. If the balance has not been broken, the node is returned as it is.

The code tells the cases apart by comparing the new value with the value of the child. If the new value is smaller than the left child, it has entered the left of the left; if larger, the right of the left. Since the values are unique, there is no equality. The usage is root = avl_insert(root, x);. Since the new root is given as the return value, no *L parameter is needed.

At most one rotation (single or double) suffices in insertion. The rotation brings the height of the subtree back to its value before the insertion; the ancestors above see no change. The code still computes heights and checks balance at all the ancestors on the path, but these are constant operations. The total cost is the length of the path, that is, O(lg n). The recursion keeps O(lg n) frames on the stack. Deletion is done in a similar way, but a rotation can decrease the height of the subtree. This decrease can upset the balance of an ancestor higher up. In deletion, therefore, up to O(lg n) rotations may be needed along the way to the root.

The behavior of the AVL tree on large inputs was also measured in the driver program. When the sorted values 1, 2, …, n were inserted, the height came out exactly ⌈lg(n + 1)⌉: 10 for 1000, 20 for a million, and 21 for two million. Because the weight always falls on the right in sorted data, only left rotations were made: 999,980 rotations in a million insertions. When a million random values were inserted, the height came out as 24. The upper bound in the theorem for this size is 28. If the same sorted data had been inserted into an ordinary binary search tree, the depth would have been a million.

11.6.7The red-black tree and the B-tree

The AVL tree keeps balance tight. The price of this tightness is that deletion may need many rotations. Two other balanced trees are also widely used in practice.

The red-black tree gives each node a color, red or black, and puts rules on the colors:

  • Every node is red or black; the root and the NULL leaves are black.
  • The children of a red node are black; there are no two red nodes in a row.
  • On every path from a node down to the NULLs below it there is the same number of black nodes.

These rules ensure that the longest path is no more than twice the shortest path. As a result the height is at most 2 lg(n + 1). The balance is looser than in AVL. In return, the number of rotations in insertion and deletion is bounded. At most two rotations in insertion and at most three in deletion, plus some recoloring, suffice. Because the structure of the tree changes less, the red-black tree is preferred in structures that are updated a lot. std::map in C++, TreeMap in Java, and many structures in the Linux kernel are red-black trees.

The B-tree is an m-way balanced search tree proposed in 1972 by R. Bayer and E. McCreight. A node holds several keys and at most m children. Every node other than the root holds between ⌈m/2⌉ − 1 and m − 1 keys. All leaves are at the same level. When a node becomes full, it splits in two by moving its middle key up to its parent. When the root splits, a new root is created. So a B-tree grows from the root, not from the leaves.

30 | 6010 | 2040 | 5070 | 80B-tree of order 3 (2-3 tree)
Figure 11.17: A small B-tree. Each node holds several sorted keys; one descends to the children through the gaps between the keys. All leaves are at the same level.

The main use of the B-tree is on disks and similar slow memories. Data is read from disk in blocks, and reading a block takes longer than making thousands of comparisons in memory. In a B-tree a node is matched to a disk block. m can be in the hundreds. The height of the tree then drops to about logm n. An index of a billion records is searched with three or four block reads. Database indexes and file systems use the B+ tree, a variant in which the data is kept only in the leaves.

11.6.8Which search tree?

Table 11.10 compares the search trees mentioned in this section.

Table 11.10: Comparison of search trees.
StructureSearch / insert / delete (worst case)Balance conditionWhere used
binary search treeO(n) (average O(lg n))nonesmall, random data; teaching
AVL treeO(lg n)|ht(left) − ht(right)| ≤ 1search-heavy workloads
red-black treeO(lg n)equal black heightlibrary maps (map)
B-tree / B+ treeO(logm n) disk accessesleaves at the same leveldatabases, file systems
splay treeO(lg n) amortizednone; the accessed node moves to the rootfrequently accessed items

The choice depends on the nature of the job. If the data is small and in random order, the ordinary binary search tree is enough and has the simplest code. If the number of searches is much greater than the number of updates, the tighter balance of the AVL tree shortens the searches. If insertions and deletions are frequent, the few rotations of the red-black tree stand out. If the data does not fit in memory, the B-tree is almost the only choice. If a small part of the accesses concentrates on a few values, the splay tree keeps those values near the root. The word "amortized" in the splay tree row of the table describes the average cost not of a single operation but of a long sequence of operations.

11.7Exam questions

The last part of the slides solves three exam questions asked in previous years. All three measure the same skill: writing correct and efficient code by combining small, well-defined procedures, and computing how much work a given piece of code does.

11.7.1The weight of an element

The question is this. In a binary tree with distinct values (it need not be a search tree), the weight of the element containing the value x is the longest of the paths from that element to the leaf nodes. If x is not in the tree or the tree is empty, the weight is 0. The procedure int FindWeight(tree_ptr L, int x) must be written without using global variables.

Read carefully, the definition shows that the weight is the depth of the subtree rooted at the node containing x. The problem is a composition of two well-known jobs: first find the node, then compute its depth. Since the tree is not sorted, the search is done with the procedure that works on any binary tree.

int FindWeight(tree_ptr L, int x) {
  /* tree_search: node holding x, or NULL */
  tree_ptr tree_search(tree_ptr L, int x);
  int depth(tree_ptr L);
  return depth(tree_search(L, x));
}
tree_ptr tree_search(tree_ptr L, int x) {
  if (!L) return NULL;
  if (L->data == x) return L;
  tree_ptr T = tree_search(L->left, x);
  return T ? T : tree_search(L->right, x);
}
int depth(tree_ptr L) {
  int max(int a, int b);  /* not smaller than a, b */
  return L ? max(depth(L->left),
                 depth(L->right)) + 1 : 0;
}

The beauty of the solution is in the third line: depth(tree_search(L, x)). If the value is not found, tree_search returns NULL. depth(NULL) is already 0. So the "not found" case is not handled separately; the definitions of the two procedures solve it automatically. The case L == NULL gives 0 the same way.

The first two lines of the code are local prototypes declared inside the procedure. These declarations make the names tree_search and depth visible only inside FindWeight. They are necessary because the procedures are defined in the file after FindWeight. In the same way, depth declares the function max. Using a function rather than a macro here is deliberate. A macro would make the number of calls of the depth procedure exponential.

The cost is the sum of two parts. The search examines all nodes in the worst case: O(n). The depth traverses only the subtree found; that has at most n nodes. The total is O(n). In the driver program, on a tree with root 2 and children 10 and 20, the weights came out as 2, 1, 1, and 0 for x = 30. On the tree from the deletion examples, the weight of 40 was found to be 6, of 60 it was 5, of 50 it was 4, and of 56 it was 1.

11.7.2How many times is the procedure called?

The second question examines a bad piece of code that tries to solve the same problem. In the code, weight(L) is a procedure that gives the depth of the subtree rooted at L.

int FindWeight(item_ptr L, int x) {
  if (!L) return 0;
  else if (L->data == x) return weight(L);
  if (FindWeight(L->left, x) >
      FindWeight(L->right, x))
    FindWeight(L->left, x);
  if (FindWeight(L->right, x) >
      FindWeight(L->left, x))
    FindWeight(L->right, x);
  return 0;
}

The question has two parts. The tree has three nodes: root 2, left child 10, and right child 20. The first part asks how many times the procedure is called for x = 20 and x = 30. In the second part, a recurrence for the worst case must be written and solved.

First consider what a leaf, say 10, does when it does not contain x. The leaf is not NULL and its value is not equal to x. The first if makes two recursive calls, and the second if makes two more. All four are made with NULL and return 0. Since 0 > 0 is false, the calls inside the conditions are not made. A leaf call, together with itself, makes 1 + 4 = 5 calls.

x = 30 is not in the tree. The root call calls 10 twice and 20 twice. Each returns 0 and the conditional calls are not made. The total is 1 + 4 · 5 = 21 calls. For x = 20 the situation is different. The call made for 20 finds equality in the second line and returns the weight (1) in a single call. At the root, the first if makes 5 calls for 10 and 1 call for 20; 0 > 1 is false. The second if again makes 1 + 5 calls and 1 > 0 is true. The FindWeight(L->right, x) inside the condition makes one more call. The total is 1 + 6 + 6 + 1 = 14. Despite all this effort, the procedure returns 0 in both cases. The results of the calls inside the conditions are not used, and the last line is always 0. The code is both slow and wrong: it gives the right answer only when x is at the root.

In the worst case x is not in the tree and the whole tree is traversed. Each call calls each of its subtrees twice. In a skewed tree one subtree has n − 1 nodes and the other is empty. The recurrence is T(n) = 2T(n − 1) + c. Unrolled, it gives T(n) = 2nT(0) + c(2n − 1), that is, Θ(2n). In a balanced tree each of the two subtrees has about n/2 nodes and all four calls are made: T(n) = 4T(n/2) + c. By the master theorem or by unrolling, the solution is Θ(n2). At each level the number of calls quadruples while the problem halves, and 4lg n = n2.

Table 11.11: Number of calls made by the bad FindWeight procedure when x is not in the tree (measured with a counter).
TreenNumber of callsRatio
chain461calls / 2n = 3.81
chain1216.3813,999
chain204.194.3014,000
full25587.381calls / n2 = 1.344
full4.09522.369.6211,334

The measurements confirm the recurrences. In a chain the number of calls is exactly 2n+2 − 3 and the ratio approaches 4. In a perfect tree the ratio approaches 4/3. The right design is the solution in the previous subsection, which takes O(n). On a chain of 20 nodes the bad procedure makes more than four million calls. The right procedure makes do with a few dozen calls to look at the 20 nodes of the same tree.

The lesson of the question is the cost of computing the result of a recursive call twice. At every level the work doubles and the factors multiply with each other. If the result of a recursive call is needed more than once, it should be stored in a local variable. The left and right variables in the depth procedure do exactly this job.

11.7.3SWAP between two calls

The third question asks about the effect of a procedure on a tree. The macro SWAP(x, y, t) exchanges the values of x and y by means of t: ((t) = (x), (x) = (y), (y) = (t)).

void proc(tree_ptr L) {
  tree_ptr p;
  if (L) {
    proc(L->left);
    SWAP(L->left, L->right, p);
    proc(L->right);
  }
}

The question is this: run the procedure on the binary search tree built with the values {44, 30, 15, 18, 86, 97, 65, 113, 74, 129}. If the picture of the tree changes each time the SWAP line is passed, redraw the tree and interpret its final form.

In the initial tree the root is 44. On its left is 30; to the left of 30 is 15, and to the right of 15 stands 18. To the right of the root is 86. To the left of 86 is 65 with 74 on its right; to the right is a chain extending to the right made of 97, 113, and 129.

At a node, the procedure first processes the left subtree, then exchanges the two children, then processes the new right child. But the new right child is the old left child, which has just been processed. The old right child has moved to the left and is never processed. The steps are as follows.

  1. proc(44) → proc(30) → proc(15). The left of 15 is empty. SWAP 15: 18 moves to the left.
  2. The new right of 15 is empty. Return to 30. SWAP 30: the subtree of 15 moves to the right.
  3. 15, the new right child of 30, is processed again. Its left (18) is processed first; SWAP is executed at 18, but since both children are empty the picture does not change. SWAP 15: 18 moves to the right again. The 18 on the right is processed once more; the picture again does not change.
  4. Return to 44. SWAP 44: the subtree of 86 moves to the left and the subtree of 30 to the right.
  5. 30, the new right child of 44, is processed again. Its left is empty. SWAP 30: the subtree of 15 turns back to the left. The new right is empty and the procedure ends.
4430151886657497113129 4430151886657497113129 4486657497113129301518 4486657497113129301518
Figure 11.18: SWAP between two recursive calls. From top to bottom: the initial tree; after the first SWAP at 30; after the SWAP at 44; the final form. The two subtrees of the root have been exchanged, but the inside of the subtrees is as at the start.

The SWAPs at which the picture changes are, in order, at 15, 30, 15, 44, and 30. The two SWAPs at 18 do not change the picture. The final tree is 44(86(65(−, 74), 97(−, 113(−, 129))), 30(15(−, 18), −)). Only the two subtrees of the root have been exchanged. The 30 subtree was processed twice, and each change was undone in the second pass. The 86 subtree was not processed at all. The result is neither the tree itself nor its mirror, and it is no longer a binary search tree. The driver program printed every step by adding a trace call to the SWAP line; the order and the final tree are as above.

If SWAP had been written before or after both recursive calls, an exact mirror of the tree would have been obtained. When it is written first, the children are exchanged and then the two subtrees are mirrored separately. When it is written last, the two subtrees are mirrored first and then their places are exchanged. In both cases every subtree is processed exactly once. In a mirrored binary search tree, inorder traversal gives the values in decreasing order.

11.8Complexity summary

Table 11.12 gives the costs of all the procedures written in these notes together. h is the depth of the tree; it is O(lg n) in a balanced tree and n in a skewed tree.

Table 11.12: Time and extra-memory cost of search tree operations.
OperationBest / balancedWorst (skewed)Extra memory
bst_search (iterative)O(lg n)O(n)O(1)
search (recursive)O(lg n)O(n)O(h) stack
bst_insertΩ(lg n)O(n)O(1)
bst_deleteO(lg n)O(n)O(1)
depthΘ(n)Θ(n)O(h)
search in a general binary treeO(n)O(n)O(h)
AVL search / insert / deleteO(lg n)O(lg n)O(lg n) recursion
single rotationO(1)O(1)—

The essence of the table: in a binary search tree, search, insertion, and deletion follow a path and take O(h). Operations that must look at every node of the tree (depth, search in a general tree) are O(n). Balanced trees keep h at O(lg n), making the worst case of the path-following operations logarithmic as well. The Ω(lg n) in the insertion row says that insertion cannot be faster than lg n in any tree.

11.9Common mistakes

  1. Failing to update the root pointer. If the insertion procedure takes tree_ptr L, the first insertion into an empty tree does not change the caller's root. The tree stays empty and the node leaks. Either the address must be passed with tree_ptr *L, or the new root must be returned and assigned.
  2. Not keeping a trailing pointer. In iterative insertion, when p reaches NULL the parent to which the new node will be attached is no longer known. Either q, trailing one step behind, or a pointer to a pointer must be used.
  3. Not returning the result of the recursive call. If only search(...) is written in recursive search instead of return search(...), the address found is lost.
  4. Forgetting the child of the moved element. In a two-children deletion, if the left child of the largest element of the left subtree (56 in the example) is not attached to its parent, it is cut off from the tree.
  5. Global variables and unnecessary extra parameters. A global counter for depth, or a parameter of the "pass 0 in the first call" kind, makes the procedure fragile and not reusable.
  6. Passing a recursive call to a macro. MAX(depth(...), depth(...)) runs one of the calls twice and makes the time exponential.
  7. Using memory after freeing it. In deletion, if the node is freed with free before the link is updated, the next line reads freed memory.
  8. Checking only against children. Whether a tree is a binary search tree cannot be told from parent–child comparisons alone; the range coming down from the root must be applied at every node.

11.10Exercises and solutions

This section solves the six exercises in the slides. The solutions with code were compiled and run with driver programs.

1. Insertion and preorder. Insert 50, 30, 70, 20, 40, 60, 80, 35 in this order into an empty tree. 50 becomes the root. 30 and 70 are its children. 20 and 40 are children of 30; 60 and 80 are children of 70. 35 follows the path 50 → 30 → 40 and goes to the left of 40. The tree is 50(30(20, 40(35, −)), 70(60, 80)) and its depth is 4. The preorder is 50 30 20 40 35 70 60 80.

2. Deleting 30 from the same tree in two ways. 30 has two children. In the first method the largest of the left subtree is sought. The left subtree of 30 is a single node (20); the largest is 20. 20 is written in place of 30 and the old node of 20 is deleted. The tree becomes 50(20(−, 40(35, −)), 70(60, 80)). Since the path 50 → 20 → 40 → 35 remains, the depth is 4. In the second method the smallest of the right subtree is sought: from 40 we go left to 35. 35 is written in place of 30 and the left of 40 becomes NULL. The tree is 50(35(20, 40), 70(60, 80)) and the depth drops to 3. In this example the second method gives a more balanced tree.

3. The smallest and the largest value. The smallest value is found by going left repeatedly from the root; it is at the first node with no left child. The largest value is found by going right repeatedly.

tree_ptr find_min(tree_ptr L) {
  if (L)
    while (L->left) L = L->left;
  return L;                 /* NULL for an empty tree */
}
tree_ptr find_max(tree_ptr L) {
  if (L)
    while (L->right) L = L->right;
  return L;
}

Both procedures follow only one path and take O(h). On the empty tree they return NULL. On the tree from the deletion examples, the smallest value came out as 10 and the largest as 73.

4. Checking a binary search tree. The permitted (lo, hi) range is passed to each node as parameters. When descending left, the upper bound becomes the value of the node; when descending right, the lower bound does.

#include <limits.h>
/* every value in L must satisfy lo < value < hi */
boolean in_range(tree_ptr L, long long lo, long long hi) {
  if (!L) return TRUE;
  if (L->data <= lo || L->data >= hi) return FALSE;
  return in_range(L->left, lo, L->data) &&
         in_range(L->right, L->data, hi);
}
boolean is_bst(tree_ptr L) {
  return in_range(L, (long long)INT_MIN - 1, (long long)INT_MAX + 1);
}

The bounds have type long long. This way the values INT_MIN and INT_MAX may also occur in the tree; the initial bounds lie just outside them. If long had been used, INT_MAX + 1 would overflow on Windows, where long is 32 bits. Since each node is looked at once, the time is O(n) and the recursion depth is O(h). The procedure found the tree from the deletion examples and its four deletion results valid. On a tree with root 15 and children 10 and 18, when 12 was placed to the left of 18, it returned FALSE. 12 is smaller than 18; a comparison with children alone would have accepted this tree as valid. But 12 is in the right subtree of 15 and cannot be smaller than 15.

5. Inserting 10, 20, 30, 25, 28 into an AVL tree. When 10 and 20 are inserted, the factor of 10 is −1. When 30 is inserted, the factor of 10 is −2 and the new value is on the right of the right (RR). 10 is rotated left and 20 becomes the root: 20(10, 30). 25 goes to the left of 30; the factors are in the range −1..+1. 28 goes to the right of 25. The factor of 30 becomes +2 and the new value is on the right of the left (LR). First 25 is rotated left: 28 takes the place of 25. Then 30 is rotated right: 28 becomes the parent of 25 and 30. The final tree is 20(10, 28(25, 30)). The driver program reported the same two rotations: rot_left(10) at 30, and rot_left(25) and rot_right(30) at 28.

6. The number of keys smaller than x. The simplest solution is to traverse the tree in inorder and count until x is reached; the time is O(n). Using the order of the binary search tree, some subtrees can be skipped. If the root is not smaller than x, the right subtree is entirely larger and counting continues only on the left. If the root is smaller than x, the root itself and its whole left subtree are smaller. These are counted and counting continues on the right.

int node_count(tree_ptr L) {
  return L ? 1 + node_count(L->left) + node_count(L->right) : 0;
}
/* number of values smaller than x */
int count_less(tree_ptr L, int x) {
  if (!L) return 0;
  if (L->data >= x)                 /* root and right are larger */
    return count_less(L->left, x);
  return 1 + node_count(L->left) /* root and left are smaller */
           + count_less(L->right, x);
}

In this version node_count still traverses the left subtrees from start to finish. So the worst case is still O(n). If the size of its subtree is stored in a field at each node, node_count drops to O(1) and the counting is done along a single path, that is, in O(h). This field must be updated at the nodes along the path at every insertion and deletion. In the example tree, 7 values smaller than 55 and 4 values smaller than 41 were found.

11.11Summary

  • In a binary search tree the values are unique; all values in the left subtree of every node are smaller than it, those in the right subtree are larger, and the subtrees are binary search trees too. Inorder traversal gives the values in increasing order.
  • Insertion searches for the value from the root and puts it in place of the first NULL. The iterative version uses the pointer q, trailing one step behind, and the parameter tree_ptr *L for the empty tree. The insertion order determines the shape of the tree; sorted data builds a skewed tree.
  • Search eliminates a subtree with every comparison and takes O(h). The recursive version is tail recursion and returns the result of the recursive call unchanged. In an unsorted tree both sides must be examined and the search is O(n).
  • Depth is computed recursively with MAX(left, right) + 1; it makes 2n + 1 calls and is Θ(n). Global variables and parameters carrying a hidden initial value are not used. If a recursive call is passed to a macro, the time becomes exponential.
  • In deletion, leaves and nodes with one child are easy. For a node with two children, the value of the predecessor (or successor) is copied and its node is deleted; the link is updated in a single line with a pointer to a pointer. The deletion method can change the depth of the tree.
  • Balance. On random data the average depth is Θ(lg n), but on sorted data it rises to n. The AVL tree keeps the balance factor of every node in the range −1..+1; its height is at most about 1.44 lg(n + 2).
  • In AVL insertion the imbalance is repaired with a single rotation in the LL and RR cases and a double rotation in the LR and RL cases. A rotation changes only two pointers and is O(1); at most one rotation suffices in insertion.
  • The red-black tree makes few rotations with a looser balance and is used in the map structures of libraries. The B-tree reduces disk accesses with its multi-key nodes and is used in databases.

11.12Key terms

  • binary search tree (BST)
  • key
  • subtree
  • leaf
  • depth
  • level
  • preorder
  • inorder
  • postorder
  • level-order
  • skewed tree
  • balanced tree
  • self-balancing tree
  • call by reference
  • pointer to pointer
  • global variable
  • macro
  • predecessor
  • successor
  • memory leak
  • AVL tree
  • balance factor
  • rotation
  • double rotation
  • red-black tree
  • B-tree
  • splay tree
  • recurrence relation
  • amortized analysis

11.13Test Yourself

  1. The values 8, 3, 10, 1, 6, 14, 4, 7, 13 are inserted in this order into an empty binary search tree. What is the depth of the tree? What are the preorder and inorder sequences?

    Answer

    The tree is 8(3(1, 6(4, 7)), 10(−, 14(13, −))). The longest paths are 8 → 3 → 6 → 4 and 8 → 10 → 14 → 13; the depth is 4. The preorder is 8 3 1 6 4 7 10 14 13 and the inorder is 1 3 4 6 7 8 10 13 14.

  2. In the same tree, 7 and 5 are searched for with bst_search. Which nodes are examined in each search, and what is the result?

    Answer

    For 7 the nodes 8, 3, 6, 7 are examined and the address of 7 is returned. For 5 the nodes 8, 3, 6, 4 are examined; since the right child of 4 is NULL, the search returns NULL.

  3. The bst_delete procedure from the slides is applied to the same tree: first only 3 is deleted (in a separate trial, only the root 8). How does the tree change in each case?

    Answer

    3 has two children. The largest of its left subtree is 1 (1 has no right child). 1 is written in place of 3 and the old node of 1 is deleted: 8(1(−, 6(4, 7)), 10(−, 14(13, −))). If the root 8 is deleted, the largest of the left subtree is found along the path 3 → 6 → 7: it is 7. 7 is written into the data field of the root and the right of 6 becomes NULL: 7(3(1, 6(4, −)), 10(−, 14(13, −))).

  4. The preorder traversal of a binary search tree is 30 20 10 25 40 35 50. What is its postorder traversal?

    Answer

    The tree is 30(20(10, 25), 40(35, 50)). The postorder traversal is 10 25 20 35 50 40 30.

  5. 1, 2, 3, 4, 5, 6, 7 are inserted in this order into an empty AVL tree. At which insertions is a rotation needed, and what is the final tree?

    Answer

    All the imbalances are RR cases and are repaired by a single left rotation. A left rotation is made at 1 when 3 is inserted, at 3 when 5 is inserted, at the root 2 when 6 is inserted, and at 5 when 7 is inserted; four rotations in all. The final tree is perfectly balanced: 4(2(1, 3), 6(5, 7)) and its height is 3.

  6. What is the minimum number of nodes in an AVL tree of height 5?

    Answer

    From the recurrence N(h) = N(h − 1) + N(h − 2) + 1, N(1) = 1, N(2) = 2, we get N(3) = 4, N(4) = 7, N(5) = 12. At least 12 nodes are needed.

  7. The one-line depth procedure is written with the MAX macro. On a right-extending chain of three nodes, how many times is the procedure called in total? How many times is the version with local variables called?

    Answer

    In the macro version T(0) = 1 and T(n) = 2T(n − 1) + 2: T(1) = 4, T(2) = 10, T(3) = 22. The version with local variables makes 2n + 1 = 7 calls. Both values were measured with a counter.

  8. If the parameter of bst_insert is changed from tree_ptr *L to tree_ptr L and the last lines are corrected accordingly, what is the result of inserting 5 and 7 into an empty tree?

    Answer

    In the first insertion the new node is assigned only to the procedure's local copy of L. The caller's root stays NULL, and the node leaks since nothing points to it. The second insertion also finds the tree empty and the same thing happens. The tree stays empty and two nodes leak.

  9. If the SWAP line in proc is moved in front of the two recursive calls, how does the tree with root 2, left child 1, right child 3, and left child 0 of 1 change?

    Answer

    First the children are exchanged at the root: 2(3, 1(0, −)). Then the left subtree (3) and the right subtree (1) are processed separately; at 1, 0 moves to the right. The final tree is 2(3, 1(−, 0)) and it is the exact mirror of the first tree. The inorder traversal is 3 2 1 0, that is, in decreasing order.

11.14Further reading

  • E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Sections 5.7 and 10.2: the source of the binary search tree procedures and the AVL tree that these notes follow.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed.), Chapters 12, 13, and 18: the binary search tree, the average depth of a randomly built tree, the red-black tree, and the B-tree, with proofs.
  • M. A. Weiss, Data Structures and Algorithm Analysis in C (2nd ed.), Section 4.4: contains the AVL insertion example and the rotation code used in the notes; also introduces the splay tree.
  • R. Sedgewick, Algorithms in C, Parts 1–4, Chapters 12–13: the average-case analysis of the binary search tree and a comparison of different kinds of balanced trees.

11.15References

  1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Sections 5.7 (binary search tree) and 10.2 (AVL tree).
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, Chapters 12 (binary search trees), 13 (red-black trees), 18 (B-trees).
  3. M. A. Weiss, Data Structures and Algorithm Analysis in C, Section 4.4 (AVL trees).
  4. R. Sedgewick, Algorithms in C, Parts 1–4, Chapters 12–13.

Related pages: Chapter 11 slides · © Sercan Külcü. All rights reserved.