# CHAPTER 4: TREES

See how trees are used to implement the file system of several popular operating systems.

See how trees can be used to evaluate arithmetic expressions.

Show how to use trees to support searching operations in O(log n) average time, and how to refine these ideas to obtain O(log n) worst-case bounds. We will also see how to implement these operations when the data is stored on a disk.

# 4.1. Preliminaries

The root of each subtree is said to be a child of r, and r is the parent of each subtree root. Figure 4.1 shows a typical tree using the recursive definition.

From the recursive definition, we find that a tree is a collection of n nodes, one of which is the root, and n - 1 edges. That there are n - 1 edges follows from the fact that each edge connects some node to its parent, and every node except the root has one parent (see Fig. 4.2).

#### Figure 4.2 A tree

In the tree of Figure 4.2, the root is A. Node F has A as a parent and K, L, and M as children. Each node may have an arbitrary number of children, possibly zero. Nodes with no children are known as leaves; the leaves in the tree above are B, C, H, I, P, Q, K, L, M, and N. Nodes with the same parent are siblings; thus K, L, and M are all siblings. Grandparent and grandchild relations can be defined in a similar manner.

A path from node n1 to nk is defined as a sequence of nodes n1, n2, . . . , nk such that ni is the parent of ni+1 for 1 i < k. The length of this path is the number of edges on the path, namely k -1. There is a path of length zero from every node to itself. Notice that in a tree there is exactly one path from the root to each node.

For any node ni, the depth of ni is the length of the unique path from the root to ni. Thus, the root is at depth 0. The height of ni is the longest path from ni to a leaf. Thus all leaves are at height 0. The height of a tree is equal to the height of the root. For the tree in Figure 4.2, E is at depth 1 and height 2; F is at depth 1 and height 1; the height of the tree is 3. The depth of a tree is equal to the depth of the deepest leaf; this is always equal to the height of the tree.

If there is a path from n1 to n2, then n1 is an ancestor of n2 and n2 is a descendant of n1. If n1 n2, then n1 is a proper ancestor of n2 and n2 is a proper descendant of n1.

## 4.1.1. Implementation of Trees

One way to implement a tree would be to have in each node, besides its data, a pointer to each child of the node. However, since the number of children per node can vary so greatly and is not known in advance, it might be infeasible to make the children direct links in the data structure, because there would be too much wasted space. The solution is simple: Keep the children of each node in a linked list of tree nodes. The declaration in Figure 4.3 is typical.

`typedef struct tree_node *tree_ptr;`

`struct tree_node`

`{`

`element_type element;`

`tree_ptr first_child;`

`tree_ptr next_sibling;`

`};`

#### Figure 4.4 First child/next sibling representation of the tree shown in Figure 4.2

Figure 4.4 shows how a tree might be represented in this implementation. Arrows that point downward are first_child pointers. Arrows that go left to right are next_sibling pointers. Null pointers are not drawn, because there are too many.

In the tree of Figure 4.4, node E has both a pointer to a sibling (F) and a pointer to a child (I), while some nodes have neither.

## 4.1.2. Tree Traversals with an Application

*Each directory in the UNIX file system also has one entry that points to itself and another entry that points to the parent of the directory. Thus, technically, the UNIX file system is not a tree, but is treelike.

#### Figure 4.5 Unix directory

`void`

`list_directory ( Directory_or_file D )`

`{`

`list_dir ( D, 0 );`

`}`

`void`

`list_dir ( Directory_or_file D, unsigned int depth )`

`{`

`/*1*/        if ( D is a legitimate entry)`

`{`

`/*2*/             print_name ( depth, D );`

`/*3*/             if( D is a directory )`

`/*4*/                  for each child, c, of D`

`/*5*/                       list_dir( c, depth+1 );`

`}`

`}`

#### Figure 4.6 Routine to list a directory in a hierarchical file system

Suppose we would like to list the names of all of the files in the directory. Our output format will be that files that are depth d will have their names indented by d tabs. Our algorithm is given in Figure 4.6.

The heart of the algorithm is the recursive procedure list_dir. This routine needs to be started with the directory name and a depth of 0, to signify no indenting for the root. This depth is an internal bookkeeping variable, and is hardly a parameter that a calling routine should be expected to know about. Thus the driver routine list_directory is used to interface the recursive routine to the outside world.

The logic of the algorithm is simple to follow. The argument to list_dir is some sort of pointer into the tree. As long as the pointer is valid, the name implied by the pointer is printed out with the appropriate number of tabs. If the entry is a directory, then we process all children recursively, one by one. These children are one level deeper, and thus need to be indented an extra space. The output is in Figure 4.7.

`/usr`

`mark`

`book`

`chr1.c`

`chr2.c`

`chr3.c`

`course`

`cop3530`

`fall88`

`syl.r`

`spr89`

`syl.r`

`sum89`

`syl.r`

`junk.c`

`alex`

`junk.c`

`bill`

`work`

`course`

`cop3212`

`fall88`

`grades`

`prog1.r`

`prog2.r`

`fall89`

`prog1.r`

`prog2.r`

`grades`

#### Figure 4.7 The (preorder) directory listing

Since the directories are themselves files, they have sizes too. Suppose we would like to calculate the total number of blocks used by all the files in the tree. The most natural way to do this would be to find the number of blocks contained in the subdirectories /usr/mark (30), /usr/alex (9), and /usr/bill (32). The total number of blocks is then the total in the subdirectories (71) plus the one block used by /usr, for a total of 72. The function size_directory in Figure 4.9 implements this strategy.

#### Figure 4.8 Unix directory with file sizes obtained via postorder traversal

`unsigned int`

`size_directory( Directory_or_file D )`

`{`

`unsigned int total_size;`

`/*1*/         total_size = 0;`

`/*2*/         if( D is a legitimate entry)`

`{`

`/*3*/              total_size = file_size( D );`

`/*4*/              if( D is a directory )`

`/*5*/                   for each child, c, of D`

`/*6*/                        total_size += size_directory( c );`

`}`

`/*7*/         return( total_size );`

`}`

#### Figure 4.9 Routine to calculate the size of a directory

`                ch1.r                3`

`                ch2.r                2`

`                ch3.r                4`

`           book                     10`

`                syl.r                1`

`                     fall88          2`

`                syl.r                5`

`                     spr89           6`

`                syl.r                2`

`                     sum89           3`

`                cop3530             12`

`           course                   13`

`           junk.c                    6`

`      mark                          30`

`           junk.c                    8`

`      alex                           9`

`           work                      1`

`                         grades      3`

`                         prog1.r     4`

`                         prog2.r     1`

`                    fall88           9`

`                         prog2.r     2`

`                         prog1.r     7`

`                         grades      9`

`                    fall89          19`

`               cop3212              29`

`          course                    30`

`     bill                           32`

`/usr                                72`

#### Figure 4.10 Trace of the size function

If D is not a directory, then size_directory merely returns the number of blocks used by D. Otherwise, the number of blocks used by D is added to the number of blocks (recursively) found in all of the children. To see the difference between the postorder traversal strategy and the preorder traversal strategy, Figure 4.10 shows how the size of each directory or file is produced by the algorithm.

# 4.2. Binary Trees

Figure 4.11 shows that a binary tree consists of a root and two subtrees, Tl and Tr, both of which could possibly be empty.

A property of a binary tree that is sometimes important is that the depth of an average binary tree is considerably smaller than n. An analysis shows that the average depth is , and that for a special type of binary tree, namely the binary search tree, the average value of the depth is O(log n). Unfortunately, the depth can be as large as n -1, as the example in Figure 4.12 shows.

## 4.2.1. Implementation

`typedef struct tree_node *tree_ptr;`

`struct tree_node`

`{`

`element_type element;`

`tree_ptr left;`

`tree_ptr right;`

`};`

`typedef tree_ptr TREE;`

#### Figure 4.13 Binary tree node declarations

Many of the rules that apply to linked lists will apply to trees as well. In particular, when an insertion is performed, a node will have to be created by a call to malloc. Nodes can be freed after deletion by calling free.

We could draw the binary trees using the rectangular boxes that are customary for linked lists, but trees are generally drawn as circles connected by lines, because they are actually graphs. We also do not explicitly draw NULL pointers when referring to trees, because every binary tree with n nodes would require n + 1 NULL pointers.

Binary trees have many important uses not associated with searching. One of the principal uses of binary trees is in the area of compiler design, which we will now explore.

## 4.2.2. Expression Trees

### Constructing an Expression Tree

We now give an algorithm to convert a postfix expression into an expression tree. Since we already have an algorithm to convert infix to postfix, we can generate expression trees from the two common types of input. The method we describe strongly resembles the postfix evaluation algorithm of Section 3.2.3. We read our expression one symbol at a time. If the symbol is an operand, we create a one-node tree and push a pointer to it onto a stack. If the symbol is an operator, we pop pointers to two trees T1 and T2 from the stack (T1 is popped first) and form a new tree whose root is the operator and whose left and right children point to T2 and T1 respectively. A pointer to this new tree is then pushed onto the stack.

As an example, suppose the input is

`a b + c d e + * *`

The first two symbols are operands, so we create one-node trees and push pointers to them onto a stack.*

*For convenience, we will have the stack grow from left to right in the diagrams.

Next, a '+' is read, so two pointers to trees are popped, a new tree is formed, and a pointer to it is pushed onto the stack.*

Next, c, d, and e are read, and for each a one-node tree is created and a pointer to the corresponding tree is pushed onto the stack.

Now a '+' is read, so two trees are merged.

Continuing, a '*' is read, so we pop two tree pointers and form a new tree with a '*' as root.

Finally, the last symbol is read, two trees are merged, and a pointer to the final tree is left on the stack.

# 4.3. The Search Tree ADT-Binary Search Trees

The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the keys in the left subtree are smaller than the key value in X, and the values of all the keys in the right subtree are larger than the key value in X. Notice that this implies that all the elements in the tree can be ordered in some consistent manner. In Figure 4.15, the tree on the left is a binary search tree, but the tree on the right is not. The tree on the right has a node with key 7 in the left subtree of a node with key 6 (which happens to be the root).

We now give brief descriptions of the operations that are usually performed on binary search trees. Note that because of the recursive definition of trees, it is common to write these routines recursively. Because the average depth of a binary search tree is O(log n), we generally do not need to worry about running out of stack space. We repeat our type definition in Figure 4.16. Since all the elements can be ordered, we will assume that the operators <, >, and = can be applied to them, even if this might be syntactically erroneous for some types.

#### Figure 4.15 Two binary trees (only the left tree is a search tree)

`typedef struct tree_node *tree_ptr;`

`struct tree_node`

`{`

`element_type element;`

`tree_ptr left;`

`tree_ptr right;`

`};`

`typedef tree_ptr SEARCH_TREE;`

## 4.3.1. Make_null

This operation is mainly for initialization. Some programmers prefer to initialize the first element as a one-node tree, but our implementation follows the recursive definition of trees more closely. It is also a simple routine, as evidenced by Figure 4.17.

## 4.3.2. Find

`SEARCH_TREE`

`make_null ( void )`

`{`

`return NULL;`

`}`

#### Figure 4.17 Routine to make an empty tree

`tree_ptr`

`find( element_type x, SEARCH_TREE T )`

`{`

`if( T == NULL )`

`return NULL;`

`if( x < T->element )`

`return( find( x, T->left ) );`

`else`

`if( x > T->element )`

`return( find( x, T->right ) );`

`else`

`return T;`

`}`

#### Figure 4.18 Find operation for binary search trees

Notice the order of the tests. It is crucial that the test for an empty tree be performed first, since otherwise the indirections would be on a NULL pointer. The remaining tests are arranged with the least likely case last. Also note that both recursive calls are actually tail recursions and can be easily removed with an assignment and a goto. The use of tail recursion is justifiable here because the simplicity of algorithmic expression compensates for the decrease in speed, and the amount of stack space used is expected to be only O(log n).

## 4.3.3. Find_min and find_max

These routines return the position of the smallest and largest elements in the tree, respectively. Although returning the exact values of these elements might seem more reasonable, this would be inconsistent with the find operation. It is important that similar-looking operations do similar things. To perform a find_min, start at the root and go left as long as there is a left child. The stopping point is the smallest element. The find_max routine is the same, except that branching is to the right child.

This is so easy that many programmers do not bother using recursion. We will code the routines both ways by doing find_min recursively and find_max nonrecursively (see Figs. 4.19 and 4.20).

Notice how we carefully handle the degenerate case of an empty tree. Although this is always important to do, it is especially crucial in recursive programs. Also notice that it is safe to change T in find_max, since we are only working with a copy. Always be extremely careful, however, because a statement such as T -> right : =T -> right -> right will make changes in most languages.

`tree_ptr`

`find_min( SEARCH_TREE T )`

`{`

`if( T == NULL )`

`return NULL;`

`else`

`if( T->left == NULL )`

`return( T );`

`else`

`return( find_min ( T->left ) );`

`}`

#### Figure 4.19 Recursive implementation of find_min for binary search trees

`tree_ptr`

`find_max( SEARCH_TREE T )`

`{`

`if( T != NULL )`

`while( T->right != NULL )`

`T = T->right;`

`return T;`

`}`

## 4.3.4. Insert

The insertion routine is conceptually simple. To insert x into tree T, proceed down the tree as you would with a find. If x is found, do nothing (or "update" something). Otherwise, insert x at the last spot on the path traversed. Figure 4.21 shows what happens. To insert 5, we traverse the tree as though a find were occurring. At the node with key 4, we need to go right, but there is no subtree, so 5 is not in the tree, and this is the correct spot.

Duplicates can be handled by keeping an extra field in the node record indicating the frequency of occurrence. This adds some extra space to the entire tree, but is better than putting duplicates in the tree (which tends to make the tree very deep). Of course this strategy does not work if the key is only part of a larger record. If that is the case, then we can keep all of the records that have the same key in an auxiliary data structure, such as a list or another search tree.

#### Figure 4.21 Binary search trees before and after inserting 5

Figure 4.22 shows the code for the insertion routine. Since T points to the root of the tree, and the root changes on the first insertion, insert is written as a function that returns a pointer to the root of the new tree. Lines 8 and 10 recursively insert and attach x into the appropriate subtree.

`tree_ptr`

`insert( element_type x, SEARCH_TREE T )`

`{`

`/*1*/       if( T == NULL )`

`{  /* Create and return a one-node tree */`

`/*2*/            T = (SEARCH_TREE) malloc ( sizeof (struct tree_node) );`

`/*3*/            if( T == NULL )`

`/*4*/                fatal_error("Out of space!!!");`

`else`

`{`

`/*5*/                T->element = x;`

`/*6*/                T->left = T->right = NULL;`

`}`

`}`

`else`

`/*7*/       if( x < T->element )`

`/*8*/            T->left = insert( x, T->left );`

`else`

`/*9*/       if( x > T->element )`

`/*10*/           T->right = insert( x, T->right );`

`/* else x is in the tree already. We'll do nothing */`

`/*11*/      return T; /* Don't forget this line!! */`

`}`

## 4.3.5. Delete

If the node is a leaf, it can be deleted immediately. If the node has one child, the node can be deleted after its parent adjusts a pointer to bypass the node (we will draw the pointer directions explicitly for clarity). See Figure 4.23. Notice that the deleted node is now unreferenced and can be disposed of only if a pointer to it has been saved.

The complicated case deals with a node with two children. The general strategy is to replace the key of this node with the smallest key of the right subtree (which is easily found) and recursively delete that node (which is now empty). Because the smallest node in the right subtree cannot have a left child, the second delete is an easy one. Figure 4.24 shows an initial tree and the result of a deletion. The node to be deleted is the left child of the root; the key value is 2. It is replaced with the smallest key in its right subtree (3), and then that node is deleted as before.

#### Figure 4.24 Deletion of a node (2) with two children, before and after

The code in Figure 4.25 performs deletion. It is inefficient, because it makes two passes down the tree to find and delete the smallest node in the right subtree when this is appropriate. It is easy to remove this inefficiency, by writing a special delete_min function, and we have left it in only for simplicity.

`tree_ptr`

`delete( element_type x, SEARCH_TREE T )`

`{`

`tree_ptr tmp_cell, child;`

`if( T == NULL )`

`error("Element not found");`

`else`

`if( x < T->element )  /* Go left */`

`T->left = delete( x, T->left );`

`else`

`if( x > T->element )  /* Go right */`

`T->right = delete( x, T->right );`

`else      /* Found element to be deleted */`

`if( T->left && T->right )  /* Two children */`

`{      /* Replace with smallest in right subtree */`

`tmp_cell = find_min( T->right );`

`T->element = tmp_cell->element;`

`T->right = delete( T->element, T->right );`

`}`

`else      /* One child */`

`}`

`tmp_cell = T;`

`if( T->left == NULL )      /* Only a right child */`

`child = T->right;`

`if( T->right == NULL )     /* Only a left child */`

`child = T->left;`

`free( tmp_cell );`

`return child;`

`}`

`return T;`

`}`

## 4.3.6. Average-Case Analysis

We prove in this section that the average depth over all nodes in a tree is O(log n) on the assumption that all trees are equally likely.

The sum of the depths of all nodes in a tree is known as the internal path length. We will now calculate the average internal path length of a binary search tree, where the average is taken over all possible binary search trees.

Let D(n) be the internal path length for some tree T of n nodes. D(1) = 0. An n-node tree consists of an i-node left subtree and an (n - i - 1)-node right subtree, plus a root at depth zero for 0 i < n. D(i) is the internal path length of the left subtree with respect to its root. In the main tree, all these nodes are one level deeper. The same holds for the right subtree. Thus, we get the recurrence

`D(n) = D(i) + D(n - i -1) + n -1`

If all subtree sizes are equally likely, which is true for binary search trees (since the subtree size depends only on the relative rank of the first element inserted into the tree), but not binary trees, then the average value of both D(i) and D(n - i -1) is . This yields

This recurrence will be encountered and solved in Chapter 7, obtaining an average value of D(n) = O(n log n). Thus, the expected depth of any node is O(log n). As an example, the randomly generated 500-node tree shown in Figure 4.26 has nodes at expected depth 9.98.

It is tempting to say immediately that this result implies that the average running time of all the operations discussed in the previous section is O(log n), but this is not entirely true. The reason for this is that because of deletions, it is not clear that all binary search trees are equally likely. In particular, the deletion algorithm described above favors making the left subtrees deeper than the right, because we are always replacing a deleted node with a node from the right subtree. The exact effect of this strategy is still unknown, but it seems only to be a theoretical novelty. It has been shown that if we alternate insertions and deletions (n2) times, then the trees will have an expected depth of . After a quarter-million random insert/delete pairs, the tree that was somewhat right-heavy in Figure 4.26 looks decidedly unbalanced (average depth = 12.51). See Figure 4.27.

#### Figure 4.26 A randomly generated binary search tree

We could try to eliminate the problem by randomly choosing between the smallest element in the right subtree and the largest in the left when replacing the deleted element. This apparently eliminates the bias and should keep the trees balanced, but nobody has actually proved this. In any event, this phenomenon appears to be mostly a theoretical novelty, because the effect does not show up at all for small trees, and stranger still, if o(n2) insert/delete pairs are used, then the tree seems to gain balance!

#### Figure 4.27 Binary search tree after O(n2) insert/delete pairs

The main point of this discussion is that deciding what "average" means is generally extremely difficult and can require assumptions which may or may not be valid. In the absence of deletions, or when lazy deletion is used, it can be shown that all binary search trees are equally likely and we can conclude that the average running times of the operations above are O(log n). Except for strange cases like the one discussed above, this result is very consistent with observed behavior.

There are quite a few general algorithms to implement balanced trees. Most are quite a bit more complicated than a standard binary search tree, and all take longer on average. They do, however, provide protection against the embarrassingly simple cases. Below, we will sketch one of the oldest forms of balanced search trees, the AVL tree.

# 4.4. AVL Trees

#### Figure 4.28 A bad binary tree. Requiring balance at the root is not enough.

Another balance condition would insist that every node must have left and right subtrees of the same height. If the height of an empty subtree is defined to be -1 (as is usual), then only perfectly balanced trees of 2k - 1 nodes would satisfy this criterion. Thus, although this guarantees trees of small depth, the balance condition is too rigid to be useful and needs to be relaxed.

An AVL tree is identical to a binary search tree, except that for every node in the tree, the height of the left and right subtrees can differ by at most 1. (The height of an empty tree is defined to be -1.) In Figure 4.29 the tree on the left is an AVL tree, but the tree on the right is not. Height information is kept for each node (in the node structure). It is easy to show that the height of an AVL tree is at most roughly 1.44 log(n + 2) - .328, but in practice it is about log(n + 1) + 0.25 (although the latter claim has not been proven). As an example, the AVL tree of height 9 with the fewest nodes (143) is shown in Figure 4.30. This tree has as a left subtree an AVL tree of height 7 of minimum size. The right subtree is an AVL tree of height 8 of minimum size. This tells us that the minimum number of nodes, N(h), in an AVL tree of height h is given by N(h) = N(h -1) + N(h - 2) + 1. For h = 0, N(h) = 1. For h = 1, N(h) = 2. The function N(h) is closely related to the Fibonacci numbers, from which the bound claimed above on the height of an AVL tree follows.

Thus, all the tree operations can be performed in O(log n) time, except possibly insertion (we will assume lazy deletion). When we do an insertion, we need to update all the balancing information for the nodes on the path back to the root, but the reason that insertion is potentially difficult is that inserting a node could violate the AVL tree property. (For instance, inserting into the AVL tree in Figure 4.29 would destroy the balance condition at the node with key 8.) If this is the case, then the property has to be restored before the insertion step is considered over. It turns out that this can always be done with a simple modification to the tree, known as a rotation. We describe rotations in the following section.

## 4.4.1. Single Rotation

The two trees in Figure 4.31 contain the same elements and are both binary search trees. First of all, in both trees k1 < k2. Second, all elements in the subtree X are smaller than k1 in both trees. Third, all elements in subtree Z are larger than k2. Finally, all elements in subtree Y are in between k1 and k2. The conversion of one of the above trees to the other is known as a rotation. A rotation involves only a few pointer changes (we shall see exactly how many later), and changes the structure of the tree while preserving the search tree property.

#### Figure 4.32 AVL property destroyed by insertion of , then fixed by a rotation

Let us work through a rather long example. Suppose we start with an initially empty AVL tree and insert the keys 1 through 7 in sequential order. The first problem occurs when it is time to insert key 3, because the AVL property is violated at the root. We perform a single rotation between the root and its right child to fix the problem. The tree is shown in the following figure, before and after the rotation:

To make things clearer, a dashed line indicates the two nodes that are the subject of the rotation. Next, we insert the key 4, which causes no problems, but the insertion of 5 creates a violation at node 3, which is fixed by a single rotation. Besides the local change caused by the rotation, the programmer must remember that the rest of the tree must be informed of this change. Here, this means that 2's right child must be reset to point to 4 instead of 3. This is easy to forget to do and would destroy the tree (4 would be inaccessible).

Next, we insert 6. This causes a balance problem for the root, since its left subtree is of height 0, and its right subtree would be height 2. Therefore, we perform a single rotation at the root between 2 and 4.

The rotation is performed by making 2 a child of 4 and making 4's original left subtree the new right subtree of 2. Every key in this subtree must lie between 2 and 4, so this transformation makes sense. The next key we insert is 7, which causes another rotation.

## 4.4.2. Double Rotation

As the diagram shows, the single rotation has not fixed the height imbalance. The problem is that the height imbalance was caused by a node inserted into the tree containing the middle elements (tree Y in Fig. 4.31) at the same time as the other trees had identical heights. The case is easy to check for, and the solution is called a double rotation, which is similar to a single rotation but involves four subtrees instead of three. In Figure 4.33, the tree on the left is converted to the tree on the right. By the way, the effect is the same as rotating between k1 and k2 and then between k2 and k3. There is a symmetric case, which is also shown (see Fig. 4.34).

#### Figure 4.34 (Left-right) double rotation

In our example, the double rotation is a right-left double rotation and involves 7, 15, and 14. Here, k3 is the node with key 7, k1 is the node with key 15, and k2 is the node with key 14. Subtrees A, B, C, and D are all empty.

If 12 is now inserted, there is an imbalance at the root. Since 12 is not between 4 and 7, we know that the single rotation will work.

Insertion of 11 will require a single rotation:

To insert 10, a single rotation needs to be performed, and the same is true for the subsequent insertion of 9. We insert 8 without a rotation, creating the almost perfectly balanced tree that follows.

Finally, we insert to show the symmetric case of the double rotation. Notice that causes the node containing 9 to become unbalanced. Since is between 9 and 8 (which is 9's child on the path to , a double rotation needs to be performed, yielding the following tree.

The reader can verify that any imbalance caused by an insertion into an AVL tree can always be fixed by either a single or double rotation. The programming details are fairly straightforward, except that there are several cases. To insert a new node with key x into an AVL tree T, we recursively insert x into the appropriate subtree of T (let us call this Tlr). If the height of Tlr does not change, then we are done. Otherwise, if a height imbalance appears in T, we do the appropriate single or double rotation depending on x and the keys in T and Tlr, update the heights (making the connection from the rest of the tree above), and are done. Since one rotation always suffices, a carefully coded nonrecursive version generally turns out to be significantly faster than the recursive version. However, nonrecursive versions are quite difficult to code correctly, so many programmers implement AVL trees recursively.

With all this, we are ready to write the AVL routines. We will do only a partial job and leave the rest as an exercise. First, we need the declarations. These are given in Figure 4.35. We also need a quick function to return the height of a node. This function is necessary to handle the annoying case of a NULL pointer. This is shown in Figure 4.36. The basic insertion routine is easy to write, since it consists mostly of function calls (see Fig. 4.37).

`typedef struct avl_node *avl_ptr;`

`struct avl_node`

`{`

`element_type element;`

`avl_ptr left;`

`avl_ptr right;`

`int height;`

`};`

`typedef avl_ptr SEARCH_TREE;`

#### Figure 4.35 Node declaration for AVL trees

`int`

`height( avl_ptr p )`

`{`

`if( p == NULL )`

`return -1;`

`else`

`return p->height;`

`}`

#### Figure 4.36 Function to compute height of an AVL node

For the trees in Figure 4.38, s_rotate_left converts the tree on the left to the tree on the right, returning a pointer to the new root. s_rotate_right is symmetric. The code is shown in Figure 4.39.

The last function we will write will perform the double rotation pictured in Figure 4.40, for which the code is shown in Figure 4.41.

# 4.5. Splay Trees

Splay trees are based on the fact that the O(n) worst-case time per operation for binary search trees is not bad, as long at it occurs relatively infrequently. Any one access, even if it takes O(n), is still likely to be extremely fast. The problem with binary search trees is that it is possible, and not uncommon, for a whole sequence of bad accesses to take place. The cumulative running time then becomes noticeable. A search tree data structure with O(n) worst-case time, but a guarantee of at most O(m log n) for any m consecutive operations, is certainly satisfactory, because there are no bad sequences.

If any particular operation is allowed to have an O(n) worst-case time bound, and we still want an O(log n) amortized time bound, then it is clear that whenever a node is accessed, it must be moved. Otherwise, once we find a deep node, we could keep performing finds on it. If the node does not change location, and each access costs O(n), then a sequence of m accesses will cost O(m n).

`SEARCH_TREE`

`insert( element_type x, SEARCH_TREE T )`

`{`

`return insert1( x, T, NULL );`

`}`

`SEARCH_TREE`

`insert1( element_type x, SEARCH_TREE T, avl_ptr parent )`

`{`

`avl_ptr rotated_tree;`

`if( T == NULL )`

`{  /* Create and return a one-node tree */`

`T = (SEARCH_TREE) malloc ( sizeof (struct avl_node) );`

`if( T == NULL )`

`fatal_error("Out of space!!!");`

`else`

`{`

`T->element = x; T->height = 0;`

`T->left = T->right = NULL;`

`}`

`}`

`else`

`{`

`if( x < T->element )`

`{`

`T->left = insert1( x, T->left, T );`

`if( ( height( T->left ) - height( T->right ) ) == 2`

`{`

`if( x < T->left->element )`

`rotated_tree = s_rotate_left( T );`

`else`

`rotated_tree = d_rotate_left( T );`

`if( parent->left == T )`

`parent->left = rotated_tree;`

`else`

`parent->right = rotated_tree;`

`}`

`else`

`T->height = max( height(T->left), height(T->right) ) + 1;`

`}`

`else`

`/* Symmetric Case for right subtree */;`

`/* Else x is in the tree already. We'll do nothing */`

`}`

`return T;`

`}`

#### Figure 4.38

`/* This function can be called only if k2 has a left child. */`

`/* Perform a rotate between a node (k2) and its left child. */`

`/* Update heights. */`

`/* Then return new root. */`

`avl_ptr`

`s_rotate_left( avl_ptr k2 )`

`{`

`avl_ptr k1;`

`k1 = k2->left;`

`k2->left = k1->right;`

`k1->right = k2;`

`k2->height = max( height(k2->left), height(k2->right) ) + 1;`

`k1->height = max( height(k1->left), k2->height ) + 1;`

`return k1;  /* New root */`

`}`

#### Figure 4.40

`/* This function can be called only if k3 has a left child */`

`/* and k3's left child has a right child */`

`/* Do the left-right double rotation. Update heights */`

`avl_ptr`

`d_rotate_left( avl_ptr k3 )`

`{`

`/* rotate between k1 and k2 */`

`k3->left = s_rotate_right( k3->left );`

`/* rotate between k3 and k2 */`

`return( s_rotate_left( k3 ) );`

`}`

## 4.5.1. A Simple Idea (That Does Not Work)

The access path is dashed. First, we would perform a single rotation between k1 and its parent, obtaining the following tree.

Then, we rotate between k1 and k3, obtaining the next tree.

Then two more rotations are performed until we reach the root.

These rotations have the effect of pushing k1 all the way to the root, so that future accesses on k1 are easy (for a while). Unfortunately, it has pushed another node (k3) almost as deep as k1 used to be. An access on that node will then push another node deep, and so on. Although this strategy makes future accesses of k1 cheaper, it has not significantly improved the situation for the other nodes on the (original) access path. It turns out that it is possible to prove that using this strategy, there is a sequence of m operations requiring (m n) time, so this idea is not quite good enough. The simplest way to show this is to consider the tree formed by inserting keys 1, 2, 3, . . . , n into an initially empty tree (work this example out). This gives a tree consisting of only left children. This is not necessarily bad, though, since the time to build this tree is O(n) total. The bad part is that accessing the node with key 1 takes n -1 units of time. After the rotations are complete, an access of the node with key 2 takes n - 2 units of time. The total for accessing all the keys in order is . After they are accessed, the tree reverts to its original state, and we can repeat the sequence.

## 4.5.2. Splaying

The splaying strategy is similar to the rotation idea above, except that we are a little more selective about how rotations are performed. We will still rotate bottom up along the access path. Let x be a (nonroot) node on the access path at which we are rotating. If the parent of x is the root of the tree, we merely rotate x and the root. This is the last rotation along the access path. Otherwise, x has both a parent (p) and a grandparent (g), and there are two cases, plus symmetries, to consider. The first case is the zig-zag case (see Fig. 4.42). Here x is a right child and p is a left child (or vice versa). If this is the case, we perform a double rotation, exactly like an AVL double rotation. Otherwise, we have a zig-zig case: x and p are either both left children or both right children. In that case, we transform the tree on the left of Figure 4.43 to the tree on the right.

#### Figure 4.43 Zig-zig

As an example, consider the tree from the last example, with a find on k1:

The first splay step is at k1, and is clearly a zig-zag, so we perform a standard AVL double rotation using k1, k2, and k3. The resulting tree follows.

The next splay step at k1 is a zig-zig, so we do the zig-zig rotation with k1, k4, and k5, obtaining the final tree.

Although it is hard to see from small examples, splaying not only moves the accessed node to the root, but also has the effect of roughly halving the depth of most nodes on the access path (some shallow nodes are pushed down at most two levels).

#### Figure 4.44 Result of splaying at node 1

To see the difference that splaying makes over simple rotation, consider again the effect of inserting keys 1, 2, 3, . . . , n into an initially empty tree. This takes a total of O(n), as before, and yields the same tree as simple rotations. Figure 4.44 shows the result of splaying at the node with key 1. The difference is that after an access of the node with key 1, which takes n -1 units, the access on the node with key 2 will only take about n/2 units instead of n - 2 units; there are no nodes quite as deep as before.

#### Figure 4.46 Result of splaying previous tree at node 2

An access on the node with key 2 will bring nodes to within n/4 of the root, and this is repeated until the depth becomes roughly log n (an example with n = 7 is too small to see the effect well). Figures 4.45 to 4.53 show the result of accessing keys 1 through 9 in a 32-node tree that originally contains only left children. Thus we do not get the same bad behavior from splay trees that is prevalent in the simple rotation strategy. (Actually, this turns out to be a very good case. A rather complicated proof shows that for this example, the n accesses take a total of O(n) time).

#### Figure 4.53 Result of splaying previous tree at node 9

The type declarations (Fig. 4.54) are simple to understand. The splaying routine (Fig. 4.55) takes as argument the last node on the accessed path and makes it the new root. The routines single_rotate and double_rotate choose the correct type of rotation. We provide the code for single_rotate in Figure 4.56.

The rotation routines are similar to the AVL rotations, except that the parent pointers must be maintained. Some sample routines are in the figures that follow. Since zig rotations always make x the new root, we know that x will have no parent after the operation. The code for this is in Figure 4.57.

Zig-zigs and Zig-zags are similar. We will write the one routine to perform the zig-zig splay when both x and p are left children. One way to do this is to write a single_rotate routine that includes pointer changes for the parent, and then implement the complex rotations with two single rotations. This is the way we coded the AVL routines. We have taken a different approach in Figure 4.58 to show the diversity of styles available. See Figure 4.59. You should try to code the other cases yourself; it will be excellent pointer manipulation practice.

`typedef struct splay_node *splay_ptr;`

`struct splay_node`

`{`

`element_type element;`

`splay_ptr left;`

`splay-ptr right;`

`splay-ptr parent;`

`};`

`typedef splay_ptr SEARCH_TREE;`

#### Figure 4.54 Type declarations for splay trees

`void`

`splay( splay_ptr current )`

`{`

`splay_ptr father;`

`father = current->parent;`

`while( father != NULL )`

`{`

`if( father->parent == NULL )`

`single_rotate (current );`

`else`

`double_rotate( current );`

`father = current->parent;`

`}`

`}`

#### Figure 4.55 Basic splay routine

`void`

`single_rotate( splay_ptr x )`

`{`

`if( x->parent->left == x)`

`zig_left( x );`

`else`

`zig_right( x );`

`}`

#### Figure 4.56 Single rotation

`void`

`zig_left( splay_ptr x )`

`{`

`splay ptr p, B;`

`p = x->parent;`

`B = x->right;`

`x->right = p;      /* x's new right child is p*/`

`x->parent = NULL;  /* x will now be a root */`

`if( B != NULL )`

`B->parent = p;`

`p->left = B;`

`p->parent = x;`

`}`

#### Figure 4.58

`void`

`zig_zig_left( splay_ptr x )`

`{`

`splay_ptr p, g, B, C, ggp;`

`p = x->parent;`

`g = p->parent;`

`B = x->right;`

`C = p->right;`

`ggp = g->parent;`

`x->right = p;           /* x's new right child is p*/`

`p->parent = x;`

`p->right = g;           /* p's new right child is g */`

`g->parent = p;`

`if( B != NULL )         /* p's new left child is subtree B */`

`B->parent = p;`

`p->left = B;`

`if( C != NULL )         /* g's new left child is subtree C */`

`C->parent = g;`

`g->left = C;`

`x->parent = ggp;        /* connect to rest of the tree */`

`if( ggp ! = NULL )`

`if( gpp->left == g )`

`ggp->left = x;`

`else`

`ggp->right = x;`

`}`

# 4.6. Tree Traversals (Revisited)

`void`

`print_tree( SEARCH_TREE T )`

`{`

`if( T != NULL )`

`{`

`print_tree( T->left );`

`print_element( T->element );`

`print_tree( T->right );`

`}`

`}`

#### Figure 4.60 Routine to print a binary search tree in order

Sometimes we need to process both subtrees first before we can process a node. For instance, to compute the height of a node, we need to know the height of the subtrees first. The code in Figure 4.61 computes this. Since it is always a good idea to check the special cases - and crucial when recursion is involved - notice that the routine will declare the height of a leaf to be zero, which is correct. This general order of traversal, which we have also seen before, is known as a postorder traversal. Again, the total running time is O(n), because constant work is performed at each node.

`int`

`height( TREE T )`

`{`

`if( T == NULL )`

`return -1;`

`else`

`return ( max( height(T->left), height(T->right) ) + 1 );`

`}`

# 4.7. B-Trees

A B-tree of order m is a tree with the following structural properties:

The root is either a leaf or has between 2 and m children.

All nonleaf nodes (except the root) have between m/2 and m children.

All leaves are at the same depth.

All data is stored at the leaves. Contained in each interior node are pointers p1, p2, . . . , pm to the children, and values k1, k2, . . . , km - 1, representing the smallest key found in the subtrees p2, p3, . . . , pm respectively. Of course, some of these pointers might be NULL, and the corresponding ki would then be undefined. For every node, all the keys in subtree p1 are smaller than the keys in subtree p2, and so on. The leaves contain all the actual data, which is either the keys themselves or pointers to records containing the keys. We will assume the former to keep our examples simple. There are various definitions of B-trees that change this structure in mostly minor ways, but this definition is one of the popular forms. We will also insist (for now) that the number of keys in a leaf is also between m/2 and m.

The tree in Figure 4.62 is an example of a B-tree of order 4.

#### Figure 4.62 B-tree of order 4

We have drawn interior nodes (nonleaves) in ellipses, which contain the two pieces of data for each node. A dash line as a second piece of information in an interior node indicates that the node has only two children. Leaves are drawn in boxes, which contain the keys. The keys in the leaves are ordered. To perform a find, we start at the root and branch in one of (at most) three directions, depending on the relation of the key we are looking for to the two (possibly one) values stored at the node.

To perform an insert on a previously unseen key, x, we follow the path as though we were performing a find. When we get to a leaf node, we have found the correct place to put x. Thus, to insert a node with key 18, we can just add it to a leaf without causing any violations of the 2-3 tree properties. The result is shown in the following figure.

Unfortunately, since a leaf can hold only two or three keys, this might not always be possible. If we now try to insert 1 into the tree, we find that the node where it belongs is already full. Placing our new key into this node would give it a fourth element which is not allowed. This can be solved by making two nodes of two keys each and adjusting the information in the parent.

Unfortunately, this idea does not always work, as can be seen by an attempt to insert 19 into the current tree. If we make two nodes of two keys each, we obtain the following tree.

This tree has an internal node with four children, but we only allow three per node. The solution is simple. We merely split this node into two nodes with two children. Of course, this node might be one of three children itself, and thus splitting it would create a problem for its parent (which would now have four children), but we can keep on splitting nodes on the way up to the root until we either get to the root or find a node with only two children. In our case, we can get by with splitting only the first internal node we see, obtaining the following tree.

If we now insert an element with key 28, we create a leaf with four children, which is split into two leaves of two children:

This creates an internal node with four children, which is then split into two children. What we have done here is split the root into two nodes. When we do this, we have a special case, which we finish by creating a new root. This is how (the only way) a 2-3 tree gains height.

Notice also that when a key is inserted, the only changes to internal nodes occur on the access path. These changes can be made in time proportional to the length of this path, but be forewarned that there are quite a few cases to handle, and it is easy to do this wrong.

There are other ways to handle the case where a node becomes overloaded with children, but the method we have described is probably the simplest. When attempting to add a fourth key to a leaf, instead of splitting the node into two we can first attempt to find a sibling with only two keys. For instance, to insert 70 into the tree above, we could move 58 to the leaf containing 41 and 52, place 70 with 59 and 61, and adjust the entries in the internal nodes. This strategy can also be applied to internal nodes and tends to keep more nodes full. The cost of this is slightly more complicated routines, but less space tends to be wasted.

We can perform deletion by finding the key to be deleted and removing it. If this key was one of only two keys in a node, then its removal leaves only one key. We can fix this by combining this node with a sibling. If the sibling has three keys, we can steal one and have both nodes with two keys. If the sibling has only two keys, we combine the two nodes into a single node with three keys. The parent of this node now loses a child, so we might have to percolate this strategy all the way to the top. If the root loses its second child, then the root is also deleted and the tree becomes one level shallower. As we combine nodes, we must remember to update the information kept at the internal nodes.

With general B-trees of order m, when a key is inserted, the only difficulty arises when the node that is to accept the key already has m keys. This key gives the node m + 1 keys, which we can split into two nodes with (m + 1) / 2 and (m + 1) / 2 keys respectively. As this gives the parent an extra node, we have to check whether this node can be accepted by the parent and split the parent if it already has m children. We repeat this until we find a parent with less than m children. If we split the root, we create a new root with two children.

The depth of a B-tree is at most logm/2n. At each node on the path, we perform O(log m) work to determine which branch to take (using a binary search), but an insert or delete could require O(m) work to fix up all the information at the node. The worst-case running time for each of the insert and delete operations is thus O(m logm n) = O( (m / log m ) log n), but a find takes only O(log n ). The best (legal) choice of m for running time considerations has been shown empirically to be either m = 3 or m = 4; this agrees with the bounds above, which show that as m gets larger, the insertion and deletion times increase. If we are only concerned with main memory speed, higher order B-trees, such as 5-9 trees, are not an advantage.

The real use of B-trees lies in database systems, where the tree is kept on a physical disk instead of main memory. Accessing a disk is typically several orders of magnitude slower than any main memory operation. If we use a B-tree of order m, then the number of disk accesses is O(logm n). Although each disk access carries the overhead of O(log m) to determine the direction to branch, the time to perform this computation is typically much smaller than the time to read a block of memory and can thus be considered inconsequential (as long as m is chosen reasonably). Even if updates are performed and O(m) computing time is required at each node, this too is generally not significant. The value of m is then chosen to be the largest value that still allows an interior node to fit into one disk block, and is typically in the range 32 m 256. The maximum number of elements that are stored in a leaf is chosen so that if the leaf is full, it fits in one block. This means that a record can always be found in very few disk accesses, since a typical B-tree will have a depth of only 2 or 3, and the root (and possibly the first level) can be kept in main memory.

Analysis suggests that a B-tree will be ln 2 = 69 percent full. Better space utilization can be obtained if, instead of always splitting a node when the tree obtains its (m + 1)th entry, the routine searches for a sibling that can take the extra child. The details can be found in the references.

# Summary

Search trees are of great importance in algorithm design. They support almost all the useful operations, and the logarithmic average cost is very small. Nonrecursive implementations of search trees are somewhat faster, but the recursive versions are sleeker, more elegant, and easier to understand and debug. The problem with search trees is that their performance depends heavily on the input being random. If this is not the case, the running time increases significantly, to the point where search trees become expensive linked lists.

We saw several ways to deal with this problem. AVL trees work by insisting that all nodes' left and right subtrees differ in heights by at most one. This ensures that the tree cannot get too deep. The operations that do not change the tree, as insertion does, can all use the standard binary search tree code. Operations that change the tree must restore the tree. This can be somewhat complicated, especially in the case of deletion. We showed how to restore the tree after insertions in O(log n) time.

We also examined the splay tree. Nodes in splay trees can get arbitrarily deep, but after every access the tree is adjusted in a somewhat mysterious manner. The net effect is that any sequence of m operations takes O(m log n) time, which is the same as a balanced tree would take.

In practice, the running time of all the balanced tree schemes is worse (by a constant factor) than the simple binary search tree, but this is generally acceptable in view of the protection being given against easily obtained worst-case input.

# Exercises

a. Which node is the root?

b. Which nodes are leaves?

#### Figure 4.63

a. Name the parent node.

b. List the children.

c. List the siblings.

d. Compute the depth.

e. Compute the height.

b. Show the result of deleting the root.

#### Figure 4.64 Tree for Exercise 4.8

a. Explain how to generate a random integer between 1 and m that is not already in the tree (so a random insert can be performed). In terms of n and , what is the running time of this operation?

b. Explain how to generate a random integer between 1 and m that is already in the tree (so a random delete can be performed). What is the running time of this operation?

c. What is a good choice of ? Why?

a. Replace with the largest node, X, in TL and recursively delete X.

b. Alternately replace with the largest node in TL and the smallest node in TR, and recursively delete appropriate node.

c. Replace with either the largest node in TL or the smallest node in TR (recursively deleting the appropriate node), making the choice randomly. Which strategy seems to give the most balance? Which takes the least CPU time to process the entire sequence?

b. What is the minimum number of nodes in an AVL tree of height 15?

b. What is the smallest AVL tree that overflows an 8-bit height counter?

#### Figure 4.65

a. What is the internal path length of the tree (exactly)?

*b. Calculate the internal path length after each of find(1), find(2), find(3), find(4), find(5), find(6).

*c. If the sequence of successive finds is continued, when is the internal path length minimized?

**b. Show that if all nodes in a splay tree are accessed in sequential order, then the total access time is O(n), regardless of the initial tree.

a. the number of nodes in T

b. the number of leaves in T

c. the number of full nodes in T

What is the running time of your routines?

a. The x coordinate can be computed by assigning the inorder traversal number. Write a routine to do this for each node in the tree.

b. The y coordinate can be computed by using the negative of the depth of the node. Write a routine to do this for each node in the tree.

c. In terms of some imaginary unit, what will the dimensions of the picture be? How can you adjust the units so that the tree is always roughly two-thirds as high as it is wide?

d. Prove that using this system no lines cross, and that for any node, X, all elements in X's left subtree appear to the left of X and all elements in X's right subtree appear to the right of X.

a. circle(x, y)

b. drawline(i, j)

The first instruction draws a circle at (x, y), and the second instruction connects the ith circle to the jth circle (circles are numbered in the order drawn). You should either make this a program and define some sort of input language or make this a function that can be called from any program. What is the running time of your routine?

b. Show the result of deleting 0 and then 9 from the 2-3 tree created in part (a).

*b. Write a routine to perform deletion from a B-tree. When a key is deleted, is it necessary to update information in the internal nodes?

#### Figure 4.66 Tree for Exercise 4.39

*c. Modify your insertion routine so that if an attempt is made to add into a node that already has m entries, a search is performed for a sibling with less than m children before the node is split.

4.39 Show how the tree in Figure 4.66 is represented using a child/sibling pointer implementation.

4.42 Two trees, T1 and T2, are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1. For instance, the two trees in Figure 4.67 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped.

a. Give a polynomial time algorithm to decide if two trees are isomorphic.

*b. What is the running time of your program (there is a linear solution)?

*b. Give an algorithm to perform this transformation using O(n log n) rotations on average.

**c. Show that this transformation can be done with O(n) rotations, worst-case.

#### Figure 4.67 Two isomorphic trees

a. How can we distinguish threads from real children pointers?

b. Write routines to perform insertion and deletion into a tree threaded in the manner described above.

a. One method is to build two separate binary search trees. How many extra pointers does this require?

b. An alternative method is a 2-d tree. A 2-d tree is similar to a binary search tree, except that branching at even levels is done with respect to key1, and branching at odd levels is done with key2. Figure 4.68 shows a 2-d tree, with the first and last names as keys, for post-WWII presidents. The presidents' names were inserted chronologically (Truman, Eisenhower, Kennedy, Johnson, Nixon, Ford, Carter, Reagan, Bush). Write a routine to perform insertion into a 2-d tree.

c. Write an efficient procedure that prints all records in the tree that simultaneously satisfy the constraints low1 key1 high1 and low2 key2 high2.

# References

Several papers deal with the lack of balance caused by biased deletion algorithms in binary search trees. Hibbard's paper [20] proposed the original deletion algorithm and established that one deletion preserves the randomness of the trees. A complete analysis has been performed only for trees with three [21] and four nodes[5]. Eppinger's paper [15] provided early empirical evidence of nonrandomness, and the papers by Culberson and Munro, [11], [12], provide some analytical evidence (but not a complete proof for the general case of intermixed insertions and deletions).

AVL trees were proposed by Adelson-Velskii and Landis [1]. Simulation results for AVL trees, and variants in which the height imbalance is allowed to be at most k for various values of k, are presented in [22]. A deletion algorithm for AVL trees can be found in [24]. Analysis of the averaged depth of AVL trees is incomplete, but some results are contained in [25].

[3] and [9] considered self-adjusting trees like the type in Section 4.5.1. Splay trees are described in [29].

B-trees first appeared in [6]. The implementation described in the original paper allows data to be stored in internal nodes as well as leaves. The data structure we have described is sometimes known as a B+ tree. A survey of the different types of B-trees is presented in [10]. Empirical results of the various schemes is reported in [18]. Analysis of 2-3 trees and B-trees can be found in [4], [14], and [33].