Chapter Seven Trees 7.1 “INTRODUCTION So far, we have been studying mainly linear types of data structures: strings, arrays, lists, stacks and queues. This chapter defines a nonlinear data structure called a tree, This structure is mainly tised to represent data containing a hierarchical relationship between elements, e.g, records, family trees and tables of contents. First we investigate a special kind of tree, cal in the computer. Although such a tree may seem to chapter that more general trees may be viewed as binary trees led a binary tree, which can be easily maintained be very restrictive, we will see later in the 7.2— BINARY TREES A binary tree T is defined as a finite set of elements, called nodes, such that: (a) Tis empty (called the mull tree or empty tree), oF (6) contains a distinguished node R, called the root of T. and the remaining nodes of T form ‘an ordered pair of disjoint binary trees 7, and T, IFT does contain a root R, then the two trees T, and 7p are called, respectively, the left and right wburees of Rif T, is nonempty, then its root is called the left successor of R; similarly, if Tis onempty, then its root is called the right successor of R TA binay tree T is frequently presented by means of a diagram. Specifically, the diagram in Fig, 71 represents a binary tree T as follows. (i) T consists of 11 nodes, represented by the letters ‘A through L, excluding I, (ii) The root of T is the node 4 at the top of the diagram. (ii) A left-72 |. Data Structures Fig. 7.4 downward slanted line from a node N indicates a left successor of NV, and a right-downward slanted line from N indicates a right successor of N. Observe that: (a) Bisa left successor and C is a right successor of the node A. ; (b) The left subtree of the root A consists of the nodes B, D, E and F, and the right subtree of A consists of the nodes C, G. H, J, K and L. Any node V in a binary tree T has either 0, | or 2 successors. The nodes A, B, C and H have two successors, the nodes E and J have only one successor, and the nodes D, F, G, L and K have no successors. The nodes with no successors are called terminal nodes. The above definition of the binary tree T is recursive since T is defined in terms of the binary subtrees T, and T;, This means, in particular, that every node N of T contains a left and a right subtree. Moreover, if N is a terminal node, then both its left and right subtrees are empty. Binary trees T and T’ are said to be similar if they have the same structure or, in other words, if they have the same shape. The trees are said to be copies if they are similar and if they have the same contents at corresponding nodes. Example 7.1 | | Consider the four binary trees in Fig. 7.2. The three trees (a), (c) and (d) are similar. In particular, the trees (a) and (c) are copies since they also have the same data at corresponding nodes. The tree (b) is neither similar nor a copy of the tree (d) because, in a binary tree, we distinguish between a left successor and a right succes- sor even when there is only one successor. A & A \, “oo A Ls © £™ YN @) ) © ey73 Trees Example 7.2 Algebraic Expressions ression E involving only binary operations, such as Ex (a-b) A(c*d) +e) E can be represented by means of the binary tree T pictured in Fig. 7.3. That is each caithle: or constant in E appears as an “internal” node in T whose left and right Subtrees correspond to the operands of the operation. For examptz: (a) In the expression £, the operands of + are c*d and @ (b) In the tree T, the subtrees of the node + correspond to the subex | aN, fs JN /\ . Fig. 7.3. £ = (a ~ 6)/((c*d) + @) Consider any algebraic exp pressions c#d Clearly every algebraic expression will correspond to a unique tree, Términology ‘Terminology describing family relationships is frequently used to describe relationships between the nodes of a tree T. Specifically, suppose N is anode in T with left successor S; and right successor Ss, Then Vis called the parent (or father) of S, and S;. Analogously, S; is called the left child (or son) of N, and Sp is called the right child (or son) of N. Furthermore, 5; and S, are said to te siblings (or brothers). Every node N in a binary tree T, except the root, has @ unique parent, called the predecessor of N. The terms descendant and ancestor have their usual meaning, That is, a node L is called a descendant of a node NV (and N is called an ancestor of L) if there is a succession of children from N to L. In particular, L is called a left or right descendant of N according to whether L belongs to the left or right subtree of NV. “Terminology from graph theory and horticulture is also used with a binary tree 7. Specifically, the line drawn from a node N of T'to a successor is called an, edge, and a sequence of consecutive edges is called a path. A terminal node is called a leaf, and a path ending in a leaf is called a branch. Each node in a binary tree T is assigned a level number, as follows. The root R of the tree T is assigned the level number 0, and every other node is assigned a level number which is 1 more than and vice versa.peta Stwctrs the level number of its parent. Furthermore, those nodes with # belong to the same generation. The depth (or height) of a tree T is th he same level number are said to ¢ maximum number of nodes in a branch of i This turns out to be 1 more than the largest level number of 7. The tree 7 in Fig. 7-1 has depth 5. words i Binary trees T and 1” are said to be similar if they have the same structure of it 0 ieY WEA they have the same shape. The trees are said to be copies if they are similar and if they fe contents at corresponding nodes. omplete Binary Trees Consider any binary tree J: Bach node of T can have at most two children. Accordingly, one can show that level r of T can have at most 2" nodes. The tree T is said to be complete if all its-levels, except possibly the last, have the maximum number of possible nodes, and if all the nodes at the last level appear as far left as possible. Thus there is a unique complete tree T, with exactly n nodes (we are, of course, igndring the contents of the nodes). The complete tree Ts with 26 nodes appears in Fig. 7.4. 5, LN, \ fy o™. VLAN ad 324 25 6 7.4 Complete Tree Tog The nodes of the complete binary tree Tyg in Fig. 7.4 have been purposely labeled by the integers 1, 2, .... 26, from left to right, generation by generation. With this labeling, one can easily determine the children and parent of any node K in any complete tree T,. Specifically, the left and right children of the node K are, respectively, 2*K and 2*K + 1, and the parent of K is the node LK/2J. For example, the children of node 9 are the nodes 18 and 19, and its parent is the node L9/2J = 4. The depth d,, of the complete tree 7,, with n nodes is given by D,, = logy n + 1J This is a relatively small number. For example, if the complete tree 7, has n = 1 000 000 nodes, then its depth D,, = 21. Extended Binary Trees: 2-Trees A binary tree tree Tis said to be a 2-tree or an extended binary tree if each node N has either 0 of 2 children. In such a case, the nodes with 2 children are called internal nodes, and the nodes with 0 children are called external nodes. Sometimes the nodes are distinguished in diagrams by using circles for internal nodes and squares for external nodes.‘The term “extended binary tree” comes from the following operation. Consider any binary tree T, such as the tree in Fig. 7.5(a). Then T may be “converted” into a 2-tree by replacing each empty subtree by a new node, as pictured in Fig. 7.5(b). Observe that the new tree is, indeed, a 2-tree. Furthermore, the nodes in the original tree T are now the internal nodes in the extended tree, and the new nodes are the external nodes in the extended tree. (a) Binary tree T (b) Extonded 2-1ree 7.5 Converting a Binary Tree T into.a 2+tree ‘An important example of a 2-tree is the tree T corresponding to any algebraic expression E which uses only binary operations. As illustrated in Fig. 7.3, the variables in E will appear as the external nodes, and the operations in £ will appear as internal nodes. 7.3 REPRESENTING BINARY TREES IN MEMORY Let T be a binary tree. This section discusses two ways of representing T in memory. The first and usual way is called the link representation of T and is analogous to the way linked lists are represented in memory, The second way, which uses a single array, called the sequential represen- tation of T. The main requirement of any representation of T is that one should have direct access to the root R of T and, given any node N of T, one should have direct access to the children of N. Liked Representation of Binary Trees Consider a binary tree T. Unless otherwise stated or implied, T will be maintained in memory by means of a linked representation which uses three parallel arrays, INFO, LEFT and RIGHT, and a pointer variable ROOT as follows. First ofall, each node N of T will correspond to a location such that: (1) INFO{K] contains the data at the node N. (2) LEFT{K] contains the location of the left child of node N (3) RIGHTIK] contains the location of the right child of node N. Furthermore, ROOT will contain the location of the root R of T. If any subtree is empty, then the corresponding pointer will contain the null value; if the tree TT itself is empty, then ROOT will contain the null value.7.6 Data Structures Remark 1: Most of our examples will show a single item of information at each node N of a binary tree T. In actual practice, an entire record may be stored at the node N. In other words, INFO may actually be a linear array of records or a collection of parallel arrays. Remark 2: Since nodes may be inserted into and deleted from our binary trees, we also implicitly assume that the empty locations in the arrays INFO, LEFT and RIGHT form a linked list with pointer AVAIL, as discussed in relation to linked lists in Chap. 5. We will usually let the LEFT array contain the pointers for the AVAIL list Remark 3: Any invalid address may be chosen for the null pointer denoted by NULL. In actual practice, 0 or a negative number is-used for NULL. (See Sec. 5.2.) Example 7.3 Consider the binary tree T in Fig. 7.1. A schematic diagram of the linked representa- tion of T appears in Fig. 7.6. Observe that each node is pictured with its three fields, and that the empty subtrees are pictured by using x for the null entries. Figure 7.7 shows how this linked representation may appear in memory. The choice of 20 elements for the arrays is arbitrary. Observe that the AVAIL list is maintained as a one-way list using the array LEFT. Roor| a [e c am etm = oem ed or im ouE *TLT= Fig. 7.6 oe ee | | Example 7.4 ‘Suppose the personnel file of a small company contains the following data on its nine employees: Name, Social Security Number, Sex, Monthly Salary Figure 7.8 shows how the file may be maintained in memory as a binary tree. Compare this data structure with Fig. 5.12, where the exact same data are organized as a one- way list.I Trees 7 INFO LEFT RIGHT 1f« [Too] o Root eS ire Ls] sfe | ol] o Ava. sloa re te Sy e| [7 1 mL o | o 2 8 4 wl 8 | wf ie " 8 wf. | o | o wl e | 2 fo 14) [15 | 5 [16 6 Ta who 7 Te _——— who fo) o | 19 20 20 Fig. 7.7 Suppose we want to draw the tree diagram which corresponds to the binary tree in Fig. 7.8. For notational convenience, we label the nodes in the tree diagram only by the key values NAME. We construct the tree as follows: (a) The value ROOT = 14 indicates that Harris is the root of the tee. (b) LEFT[14) = 9 indicates that Cohen is the left child of Harris, and RIGHT(14 that Lewis is the right child of Harris. 7 indicates Repeating’ Step (b) for each new node in the diagram, we obtain Fig, 7.9 _sequential Representation of Binary Trees ‘omplete or nearly complete. Then there is an efficient way of Suppose T is a binary tree that is ¢ acpraining T in memory called the sequential representation of T. This representation uses only a single linear array TREE as follows:7.8 Data Structures NAME _SSN Sex SALARY LEFT RIGHT 1 ° } Root 2 [dave | [reecere82| | Fomaie | [22000] | o | [12 14 3[ Kary | [reseesssr] [aie | [19000] | 0 ° 4 Green | [r7s-se-2as1| [ mare | [27200] [2 ° avalL 5 1 8 6 [Brown | [r7eset065] [Femare | [14700] [0 ° 7 [ews | [16-38-0000] | Femae | [16400] | 3 10 Le 7 9 [Conon | [r77aeass7] | mae | [9000] | 6 4 10 | Rubin | [raso-ea62| [Femaie | [15500] [0 0 n 13 12 | evens | [r60s00%10] [wae | [4200] [0 o 18 3 +4 [Haris | [2oes6-1654] | Femaie | [2ea00| [0 7 Fig. 7.8 Harrig Sone Towis Broun Gygen kelly Aubin Davie Evans Fig. 7.9 (a) The root R of T is stored in TREE[1]. (b) If a node N occupies TREE[K], then its left child is stored in TREE[2*K] and its right child is stored in TREE(2*K + 1). Again, NULL is used to indicate an empty subtree. In particular, TREE[1] = NULL indicates that the tree is empty. The sequential representation of the binary tree T in Fig. 7.10(a) appears in Fig. 7.10(b). Observe that we require 14 locations in the array TREE even though T has only 9 nodes. In fact, if we included null entries for the successors of the terminal nodes, then we would actually require TREE(29] for the right successor of TREE{14]. Generally speaking, the sequential representation— Trees cy TREE [4s 2| 2 s| 7 afin | 30 6 As 7 90 LN : 7 % 9 15 A \ GB 1 30 80 " Vl fos 8 14 | 88 15 16 29 (@) (o) Fig, 7.10 of a tree with depth d will require an array with approximately 24*! elements, Accordingly, this, sequential representation is usually inefficient unless, as stated above, the binary tree T is complete or nearly complete. For example, the tree T in Fig. 7.1 has 11 nodes and depth 5, which means it would require an array with approximately 2° = 64 elements. 7.4.TRAVERSING BINARY TREES There are thr called preorder, inorder and postorder, are as follows: Preorder (1) Process the root R. (2) Traverse the left subtree of R in preorder. (3) Traverse the right subtree of R in preorder, ee standard ways of traversing a binary tree T with root R. These three algorithms,(710 ] Data Structures Inorder (1) Traverse the left subtree of R in inorder. (2) Process the root R. | . | (3) Traverse the right subtree of R in inorder. Postorder (1) Traverse the left subtree of R in postorder. (2) Traverse the right subtree of R in postorder. (3) Process the root R Observe that each algorithm contains the same three steps, and that the left e traversed before the right subtree. The difference between the algorithms is the time at which the root R is processed. Specifically, in the “pre” algorithm, the root R is processed before the subtrees are traversed; in the “in” algorithm, the root R is processed between the traversals of the subtrees; and in the “post” algorithm, the root R is processed after the subtrees are traversed. The three algorithms are sometimes called, respectively, the node-left-right (NLR) traversal, the left-node-right (LNR) traversal and the left-right-node (LRN) traversal. Observe that each of the above traversal algorithms is recursively defined, since the algorithm involves traversing subtrees in the given order. Accordingly, we will expect that a stack will be used when the algorithms are implemented on the computer. t the left subtree of R is always Example 7.5 Consider the binary tree T in Fig. 7.11. Observe that A is the root, that its left subtree L; consists of nodes B, D and E and that its right subtree Ry consists of nodes Cand F. A i c ™ / \ Ne DOE F Fig. 7.11 (a) The preorder traversal of T processes A, traver traverses L; and traverses Ry. However, the preorder traversal of L; processes the root B and then and E, and the ler traversal of Ry processes the root C DECF i preorder wavenat or and then F. Hence ABDECF is the (b) The inorder traversal of T traverses Ly, processes A and traverses Ry. However, ne inorder traversal of Ly processes D, B and then E, and the inorder traversal Of Rr processes C and then F. Hence DBEACF is the inorder traversal of T.Trees 71 (©) The postorder traversal of T traverses Ly, traverses Ry, and processes A.. However, the postorder traversal of Ly processes D, E and then B, and the postorder traversal of R; processes F and then C. Accordingly, DEBFCA is the postorder | traversal of T. Example 7.6 Consider the tree T in Fig. 7.12. The preorder traversal of T is ABDEFCGHILK. This order is the same as the one obtained by scanning the tree from the left as indicated by the path in Fig. 7.12. That is, one “travels” down the left-most branch until meeting a terminal node, then one backtracks to the next branch, and so on. In the preorder traversal, the right-most terminal node, node K, is the last node scanned. Observe that the left subtree of the root A is traversed before the right subtree, and both are traversed after A. The same is true for any other node having subtrees, | which is the underlying property of a preorder traversal. ‘The reader can verify by inspection that the other two ways of traversing the binary tree in Fig. 7.12 are as follows: (Inorder) DBFEAGCLIJ HK (@ostorder) .D F EB GLI KHCA Observe that the terminal nodes, D, F, G, L and K, are traversed in the Same order, from left to right, in all three traversals. We emphasize that this is true for any binary tree T.2. Data Structures Example 7.7 Let £ denote the following algebraic expression: [a+ (b- d)*[d- e)/F+9- MI oo. The corresponding binary tree T appears in Fig. 7.13. The reader can verify by inspec- tion that the preorder and postorder traversals of T are as follows: (Preorder) + +a - bc f-de-+f gh (Postorder) @ bec - +de-fgth-/ * | The reader can also verify that these orders correspond precisely to the prefix and postfix Polish notation of £ as discussed in Sec. 6.4. We emphasize that this is true for any algebraic expression E. aN, LW LN. a LS /S, Fig. 7.13 Example 7.8 Consider the binary tree T in Fig. 7.14, The reader can verify that the postorder traversal of T iS as follows: Sy Se Sw Sy Sp Sy Sy Sy M One main property of this traversal algorithm is that every descendant of any node N is processed before the node N. For example, S, comes before S,, Sg and S, come before S,. Similarly, S, and Sp come before S,, and S,, Sg and Ss come before Sp. | Moreover, all the nodes S,, S,, ..., Sg come before the root M. | ON. Z \\. — f f \, Fig. 7.14 , °Trees 7.13 Remark: ‘The reader may be able to implement by inspection the three different traversals of @ binary tree T if the tree has a relatively small number of nodes, as in the above two examples. Implementation by inspection may not be possible when T contains hundreds or thousands of nodes. That is. we need some systematic way of implementing the recursively defined traversals. The stack is the natural structure for such an implementation. The discussion of stack-oriented algorithms for this purpose is covered in the next section. 7.5 TRAVERSAL ALGORITHMS USING STACKS ‘Suppose a binary tree T is maintained in memory by some linked representation TREE(INFO, LEFT. RIGHT, ROOT) This section discusses the implementation of the three standard traversals of T, which were defined recursively in the last section, by means of nonrccursive procedures using stacks. We discuss the three traversals separately Preorder Traversal The preorder traversal algorithm uses a variable PTR (pointer) which will contain the location of the node N currently being scanned. This is pictured in Fig. 7.15, where L(N) denotes the left child of node N and R(N) denotes the right child. The algorithm also uses an array STACK, which will hold the addresses of nodes for future processing. pref / a’ / / / \ Lin) FUN) JN /\ Fig. 7.15 Algorithm: — Initially push NULL onto STACK and then set PTR := ROOT. Then repeat the following steps until PTR = NULL or, equivalently, while PTR # NULL. (a) Proceed down the left-most path rooted at PTR, processing each node N on the path and pushing each right child R(N), if any, onto STACK. ‘The traversing ends after a node N with no left child L(N) is processed. (Thus PTR is updated using the assignment PTR := LEFT[PTR], and the traversing stops when LEFT(PTR] = NULL.) (b) [Backtracking.] Pop and assign to PTR the top element on STACK. If PTR # NULL, then return to Step (a); otherwise Exit. (We note that the initial element NULL on STACK is used as @ sentinel.)7.1 Data Structures We simulate the algorithm in the next example. Although the example works with te odes theriselves, in actual practice the locations of the nodes are assigned to PTR and are pushed ont the STACK. { Example 7.9 Consider the binary tree T in Fig. 7.16. We simulate the above algorithm with T, showing the contents of STACK at each step. “oN “ f ‘S Fig. 7.16 41, Initially push NULL onto STACK: STACK: @, Then set PTR := A, the root of T. 2. Proceed down the left-most path rooted at PTR = A as follows: (i) Process A and push its right child C onto STACK: STACK: @, C. (ii) Process B. (There is no right child.) (ii) Process D and push its right child H onto STACK: STACK: 9, C,H. (iv) Process G. (There is no right child.) No other node is processed, since G has no left child, 3. [Backtracking.] Pop the top element H from STACK, and set PTR = H. This leaves: STACK: 9, C. | Since PTR # NULL, return to Step (a) of the algorithm. | 4, Proceed down the left-most path rooted at PTR = H as follows: (v) Process H and push its right child K onto STACK: STACK: 0, C, K. No other node is processed, since H has no left child, 5. [Backtracking.] Pop K from STACK, and set PTR := K. This leaves: STACK: 8, C. Since PTR # NULL, return to Step (a) of the algorithm. 6. Proceed down the left-most path rooted at PTR = K as follows: (si) Process K. (There is no right child.) No other node is processed, since K has no left child,Trees 7.15 7, (Backtracking.] Pop C from STACK, and set PTR := C. This leaves: STACK: @. . ‘Since PTR # NULL, return to Step (a) of the algorithm. 8. Proceed down the left most path rooted at PTR = C as follows: (vii) Process € and push its right child F onto STACK: STACK: @, F. (vii) Process E. (There is no right child.) 9. [Backtracking.] Pop F from STACK, and set PTR = F. This leaves: STACK: 0. Since PTR # NULL, return to Step (a) of the algorithm. 10. Proceed down the left-most path rooted at PTR = F as follows: | (ix) Process F. (There is no right child.) | ' No other node is processed, since F has no left child. 1 11, [Backtracking.] Pop the top element NULL from STACK, and set PTR := NULL. Since PTR = NULL, the algorithm is completed. ‘As seen from Steps 2, 4, 6, 8 and 10, the nodes are processed in the order A, B, D, G, H, K, C, E, F. This is the required preorder traversal of T. ‘A formal ‘presentation of our preorder traversal algorithm follows: Algorithm 7.1: PREORD(INFO, LEFT, RIGHT, ROOT) ‘A binary tree T is in memory. The algorithm does a preorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Initially push NULL onto STACK, and initialize PTR.] Set TOP := 1, STACK[I] := NULL and PTR := ROOT. 2, Repeat Steps 3 to 5 while PTR # NULL: 3. Apply PROCESS to INFO[PTRI. 4. [Right child?] if RIGHT[PTR] # NULL, then: [Push on STACK.] Set TOP := TOP + 1, and STACK[TOP] := RIGHT[PTR]. [End of If structure.) 5, [Left child?} If LEFT[PTR] # NULL, then: Set PTR := LEFT(PTRI. Else: [Pop from STACK.] Set PTR := STACK(TOP] and TOP := TOP ~ 1. {End of If structure.} [End of Step 2 loop.] 6. Exit.[ze | Dota Stuuctuses Inorder Traversal ‘The inorder traversal algorithm also uses a variable pointer PTR. which will contain the location of the node N currently being scanned, and an array STACK, which will hold the addresses of node, for future processin; fact, with this algorithm, a node is processed only when it is popped from STACK. Algorithm: Initially push NULL onto STACK (for a sentinel) and then set PTR := ROOT. Then repeat the following steps until NULL is popped from STACK. (a) Proceed down the left-most path rooted at PTR, pushing each node N onto STACK and stopping when a node N with no left child is pushed onto STACK. (b) [Backtracking.] Pop and process the nodes on STACK. If NULL is popped, then Exit. If a node N with a right child R(N) is processed, set PTR = RON) (by assigning PTR := RIGHT[PTR]) and return to Step (a). We emphasize that a node N is processed only when it is popped from STACK. Example 7.10 Consider the binary tree T in Fig. 7.17. We simulate the above algorithm with T, showing the contents of STACK. A oe om & a | a “m™ K OM Fig. 7.17 1. Initially push NULL onto STACK: STACK: 8. Then set PTR := A, the root of T. 2. Proceed down the left-most path rooted at PTR = A, pushing the nodes A, B, D, G and K onto STACK: STACK: @, A, B, D, G, K. (No other node is pushed onto STACK, since K has no left child.) 3, [Backtracking.] The nodes K, G and D are popped and processed, leaving: STACK: 0, A, B. j (We stop the processing at D, since D has a right child.) Then set PTR := H, the right child of D._ Trees 7.17 Proceed down the left-most path rooted at PTR = H, pushing the nodes H and L onto STACK: STACK: 0, A, B, H, L. (No other node is pushed onto STACK, since L has no left child.) 5. [Backtracking.] The nodes L and H are popped and processed, leaving: | STACK: 0, A, B. } (We stop the processing at H, since H has a right child.) Then set PTR := M, the | right child of H. 6. Proceed down the left-most path rooted at PTR = M, pushing node M onto STACK: STACK: 0, A, B, M. (No other node is pushed onto STACK, since M has no left child.) 7. [Backtracking.] The nodes M, B and A are popped and processed, leaving: STACK: 0. (No other element of STACK is popped, since A does have a right child.) Set PTR == C, the right child of A. 8, Proceed down the left-most path rooted at PTR = C, pushing the nodes C and E onto STACK: STACK: @, C, E. 9 |. [Backtracking.] Node E is popped and processed. Since E has no right child, node C is popped and processed. Since C has no right child, the next element, NULL, is popped from STACK. The algorithm is now finished, since NULL is popped from STACK. As seen from Steps 3, 5, 7 and 9, the nodes are processed in the order K, G, D, L, H, M, B, A, E, C. This is the required inorder traversal of the binary tree T. A formal presentation of our inorder traversal algorithm follows: Algorithm 7.2: INORD(INFO, LEFT, RIGHT, ROOT) A binary tree is in memory. This algorithm does an inorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Push NULL onto STACK and initialize PTR. Set TOP = 1, STACK[1] := NULL and PTR := ROOT. 2. Repeat while PTR # NULL: [Pushes left-most path onto STACK.] (a) Set TOP := TOP + 1 and STACK[TOP] := (b) Set PTR = LEFT[PTR]. [Updates PTR.] [End of loop.] "TR. [Saves node.] 3. Set PTR := STACK{TOP] and TOP := TOP ~ 1. [Pops node from STACK.] . - 4. Repeat Steps 5 to 7 while PTR # NULL: [Backtracking.] 5. Apply PROCESS to INFO[PTR]7.18 Data Structures 6. [Right child? If RIGHT(PTR] # NULL, then: (a) Set PTR := RIGHT(PTR). (b) Go to Step 3. [End of If structure.} 7. Set PTR := STACK[TOP] and TOP := TOP -1. (Pops node.] [End of Step 4 loop.] 8. Exit. Postorder Traversal The postorder traversal algorithm is more complicated than the preceding two algorithms, because here we may have to save a node N in two different situations. We distinguish between the two cases by pushing either N or its negative, -N, onto STACK. (In actual practice, the location of N is pushed onto STACK, so -N has the obvious meaning.) Again, a variable PTR (pointer) is used which contains the location of the node N that is currently being scanned, as in Fig. 7.15. Algorithm: Initially push NULL onto STACK (as a sentinel) and then set PTR := ROOT. Then repeat the following steps until NULL is popped from STACK. (@) Proceed down the left-most path rooted at PTR. At each node N of the path, push N onts STACK and, if N has a right child R(N), push —R(N) onto STACK. (b) [Backtracking.] Pop and process Positive nodes on STACK. If NULL. is popped, then Exit. If a negative node is popped, that is, if PTR = —N for some node N, set PTR = N (by assigning PTR := -PTR) and retum to Step (a). We emphasize that-a node N is processed only when it is popped from STACK and it is positive. Consider again the binary tree T in Fig. 7.17. We simulate the al ove algorithm with T, showing the contents of STACK. 1, Initially, push NULL onto STACK and set PTR := A, the root of T: STACK: @. 2. Proceed down the left-most path rooted at PTR = A, pushing t! G and K onto STACK. Furthermore, since A has aright child c me sone STACK after A but before B, and since O has a right child H, push “tl one STACK after D but before 6. This yields: . ‘STACK: @, A, -C, B, D, -H, GK. . [Backtracking.] Pop and pi only pop -H. This leaves: STACK: @, A, -C, B, D. Now PTR = » rocess K, and pop and process G. Since -H is negative, ~H. Reset PTR = H and return to Step (a). |a Trees 4 . froseed reid the leftmost path rooted at PTR = H. First push H onto STACK. STACK. This give ld M Push -M onto STACK after H. Lat, push L onto e STACK: @, A, -C, B,D, H, -M, L. facktracking.] Pop and process L, but only pop -M. This z Sin] Pep and oc ly pop -M. This leaves: ‘ Now PTR = -M. Reset PTR = M and return to Step (a). Proceed down the left-most path rooted at PTR = M. Now, ‘onto STACK, This yields: wonky Hs pushed STACK: @, A, -C, B,D, H, M. [Backtracking.} Pop and process M, H, D and B, bi ~C. Thi 3 leaching | H, , but only pop ~C. This leaves: Now PTR = ~C. Reset PTR = C, and return to Step (a). Proceed down the left-most path rooted at PTR = C. First C is pushed onto STACK and then E, yielding: STACK: 0, A, C, E. [Backtracking.] Pop and process E, C and A. When NULL is popped, STACK is empty and the algorithm is completed. ro ~ As seen from Steps 3, 5, 7 and 9, the nodes are processed in the order K, G, L, M, H,. D, B, E, C, A. This és the required postorder traversal of the binary tree T. A formal presentation of our postorder traversal algorithm follows: Algorithm 7.3: POSTORD(INFO, LEFT. RIGHT, ROOT) A binary tree T is in memory. This algorithm does a postorder traversal of T. applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Push NULL onto STACK and initialize PTR.) Set TOP := 1, STACK[1] := NULL and PTR := ROOT. 2. {Push left-most path onto STACK.] Repeat Steps 3 to 5 while PTR # NULL: 3. Set TOP := TOP + | and STACK{TOP] := PTR. (Pushes PTR on STACK.] 4. If RIGHT[PTR] # NULL. then: (Push on STACK.] Set TOP := TOP + | and STACK[TOP] := -RIGHTIPTR]. [End of If structure.] 5, Set PTR := LEFT[PTR]. (Updates pointer PTR.] [End of Step 2 loop.] 6. Set PTR := STACK[TOP] and TOP := TOP - 1 [Pops node from STACK.] | | |Data Structures 7. Repeat while PTR > 0: (a) Apply PROCESS to INFO[PTR]. (b) Set PTR := STACK[TOP] and TOP := TOP - 1 [Pops node from STACK.] {End of loop.] 8. If PTR <0, then: (a) Set PTR := -PTR. (b) Go to Step 2. {End of If structure.] 9. Exit. 7.6 HEADER NODES; THREADS g Ce ‘onsider a binary tree T. Variations of the linked representation of T are frequently used because certain operations on T are easier to implement by using the modifications. Some of these varia- tions, which are analogous to header and circular linked lists, are discussed in this section. Header Nodes Suppose a binary tree T is maintained in memory by means of a linked representation. Sometimes an extra, special node, called a header node, is added to the beginning of T. When this extra node is used, the tree pointer variable, which we will call HEAD (instead of ROOT), will point to the header node, and the left pointer of the header node will point to the root of T. Figure 7.18 shows a schematic picture of the binary tree in Fig. 7.1 that uses a linked representation with a header node. (Compare with Fig. 7.6.) HEAD [ot x | Header node =] pee (x[e Tx] pee x[e]* LHL o Fig. 7.18_ 7.21 Suppose a binary tree T is empty. Then T w the header node will coms ea eet, ils contin a header node, but he let pointer of hus the condition / LEFT[HEAD] = NULL will indicate an empty tree. Another variation of i ‘ation of the above representation of a binary tree T is to use the header node as a sentinel, That is, i the address aes a node has an empty subtes, then the pointer field for the subtree will contain . . node instead of the null value. According! 4 . an invalid address. and the condition \c ‘gly. no pointer will ever contain LEFT[HEAD] = HEAD will indicate an empty subtree. Threads; Inorder Threading Consider again the linked representation of a binary tree T. Approximately half of the entries in the pointer fields LEFT and RIGHT will contain null elements. This space may be more efficiently used by replacing the null entries by some other type of information. Specifically, we will replace certain null entries by special pointers which point to nodes higher in the tree. These special pointers are called threads, and binary trees with such pointers are called threaded trees. The threads in a threaded tree must be distinguished in some way from ordinary pointers. The threads in a diagram of a threaded tree are usually indicated by dotted lines. In computer memory, an extra I-bit TAG field may be used to distinguish threads from ordinary pointers, or. alterna- tively, threads may be denoted by negative integers when ordinary pointers are denoted by positive integers. ‘There are many ways to thread a binary tree T, but each threading will correspond to a particu- lar traversal of T. Also, one may choose a one-way threading or a Wwo-way threading. Unless otherwise stated, our threading will correspond to the inorder traversal of T. Accordingly, in the one-way threading of T, a thread will appear in the right field of a node and will point to the next rode in the inorder traversal of T; and in the two-way threading of T, a thread will also appear in the LEFT field of a node and will point to the preceding node in the inorder traversal of T. Fosthermore. the left pointer of the first node and the right pointer of the last node (in the inorder travereal of T) will contain the null value when T does not have a header node, but will point ro the T does have a header node. ner is a2 ealogous one-way threading of a binary tree T which corresponds to the preorder traversal of T, (See Solved Problem 7.13.) On the other hand, there is no threading of T which corresponds to the postorder traversal of T Example 7.12 } Consider the binary tree T in Fig. 7.1. way inorder threading of T appears in Fig. 7.19(a). There is a thread ® from node F to node A, since A is accessed after E in the inorder traversal of T-Data Structures it threading rae (b) Two-way inorder threading =| Header node it (c) Two-way threading with header node Fig. 7.19 Observe that every null right pointer has been replaced by a thread except for the node K, which is the last node in the inorder traversal of 7. (6) The two-way inorder threading of T appears in Fig, 7.19(b). There is a left thread from node | to node C, since L is accessed after ¢ ya the inorder traversal(9 d Trees Of T. Observe that every null left for node D, which is the fir; noe threads are the sa ig The two-way 7.19(c). Here node. Otherwi: Pointer has been replaced by a thread except de in the inorder traversal of T. All the right me as in Fig. 7.19(a), ‘inorder threading of T when T has a header node appears in Fig. the left thread of D and the right thread of K point to the header se the picture is the same as that in Fig. 7.19(b). Figure 7.7 shows how T may be maintained in memory by using a linked repre- Sentation. Figure 7.20 shows how the representation should be modified so that Tis a two-way inorder threaded tree using INFO[20] as a header node. Observe that LEFT[12] = - 10, which means there is a left thread from node F to node B. Analogously, RIGHT[17] = - 6 means there is a tight thread from node J to node H. Last, observe that RIGHT[20] = 20, which means there is an ordinary Tight pointer from the header node to itself, If T were empty, then we would set LEFT[20] = - 20, which would mean there is a left thread from the header node to itself, INFO LEFT RIGHT 1[« [=7 | -2 HEAD 2|¢ 3 é 20 sj «| s | 2 oe 16 AVAIL Ss] A | 10 2 8 e{ 4 | a7 1 7f uc | 2] -7 8 8 e 4 wl 8 | 13 " 19 wf e [=o | 3 wie | 2 5 1“ 16 15 16 16 uw wld 7 ad 1e{ 0 | -20 | -10 19 ° 20 5 20 Fig. 7.207.26 Data Structures 44 BINARY SEARCH TREES a This section discusses one of the most important data structures in computer science. a binary search tree. This structure enables one to search for and find an element with an average running time fin) = O(log, n). It also enables one to easily insert and delete elements. This structure contrasts with the following structures: (a) Sorted linear array, Here one can search for and find an element with a running time f{n) = O(log, n), but it is expensive to insert and delete elements. (b)- Linked list. Here one can easily insert and delete elements, but it is expensive to search for and find an element, since one must use a linear search with running time fn) = O(n). Although each node in a binary search tree may contain an entire record of data, the definition of the binary tree depends on a given field whose values are distinct and may be ordered. Suppose T is a binary tree. Then T is called a binary search tree (or binary sorted tree) if each node N of T has the following property: The value at N is greater than every value in the left Subtree of N and is less than every value in the right subtree of N. (It is not difficult to see that this Property guarantees that the inorder traversal of T will yield a sorted listing of the elements of T.) Example 7.13 { () Consider the binary tree T in Fig, 7.21. Tis a binary search tree: that is, every node N in T exceeds every number in its left subtree and is less than every number in its right subtree, Suppose the 23 were replaced by 35. Then T would still be a binary search tree. On the other hand, suppose the 23 were replaced by 40. Then T would not be a binary search tree, since the 38 would not be greater than the 40 in its left subtree. woo ON a 8 / 70 Fig. 7.21 = a (b) Consider the file in Fig. 7.8, As indicated by Fig. 7.9, the file is a binary search tree with Fespect to the key NAME. On the other hand, the file is not a binary search tree with respect to the social security number key SSN. This situation is similar to an array of records which is sorted with respect to one key but is unsorted with respect to another key.Trees The definition of a binary search tree given in this section section distinct. There is assumes that all the node values are an analogous defini each node N has the Tole ntion OF Binary search tree which admits duplicate, tht i in winsubinee of Nand is less thon 8 property: The value at N is greater than every value in the or equal t0 every value in the right subtree of N. When this definition is used, the operations in the next section must be modified accordingly. 7.8 SEARCHING AND INSERTING IN BINARY SEARCH TREES se T is a bi cl . panies can sey Search tree. This section discusses the basic operations of searching and inserting with respect 10 T. In fact, the searching and inserting will be given by a single search and insertion algorithm. The operation of deleting is treated in the next section. Traversing in T is the same as traversing in any binary tree; this subject has been covered in Sec. 7.4. Suppose an ITEM of information is given. The following algorithm finds the location of ITEM in the binary search tree T, or inserts ITEM as a new node in its appropriate place in the tree. (a) Compare ITEM with the root node N of the tree. (i) If ITEM N, proceed to the right child of N. {b) Repeat Step (a) until one of the following occurs: (i) We meet a node N such that ITEM = N. In this case the search is successful. Gi) We meet an empty subtree, which indicates thatthe search is unsuccessful, and we insert ITEM in place of the empty subtree. In other words, proceed from the root R down through the tree T undl Finding ITEM in T or inserting ITEM as a terminal node in T. Example 7.14 (a) Consider the binary search tree T in Fig. 7.21. Suppose ITEM = 20 is given. Simulating the above algorithm, we obtain tthe following steps: 4. Compare ITEM = 20 with the root, 38, of the tree T. Since 20 < 38, proceed to the left child of 38, which is 14. 2. Compare ITEM = 20 with 14. Since 20 > 14, proceed to the right child of 14, which is 23. 3. Compare ITEM = ich is 18. | 4 Coote TTEM = 20 with 18. Since 20 > 18 and 18 does not have a right Child, insert 20 as the right child of 18. th ITEM = 20 inserted. The shaded edges tree during the algorithm. fh tree T in Fig. 7.9. Suppose ITEM = Davis is given. we obtain the following steps: 20 with 23. Since 20 < 23, proceed to the left child of 23, Figure 7.22 shows the new tree wi Piartate the path down through the (b) Consider the binary search t Simulating the above algorithm,Data Structures _ a * ———— 14, 56 aa a 8 P 45 / 8 70 \ 20 Fig. 7.22 ITEM = 20 Inserted 1. Compare ITEM = Davis with the root of the tree, Harris. Since Davis < Harris, proceed to the left child of Harris, which is Cohen. 2. Compare ITEM = Davis with Cohen. Since Davis > Cshen, proceed to the right child of Cohen, which is Green. 3. Compare ITEM = Davis with Green. Since Davis < Green, proceed to the left child of Green, which is Davis. Compare ITEM = Davis with the left child, Davis. We have found the location of Davis in the tree. - Example 7.15 tree: 40, 60, 50, 33, 55, 11 Figure 7.23 shows the six stages of the tree. We emphasize that if the six numbers were given in a different order, then the tree might be different and we might have a different depth. | | Suppose the following six numbers are inserted in order into an empty binary search | | 40 40 40. 40. 60 No 38 Nye i 50 86 | (1)ITEM=40 (2) ITEM=60 (3) ITEM =50 (4) ITEM = 33 D 33 Sp 4 80 \ 85 (ITEM =11 Fig. 7.23using the pointer PTR and the pointer § Parent. The procedure traverses down the tree in the next section, on deletion, Procedure 7.4: FINDANFO, LEFT. RIGHT, ROOT, ITEM, LOC, PAR) inary is in ns . 5 Y Search tree T is in memory and an ITEM of information is given. This proc: i PAR ne a finds the location LOC of ITEM in T and also the location Parent of ITEM. There are three special cases: (@ Loc =Nu ‘al indi , (5 toca NULL and PAR NULL will indicate that the tree of T. (iii) LOC = NULL and PAR # NULL will indicate that ITEM is not in T and can be added to T as a child of the node N with location PAR. 1. (Tree empty?] If ROOT = NULL. then: Set LOC := NULL and PAR Return, 2. {ITEM at root?] If ITEM = INFO[ROOT], then: Set LOC and Return. 3. [Initialize pointers PTR and SAVE.) if ITEM < INFO[ROOT], then: Set PTR EFT[ROOT] and SAVE := ROOT. Else: Set PTR := RIGHT[ROOT] and SAVE [End of If structure.) 4. Repeat Steps $ and 6 while PTR # NULL: s empty. ULL will indicate that ITEM is the root TULL, and ROOT and PAB := NULL, ROOT. 5. (ITEM found?] If ITEM = INFO[PTR], then: Set LOC := PTR and PAR := SAVE. and Return. 6. If ITEM < INFO[PTR], then: Set SAVE = PTR and PTR = LEFT{PTR). Else: Set SAVE ‘= PTR and PTR := RIGHTIPTR}. [End of If structure.] .d of Step 4 loop.) . 7, [Search unsuccessful.] Set LOC == NULL and PAR := SAVE. 8. Exit Obs th: Step 6, we move to the left child or the right child according to whether erve that, J e that, in Step ITEM < INFOIPTR] oF ITEM > INFOIPTRI. 4 follows. ‘The formal statement of our search and insertion algorithmStructures (7.28 | Data Str Algorithm 7.5: INSBST(INFO, LEFT, RIGHT, ROOT, AVAIL, ITEM, LOC) a SN Sinary search tee 7 is in-memory and an ITEM of information is given ‘his algorithm finds the location LOC of ITEM in T or auds ITEM as a new node in T at location LOC. 1. Call FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR). [Procedure 7.4.] 2. If LOC # NULL, then Exit. 3. (Copy ITEM into new node in AVAIL list.] . (a) If AVAIL = NULL, then: Write: OVERFLOW, and Exit. (b) Sct NEW := AVAIL, AVAIL := LEFT[AVAIL] and INFO[NEW] := ITEM. {c) Set LOC := NEW. LEFT[NEW. RIGHT[NEW] := NULL. 4, [Add ITEM to tree.] If PAR = NULL, then: Set ROOT := NEW. Else if ITEM < INFO[PAR], then: Set LEFT[PAR] := NEW. Else: ‘ Set RIGHT[PAR]} [End of If structure.] 5. Exit. NULL and * EW. Observe that, in Step 4, there are three possibilities: (1) the tree is empty, (2) ITEM is added as ¢ left child and (3) ITEM is added as a right child. Complexity of the Searching Algorithm Suppose we are searching for an item of information in a binary search tree T. Observe that the number of comparisons is bounded by the depth of the tree. This comes from the fact that we proceed down a single path of the tree. Accordingly, the running time of the search will be proportional to the depth of the tree. Suppose we are given n data items, A, A, ..., Ay, and suppose the items are inserted in order imo a binary search tree T. Recall that there are 2! permutations of the 7 items (Sec, 2.2). Each such permutation will give rise to a corresponding tree. It can be shown that the average depth of the n! trees is approximately c log, n, where c= 1.4, Accordingly, the average running time f(n) © search for an item in a binary tree T with 1 elements is proportional to log, n, that is, fin) = O(log. ") Application of Binary Search Trees Consider a collection of 1m data items, Aj. Ag, . ‘Ay. Suppose we want to find and delete all duplicates in the collection. One s aightforward way to do this is as follows:_Trees Algorithm Az Scan the elements from A, to Ay (that is, from left to right), (@) For each element Ax compare Ax with A,, A : © Ax.with those elements which precede Ay.” x does occur among A; Ap, ..., Ax. then delete AK. fer all elements have been scanned, there will be no duplicates ++ Ay 1. that is, compare Example 7.16 Suppose Algorithm A is applied to the following list of 15 numbers: 44, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 23 Observe that the first four numbers (14, 10, 17 and 12) are not deleted. However, As = 10 is deleted, since Aya Ar Ag = 12 is deleted, since Aga Ay An = 20 is deleted, since Au Ay Aye is deleted, since Aig As When Algorithm A is finished running, the 11 numbers 14, 10, 17, 12, 11, 20, 18, 25, 8, 22, 23 which are all distinct, will remain. Consider now the time complexity of Algorithm A, which is determined by the number of ‘comparisons. First of all, we assume that the number d of duplicates is very small compared with the number n of data items. Observe that the step involving Ay will require approximately k - 1 comparisons, since we compare Ay, with items Ay Aa .... Ax (less the few that may already have been deleted). Accordingly, the number (7) of comparisons required by Algorithm A is approxi- mately n-\)n OF 14 243e oF -DeM-—D = O(n) For example, for n = 1000 items, Algorithm A will require approximately 500 000 comparisons. In other words, the running time of Algorithm A is proportional to 7 : Using a binary search tree, we can give another algorithm to find the duplicates in the set Aj, Ay... Ay of n data items. Jlements Aj, Ap. ..., Ay. In building the Al : binary search tree T using the e 15 Ay ees Avy ng feritum Bs aan elete Ax from the list whenever the Value of Ay already appears in the tree. ‘i Jement Ay is compared only with the elements The mai ‘Algorithm B is that each el K in single erent ot te ee. It can be shown that the average length of such @ branch approximately logy k where ¢ = 1.4. Accordingly. the total number fin) of comparisons required 2Data Structures is, fim) = . For example, for n = 1009, i logy m that is, fin) = OCH 1082 ”). yy Aloe a imately To 000 comparisons rater than the 500 000 comparion with “algorithm ‘A. (We note that, for the worst case, the number of comparisons for Algorithm B is the same as for Algorithm A.) Example 7.17 Consider again the following list of 15 numbers: 44, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 23 Applying Algorithm B to this list of numbers, we obtain the tree in Fig. 7.24. The exact number of comparisons is Ode de Ze 2tRe2eTe Ze THT H Zt hehe 5a 3B 10. N 7 4™ Sx / a — " / 22 \ 23 Fig. 7.24 On the other hand, Algorithm A requires O14 243 4+24+4+54+44+64+74+64+84+9454+10 = 72 comparisons. 7.9 DELETING IN A BINARY SEARCH TREE Suppose T is a binary search tree, and suppose an ITEM of information is given. This section gives an algorithm which deletes ITEM from the tree T. The deletion algorithm first uses Procedure 7.4 to find the location of the node N which contains ITEM and also the location of the parent niode P(N). The way N is deleted from the tree depends primarily on the number of children of node N. There are three cases: Case 1. N has no children. Then N is deleted from T by si i i it P yy simply replacing the location of N in the parent node P(N) by the null pointer. . ”case 2. N has exactly one child, Th in P(N) by the location of ‘en N is deleted from T by si simpl i mt the only chid of cr” 7 CY Simply replacing the location of case 3. N has two children. Let sy that S(N) does ner het <¢ !) denote the inord left child.) Then N ‘er successor of N. (The reader can verify from T (by using Case 1 of t is deleted from T by first deleting S(N) ° 4se 2) and then replacing node N in.T by the node S(N). observe that the third case is much more co mplicated the memory space of the deleted node N is returned 19 the aa Tit ee ina tree cases Example 7.18 Consider the binary search tree in Fi j aan ig. 7:25(a). in Fig. 7.25(b). ig. 7-25(a). Suppose T appears in memory as INFO LEFT RIGHT root 1[ 33 | 0 8 60 { 3 ] 2| 2 8 10 ON, ava 3 | 60 | 2 7 @ © & «ete 15 50 66 5 6 6 ° 8 7| 7% | 4 ° \ @ | 15 0 oO o[ 44 | 0 0 10 | 50 1 ° (a) Before deletions (©) Linked representation Fig. 7.25 in Fig. 7.25. Note that node 44 has se we delete node 44 from the tree T in Fig. 7.2 d « mere. Figure 7.26(a) pictures the tree after 44 is deleted, and Fig. 7.26(b) shows the Linked representation in memory. The deletion is accom. plished by simply assigning NULL to the parent node, 33. (The shading indicates the changes.) — instead of node 44 de 75 from the tree T in Fig. 7.25 instead of node 44, note that n te 13 hos only one child. Figure 7.27(a) pictures the tree after 75 hie teat d Fig. 7.27(b) shows the linked representation. The deletion is is deleted, and Fg, the right pointer of the parent node 60, which 2a Oo 78,50 that it now points to node 66, the only child of 75. orig " (The shading indicates the changes.) ()Data Structures - m2 INFO| LEFT RIGHT root 1|_ 33 ° 9 3 ] 2] 26 8 10 4 “NS aval 3 | 60 2 7 2s = fo} «fm fo | 4 / 5 6 6 5068 : 3 é 7| 7 4 ° e| 15 ° ° 8 5 10 | 50 1 0 (a) Node 44 is deleted (b) Linked representation Fig. 7.26 INFO_LEFT RIGHT root 1/ 33 | 0 9 a 3 2[ 2 | e 10 ZN wna feo fe fa = & 7 4{ 6 | o ° i \o 8 5 6 | 0 33 7 3 \ 8/1 | o ° “ 9| 44 ° 0 10 | 50 1 0 (a) Node 75 is deleted (b) Linked representation Fig. 7.27 (c) Suppose we delete node 25 from the tree T in Fig. 7.25 instead of node 44 or node 75. Note that node 25 has two children. Also observe that node 33 is the inorder successor of node 25. Figure 7.28(a) pictures the tree after 25 is deleted, and Fig. 7.28(b) shows the linked representation. The deletion is accamplished by first deleting 33 from the tree and then replacing node 25 by node 33. We emphasize that the replacement of node 25 by node 33 is executed in memory only by changing pointers, not by moving the contents of a node from one location to another. Thus 33 is still the value of INFO[1].7.33 INFO LEFT RIGHT Root 1[ a3 7 1 ZO oN 2 33 7 avait 3 | 60 7 7 LN / [2] «[e [eo 0 18 30 : ; 44 6 ° 7\| 75 4 0 | a| 15 ° 0 } | 9| 44 0 0 10 50, 9 O | (a) Node 25 is deleted (0) Linked representation Fig. 7.28 Our deletion algorithm will be stated in terms of Procedures 7.6 and 7.7, which follow. The first procedure refers to Cases | and 2, where the deleted node N does not have two children; and the second procedure refers to Case 3, where N does have two children. There are many subcases which reflect the fact that N may be a left child, a right child or the root. Also, in Case 2, N may have a left child or a right child. Procedure 7.7 treats the case that the deleted node N has two children. We note that the inorder successor of N can be found by moving to the right child of N and then moving repeatedly to the left until meeting a node with an empty left subtree. Procedure 7.6: CASEA(INFO, LEFT, RIGHT, ROOT, LOC, PAR) ‘This procedure deletes the node N at location LOC. where N does not have two children. The pointer PAR gives the location of the parent of N. or else PAR = NULL indicates that N is the root node. The pointer CHILD gives the atijon of the only child of N. or else CHILD = NULL indicates N has no children. itializes CHILD.] * PLEFTILOCI = NULL and RIGHT[LOC] = NULL, then: Set CHILI a Lith Else if LEFT[LOC] 4 N' LL. then: Set CHILD := LEFT{LOC]. I set CHILD := RIGHTILOC]. [End of If structure.)= Data Structures _ 2. If PAR # NULL, then: If LOC = LEFT[PAR], then: Set LEFT[PAR] := CHILD. Ise: . Set RIGHT[PAR] := CHILD. [End of If structure] Else: Set ROOT := CHILD. [End of If structure] 3. Return. Procedure 7.7: CASEB(INFO. LEFT, RIGHT, ROOT, LOC, PAR) This procedure will delete the node N at location LOC. where N has two children. The pointer PAR gives the location of the parent of N, or else PAR = NULL indicates that N is the root node. The pointer SUC gives the location of the inorder successor of N, and PARSUC gives the location of the parent of the inorder successor. 1, [Find SUC and PARSUC.] (a) Set PTR := RIGHT[LOC] and SAVE := LOC. (b) Repeat while LEFT[PTR] # NULL: Set SAVE := PTR and PTR (End of loop.] (c) Set SUC := PTR and PARSUC := SAVE. 2, [Delete inorder successor. using Procedure 7.6.] Call CASEA(INFO. LEFT, RIGHT, ROOT, SUC, PARSUC). 3. [Replace node N by its inorder successor. ] (a) If PAR # NULL, then: If LOC = LEFTIPAR], then: Set LEFT[PAR] := SUC. Else: Set RIGHT{PAR] := SUC. [End of If structure.} Else: Set ROOT := SUC. [End of If structure,} (b) Set LEFT|SUC] := LEFT(LOC] and RIGHT(SUC] := RIGHT|LOC]. 4. Return. LEFT[PTR]. We can now formally state our deletion algorithm, using Procedures 7.6 and 7.7 as building blocks.Trees 735 | Algorithm 7.8; RAINFO. LEFT, RIGHT, ROOT, AVAIL, ITEM) ie al search tree T is in memory, and an ITEM of information is given, Teer deletes ITEM from the tree. . locations of ITEM and its parent, using Procedure 7.4.] Call FIND(NFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR). 2, (ITEM in tree?} ILO = NULL, then: Write: ITEM not in tree, and Exit. 3. [Delete node containing ITEM.] TERIGHT(LOC] # NULL and LEFT[LOC] # NULL, then: Call CASEB(INFO, LEFT, RIGHT, ROOT, LOC, PAR). Else: Call CASEA(INFO, LEFT, RIGHT, ROOT, LOC, PAR). (End of If structure.] 4. [Return deleted node to the AVAIL list.] Set LEFT[LOC) := AVAIL and AVAIL := LOC. 5. Exit. 7.10 AVL SEARCH TREES The binary search tree data structure was discussed in sections 7.7-7.9(Consider the elements A, B, C, D,..., Z to be inserted into a binary search tree as shown in Fig. 7.29(a). Observe’ how the binary search tree turns out to be right skewed. Again the insertion of elements Z, Y, c,B, A in that order in the binary search tree results in a left skewed binary search tree (Fig. 7.29(b)) The disadvantage of a skewed binary search tree is that the worst case time complexity of a search is O(n). Therefore there arises the need to maintain the binary search tree to be of balanced height. By doing so it is possible to obtain for the search operation a time complexity of O(log n) in the worst case. One of the more popular balanced trees was introduced in 1962 by Adeison—Velskii and Landis and was known as AVL trees. ar TY ® © ‘ é Right skewed binary Light skewed binary search tre st Fig. 7.29Data Structures 7.36 Definition ‘ VL tree iff given Té and , an empty bifary tee is an AVL tree. A non emply Prt tree Tie a eof aibbees Tans | ne at and right subtreésof T and h(T™) apa Ma oA ope me 8 Teapecivly, Te and T® aze AVL trees and HT) (TS TL tree the balance factor of node NTS) = h(T®) is known as the balance. factor (BF) anid for an can be'either 0, 1,or—L ‘An AVL search tree is'a binary se Representation of an AVL Search Tree are represented using arch tree which is an AVL tee, a linked representation. However, ion of an AVL search AVL search trees like binary search trees hows the representa! every node registers its balance factor Figure 7:30 s cere number against each node represents its balance factor. eq" (0), a) 5519) Fig. 7.30 AVL Searching an AVL Search Tree Searching an AVL search tree for an element is e search tree (Illustrated in procedure 7.4). 7.11 INSERTION IN AN AVL SEARCH TREE Inserting an element into an AVL search tree in its first phase is similar f0 that of the one used in tpinary search tree. However, if after insertion of the element, the balance factor of any node in a eines is affected so as to render the binary search tree unbalanced, we resort to techniques called zations to restore the balance of the search tree. For example. consider the AVL. search Ue servi in Fig. 7.30. inserting the element E into the tree makes it unbalanced the tree, since BFC) 2 ‘To perform rotations itis necessary to identify a specific node A whose BF(A) is neither 0, 1 oF <1 andi which is the nearest ancestor to the inserted node on the path from the inserted node the root, This implies that all nodes on the path from the inserted node to A will have their balance: foctors to be either 0, 1, oF =I, The rebalancing rotations are classified as LL. LR, RR and RL as illustrated below, based on the position of the inserted node with reference to A sxactly similar to the method used in a binary LL rotation: Inserted node is in the left subtree of left subtree of node A RR rotation: Inserted node is in the right subtree of right subtree of node A LR rotation: Inserted node is in the right subtree of left subtree of node A RL rotation: Inserted node is in the left subtree of right subtree of node A Each of the rotations is explained with an example.Trees \ . 737 LL Rotation Figure 7.31 illustrates the balancing of Balanced % of an AVL search tree through LL rotation. AVL Unbalane on Search roo ater Balanced AVL (+1) insertion ‘search tree after (a) (2) rotation Insert x 0) 0) intoB, (+1), CA) LL rotation ©) (3) 4 @) _. CO} t Ls F mn BT | 0S By : Left subtree of B & Bp : Right subtree of 8 ‘Ag : Right subtree of A fh: Height Fig. 7.31 ‘The new element X is inserted in the left subtree of left subtree of A, the closest ancestor node whose BF(A) becomes +2 after insertion. To rebalance the search tree, it is rotated so as to allow B to be the root with B, and A to be its left subtree and right child, and Br and Ag to be the left and right subtrees of A. Observe how the rotation results in a balanced tree. Example 7.19 . | Insert 36 into the AVL search tree _given in Fig. 7.32(2). Figure 7.32(b) shows the AVL search tree after insertion and Fig. 7.32(c) the same after LL rotation. RR Rotation it ing RR rotation. Here the new i 33 illustrates the balancing of an AVL search tree using Senet is ithe right subtree of A. The rebalancing rotation pushes B up to the root with A as its loft child and By as its right subtree, and A. ‘and By, as the left and right subtrees of A. Observe the balanced height after the rotation. | i | Example 7.20 ig. 7.34(a). Figure 7.34(b) shows the ) the rebalanced search tree after RR arch tree shown in Fi srtion and Fig 7.34(¢) Insert 65 into the AVL sei unbalanced tree after inse rotation.Data Structures Insert 36 Unbalanced AVL search tree (b) LL rotation Balanced AVL search {ree after LL rotation ©) Fig, 7.32 Balanced Unbalanced AVL AVL search search tree after tree insertion 1) (2) (a) Ingort x A (0) into Ba (1) t (B) = 4 8 By, Br Bi Br; Ay lh 4 r n LL ney xt Zu rotation (A) Peat | | net h Balanced AVL search t x4 treeaner rotation Fig. 7.33~ Trees Insertes (0) Unbalanced BO AVL search tree (b) om Gi R rotation Balanced AVL, search tree after RR rotation () Fig. 7.34 LR and RL Rotations d RL rotations are sit ‘The balancing methodology of LR an‘ ne another, Hence we ilustrate one of them viz. LR rotation in this set the balancing of an AVL search tree using LR rotation in this case, the BF values of nodes A and B after bal node C after insertion. BF(B)=0, after rotation 0, BF(B) = 1, after rotation 1, BE(B) = 0, after rotation milar in nature but are mirror images of ction. Fig. 7.35 illustrates Jancing are dependent on the BF value of Example 7.21 shown in Fig. 7.36(a). Figure 7.36(b) shows the (c) the rebalancing of the AVL tree using LR ion BF(C = 39) = 1 leads to BF(A = 44) = -1 and iL search tree Insert 37 into the AVI and Fig. 7.3! imbalance in the tree e rotation. Observe how after inserti he rotation. BF(B = 30) = 0 after the (otANT are called as single rotatic LL and RR rotations ions and LR and RL are i ‘omplished by RR followed by LL rotation and RL Amongst the rotations, known as double rotations since. LR can be ac i by RR rotation. can be accomplished by LL followed in an AVL tree is given bY ‘O(height)= (108 ")- ‘The time complexity of an insertion operation— 7.40 Data Structures Unbalanced Balanced AVL search tree AVL search tree after insertion aye Aye? © InsertxintoC, (+1) 8 ay ==> n 8, (0) 8 (+1) f c - c t ca | |h c on hl [erje. ALLE Lie Rotation Aa : — Balanced AVL search C, : Loft subtree of C Ca . Gq : Right subtree of C Larotation (+t) @ @ @° (0) (0) (0), Initial AVL search tree (a) Unbalanced AVL search tree tree after rotation (e) Fig. 7.36Zt Trees EXAMPLE 7.22 Construct an AVL search tree by inserting the following elements in the order of their occurrence. 64, 1, 44, 26, 13, 110, 98, 85 Inserted, 1 o Insert 14 Insert 85(382 Data Structures _ 7.12 DELETION IN AN AVL SEARCH TREE ‘The deletion of an element in an AVL search tree proceeds as illustrated in procedures 7.6, 7.7 and algorithm 7.8 for deletion of an element in a binary search wee. However, in the event of an imbalance due to deletion, one or more rotations need to be applied to balance the AVL tree, On deletion of a node X from the AVL tree, let A be the closest ancestor node on the path from X to the root node, with a balance factor of +2 or -2. To restore balance the rotation is first classified as L or R depending on whether the deletion occurred on the left or right subtree of A. Now depending on the value of BF(B) where B is the root of the left or right subtree of A, the R or L imbalance is further classified as RO, R1 and R-I or LO, LI and L-1. The three kinds of R rotations are illustrated with examples. The L rotations are but mirror images of these rotations. RO Rotation If BF(B)=0, the RO rotation is executed as illustrated in Fig. 7.38. rch tree Unbalanced AVL search before deletion of x tree after deletion of x aye By (2) © ba Delete x © bn 8 8 + t 1 ‘ h Ba het t $A} aanosaveaconn AEP TLL | + ¥ ‘tree after RO Rotation Y — B Bn x:node to be deleted Fig. 7.38 Example 7.23 set right the imbalance since deletion occurs to the right of node A = 46 whose BF(A = 46) = +2 and BF(B = 20) = 0. Figure 7.39(b) shows the imbalance after deletion | | Delete 60 from the AVL search tree shown in Fig. 7.39(a). This calls for RO rotation to and Fig. 7.39(c) the balancing of the tree using RO rotation,AVL search tree before delétion (a) Unbalanced AVL search tree after deletion of 60 Balanced AVL search tree after RO rotation © Fig. 7.39 R1 ROTATION If BF(B) = 1, the RI rotation as illustrated in Fig. 7.40 is executed. Example 7.24 Delete 39 from the AVL search tree as shown in Fig 7.41(a). This calls for R1 rotation to set right the imbalance since deletion occ’ to the right of node A = 37 whose BF(A = 37) = +2 and BF(B = 26) = *- Figure 7.41(b) shows the imbalance after i it he tree using Ri rotation. deletion and Fig.7.44(c) the balancing of © R-1 Rotation If BF(B) = -1, the RI rotation as stustrated in Fig. 7.42 is executed.7. Data Structures AVL search tree before deletion of x ayy a), An Delete x oe» ||! : pat ; ‘ a” By, (0) AVL searc! before del (a) bot y Balanced AVL search tree after At rotation Fig. 7.40 Gn htree letion (a) fn Br LI 4 Ant Delete 39 Unbalanced AVL search tree after deletion of x (+2) Br hoe + Unbalanced AVL search tree after deletion of 39 (b) Balanced AVL search tree after Rt rotation (o) Fig. 7.41 vTrees 7a AVL search tree befor : s v0 deletion of x Unbalanced AVL search on tree after deletion of x Balanced AVL search tree alter R-1 Rotation Fig. 7.42 | Example 7.25 tree shown in Fig. 7.43(2). This calls for R-1 rotation | to set right the imbalance since deletion occurs to the right of node A = 44 whose BF(A = 44) = +2 and BF(B = 22) = -1. Figure 7.43(b) shows the imbalance after L Gelation and Fig. 7.43(c) the balancing of the ee using R-1 rotation. | delete 52 from the AVL search EXAMPLE 7.26 wn in Fig. 7.44(a) delete the listed elements: | Given the AVL search tree sho 120, 64, 130Dota Structures _ 746. Deiste 52 SK (0) (0) @ & Unbalanced AVL search tree AVL search tree (a) (b) (0) (0) Balanced AVL search tree after R-1 Rotation ) Fig. 7.43 4.13 m-WAY SEARCH TREES Alll the data structures discussed so far favor data stored in the internal memory and hence support internal information retrieval. However, to favor retrieval and manipulation of data stored in external memory, viz., storage devices such as disks etc., there is a need for some special data structures. m-way search trees, B trees and B* trees are examples of such data structures which find application in problems such as fife indexing. m-way search trees are generalized versions of binary search trees. The goal of m-way search (ree is to minimize the accesses while retrieving a key from a file. However, an m-way search tree of height h calls for O(4) nitimber of accesses for an insert/delete/retrieval operation. Hence it pays to ensure that the height / is close to log,,(n +1), because the number of elements in an m-way search tree of height h ranges from a minimum of A to a maximum of m' —1, This implies. that an meway search tree of n elements ranges from a minimum height of log,(n +1) to a maximum height of n. Therefore there arises the need to maintain balanced m-way search trees. B trees are balanced m-way search trees. Definition An m-way search tree T may be an empty tree. If T is non empty, it satisfies the following properties: . 7 oF (i) For some integer m, known as order of the tree, each node is of degree which can reach @ maximum of m, in other words, each node has, at mést_m child nodes. A node’may be~— Tree Delete 120: Delete 64: Delete 190: Ay)» Ky 42): Kyte Ame) where, K, | SiS m- 1 are the keys r 5 Ay Kn corse te subtrees of T. rig gis m-— | are the pointers and Ay 0 5 io Mild nodes where k:S.mb then the node can have only (k— 1) keys Ky Ky ‘partitions all the (ii) If a node has £ hat ‘K, < Kj,1 and each of the keys Ky, containe' keys in the subtrees into id in the node SU7.48 ‘bata Structures i C biree pointed to by (ili) For a node Ag, (Ky, Ay), (Kay Ag)--o(Kn= 1» Am 1s all Key values in the sul i y ate less than the key K;,,,0-< iS m~ 2, and all key values in the subtree pointed to by Ajj. ate greater than K,_) (iv) Each of the subtrees A;, 0 < i$ m— 1 are also m-way search trees. An example of a 5-way Search tree is shown in Fig, 7.45. Observe how each node has at most 5 child nodes and therefore has at most 4 keys contained in it. The rest of the properties of an m-way search tree can also be verified by the example. ie [a] 7 [a8] =Lel 7 {2 eo [oe [141 262] * x x] « x eli] [7] _[ieelisiiva|ies] _[ava] ave [aso x x Tx ] xf» if xfx«f« «[«]«[« Pointer to subtiee [=] sm pointers [| ike elds Fig. 7.45 7.14 SEARCHING, INSERTION AND DELETION IN AN m-WAY SEARCH TREE Searching an m-Way Search Tree Searching for a key in an m-way search tree is similar to that of binary search trees. To search for 77 in the S-way search tree, shown in Fig. 7.45, we begin at the root and as 77 > 76 > 44 > 18, move to the fourth subtree. In the root node of the fourth subtree, 77 < 80 and therefore we move to the first subtree of the node. Since 77 is available in the only node of this subtree, we claim 77 was successfully searched. To search for 13, we begin at the root and as 13 < 18, we move down to the first subtree. Again, since 13 >12 we proceed to move down the third subtree of the node but fall off the tree having encountered a null pointer. Therefore we claim the search for 13 was unsuccessful. Insertion in an m-Way Search Tree To insert a new element into an m-way search tree we proceed in the same way as one would ina null pointer, Si ‘; eo ake re int cr _ Since the Rode has only wo Teed es (7, 12] with the first child node Oe ena: 6 is inserted into the node a S-way search tree can accommo- (148, 151, 172, is already full, as (6, 7, 12). But to insert 146, the node 15) ft her these insertions have been illustrated in Fig. 7 qhen # new child node and Insert 146 jato it. Both 18 | 44 | 76 [198 { «[* T 80 | 92 [141 262 | [T=] Coa “‘eifive[tes] _ [are] 206] 350] rele) Fe Ll Fig. 7.46 Deletion in an m-Way Search Tree Let K be a key to be deleted from the m-way search tree. To delete the key we proceed as one would to search for the key. Let the node accommodating the key be as illustrated in Fig. 7.47. SCE sy T_T a Ay Pomerstosubtees A 4 Fig. 7.47 =A ete K. t to MD then ‘shoose the largest of the key elements K’ in the child node 0 Ay * NOLL, Ay fe the key ’ and replace K by K’. Obviously deletion of K’ may call for Mutvoqvent eplecement ne therefore deletions in a similar manner to enable the key K’ move up the tree, f the key elements K” from the subtree noose the smaltest of the key elemer ponte Ns ULL. a ae place x By", Again deletion of K” may wigger subsequent y Aj ve up the tree. teplacements and deletions to enable K” move UP7.50, Data Structures If (4, # NULL, A; # NULL) then choose either the largest of the key elements K’ in the subtree pointed to by A, or the smallest of the key elements K” from the subtree pointed to by A, to replace K, As mentioned before, to move K’ or K” up the tree it may call for subsequent replacements and deletions. We illustrate deletions on the 5-way search tree shown in Fig, 7.45. To delete 151, we search for 151 and observe that in the leaf node [148, 151, 172, 186] where it is present, both its left subtree pointer and right subtree pointer are such that (A; = 4, = NULL). We therefore simply delete 151 and the node becomes (148. 172. 186] . Deletion of 92 also follows a similar process. To delete 262, we find its left and right subtree pointers A, and A, respectively, are such that (A; = NULL, A; # NULL). Hence we choose the smallest clement 272 from the child node [272, 286, 300}, delete 272 and replace 262 with 272. Note that, to delete 272 the deletion proc needs to be observed again. Figure 7.48 illustrates the deletion of 262. 18 | 44 I 76 [198 Delete 262 and x]* replace with 272 7 Le] 0 | 9 [147 272 @ [ie [7 48 51] 172] 108 286 [850 Fig. 7.48 To delete 12, we find the node [7, 12] accommodates 12 and the key satisfies (A, # NULL, A,= NULL). Hence we choose the largest of the keys from the node pointed to by A,, viz., 10 and replace 12 with 10. Figure 7.49 illustrates the deletion of 12, Delete 12a _[ 78 [aa [76 [708 replace wih pot ‘0 7 [10 we[ra] pase 3 IL _[walisr[vreltes] [ave onafoco Fig. 7.49— — Trees 7.51 Example 7.27 A 3-way search tree constructed out of an i it in the order shown, is illustrated in Fig. 750° fy search ce withthe Flowing Kee D,K,P, V,A,G Insert D: ingortk: © DIK Insert Pv: [PL PLy Insert a, 6: DK [a é Pv Fig. 7.50 Deletion of A and K in the 3-way search tree of Fig. 7.51 yields: 7.15 B TREES m-way search trees have the advantage of minimizing file accesses due to their restricted height. However it is‘essential that the height of the tree be kept as low as possible and therefore there° structures 752 Data St balanced m-way search tree j, balanced m-way search trees. Such @ if! arises the need to maintain what is defined as a B tree. — Definition search tree in which: A Buuee of order m, if non empty,” is an m-way 1 most m child nodes (@__ the root has at least two child nodes and al (ii) the internal nodes except the root have at least [ 2] child nodes and at most m chi nodes. ‘ . ¢ less than the number of child nodes and (iii) the number of keys in each internal node is on janner similar to that of m-way these keys partition the keys in the subtrees of the node in a m search trees. (iv) all Ieaf nodes are op the same level |A Buree of order 3 is referred to as 2-3 tree since the internal nodes are of degree 2 or 3 only. Example 7.28 The tree shown in Fig. 7.52 is a B tree of order 5. All the properties of the B tree can be verified on the tree. aT Te [Ey Pointers tosubirees — ] Key eas [Z) Nupointere 7.16 SEARCHING, INSERTION AND DELETION IN A B-TREE Searching a B-tree Searching for a key in a B-tree is similar to the one o 5 fan me: f accesses depends on the height A of the B-tree. mrway search tes. The number °Trees 7.53 Insertion in a B-tree ‘The insertion of a key in a B-tree proceeds as if one were searching for the key in the tree. When the search terminates in a failure at a leaf node and tends to fall off the tree, the key is inserted according to the following procedure: If the leaf node in which the key is to be inserted is not full, then the insertion is done in the node, A node is said to be full if it contains a maximum of (m — 1) keys, given the order of the B- tree to bem. If the node were to be full, then insert the key in order into the existing set of keys in the node, split the node at its median into two nodes at the same level, pushing the median element up by ‘one level. Note that the split nodes are only’half full. Accommodate the median element in the parent node if it is not full. Otherwise repeat the same procedure and this may even call for rearrangement of the keys in the root node or the formation of a new root itself. Thus a major observation pertaining to insertion in a B-iree is that, since the leaf nodes are all at the same level, unlike m-way search trees, the tree grows upwards. Example 7.29 Consider the B-tree of order 5 shown in Fig. 7.53. Insert the elements 4, 5, 58, 6 in the order given. [elev CLT 1 ] [a lepes[ee] _frosrio]_—_[s7] 45] retells) eb) CEE Fig. 7.53 fe 6 The insertion of the given elements is shown in Fig. 7.54. Note how insertion of 4, 5 is easily done in the first child node of the root since the node is not full. But during the insertion of 58, the second child node of the root, where the insertion reeds to be done is full. Now we insert the key into the list of keys existing in the ode in the Sorted order and split the node into two nodes at the same level at its median, viz., 35, Push the key 55 up to accommodate it in the parent node which is not full. Thus the key 58 is inserted. The insertion of 6 is interesting. The first child node of the root where its place is due, is full. Now the node splits at the median pushing 5 up. But the parent node viz, the root, is also full. This in turn forces a split in the root node resulting in the creation of a new root which is 55. Tt needs to be highlighted that all the keys in the node should be ordered every time there is a rearrangement of keys in a node.7.54 Data Structures Insert 4,5 & [se [n6 21817 wa | 5] 06 ‘oe[no] [ar] 45 SED) Gee Go) Cee Insort se: eae 2[4[s]7 a7 46 se [ee] _[ro[vvo] [797] 148] Inserts: ee 96 [116 ra el? a7 48 58 [06 wos] 90 a7] 165 Deletion in a B-tree While deleting a key it is desirable that the keys in the leaf node are removed, However when a case arises forcing a key that is in an internal node to be deleted, then we promote a successor or a predecessor of the key to be deleted, to occupy the position of the deleted key and such a key is bound to occur in a leaf riode (How?) While removing a key from a leaf node, if the node contains more than the minimum number of elements, then the key can be easily removed. However, if the leaf node contains just the minimum number of elements, then scout for an element from either the left sibling node or right sibling node to fill the vacancy. If the left sibling node has more than the minimum number of keys, pull the largest key up into the parent node and move down the intervening entry from the parent node to the leaf node where the key is to be deleted. Otherwise, pull the smallest key of the right sibling node to the parent node and move down the intervening parent element to the leaf node. If both the sibling nodes have only minimum number of entries, then create a new leaf node out of the two leaf nodes and the intervening element of the parent node, ensuring that the total number does not exceed the maximum limit for a node. If while borrowing the intervening element from the parent node, it leaves the number of keys in the parent node to be below the minimum number, then we propagate the process upwards ultimately resulting in a reduction, of height of the B-tree.Trees 7.55 Example 7.30 Deletion of keys 95, 226, 221 and 70 on a given B-tree of order 5 is shown in Fig. 7.55. The deletion of key 95 is simple and straight since the leaf node has more than the minimum number of elements. To delete 226, the internal node has only the minimum number of elements and hence borrows the immediate successor viz., 300 from the leaf node which has more than the minimum number of elements. Deletion of 221 calls for the hauling of key 440 to the parent node and pulling down of 300 to take the place of the deleted entry in the leaf. Lastly the deletion of 70 is a little more involved in process. Since none of the adjacent leaf nodes can afford lending a key, two of the leaf nodes are combined with the intervening element from the parent to form a new leaf node, viz., [32, 44, 65, 81] leaving 86 alone in the parent node. This is not possible since the parent node is now running low on its minimum number of elements. Hence we once again proceed to combine the adjacent sibling nodes of the specified parent node with a median element of the parent which is the root. This yields the node [86, 110, 120, 440] which is the new root. Observe the reduction in height of the B-tree. | Example 7.31 On the B-tree of order 3 shown in Fig. 7.56, perform the following operations in the order of their appearance: Insert 75, 57 Delete 35, 65 The B-tree after the operations is shown in Fig. 7.57 7.17 HEAP; HEAPSORT This section discusses another tree structure, called a heap. The heap is used in an elegant sorting algorithm called heapsort. Although sorting will be treated mainly in Chapter 9, we give the heapsort algorithm here and compare its complexity with that of the bubble sort and quicksort algorithms, which were discussed, respectively, in Chaps. 4 and 6 Suppose H is a complete binary tree with n elements. (Unless otherwise stated, we assume that His maintained in memory by a linear array TREE using the sequential representation of H, not a linked representation.) Then H is called a heap, ot a maxheap, if each node N of H has the following property: The value at N is greater than or equal to the value at each of the children of N. Accordingly, the value at N is greater than or equal to the-value at any of the descendants of N. (A minheap is defined analogously: The value at N is less than or equal to the value at any of the children of N.)7.56 Data Structures [rao ]z26. [ee] Ta af] cate Come fret ela slaelsola [5 [oe 120] 300 wl] [role] [oo]soo] [iste 200) 221 ‘440 550] 601 [ ] ® [6] ET [eta 100 vis{ria]_—_[200]300] [sso] eon betta 7 36 [110] 120] 440] lle [er so [100] _—_[ris[v8] [oo] a00] [eso] orTrees B-tree of order a) % — 30 | 35 ry Example 7.32 Consider the complete tree H in Fig. 7.58(a). Observe that H is a heap. This means, in particular, that the largest element in H appears at the “top” of the heap, that is, at the root of the tree. Figure 7.58(b) shows the sequential representation of H by the array TREE. That is, TREE[1] is the root of the tree H, and the left and right children of node TREE[K] are, respectively, TREE[2K] and TREE(2K + 1]. This means, in particu- lar, that the parent of any nonroot node TREE[J] is the node TREE[J + 2] (where J + 2 means integer division). Observe that the nodes of H on the same level appear ‘one after the other in the array TREE. Inserting into a Heap Suppose H is a heap with N elements, and suppose an ITEM of information is given. We insert ITEM into the heap H as follows: (1) First adjoin ITEM at the end of H so that H is still a complete tree, but not necessarily @ heap. (2) Then let ITEM rise to its “appropriate place” in H so that H is finally a heap. We illustrate the way this procedure works before stating the procedure formally. Example 7.33 Consider the heap H in Fig. 7.58. Suppose we want to adé ITEM = 70 0 f First we adjoin 70 as the next element in the complete tree; that is, we ser EI (et), 1 e- Thon 40 ig the right child of TREE[10] = 48. The path Fom Tot the rot of Wi pictured in Fig. 7.59(a)- We now find the appropriate place of 70 i P follows:7.58 Data Structures Insert 75: 50 Insert 87: x Le 20] 35 45 35 38 Delete 35, [20 45 58 Delete 65: 20 @ | Fig. 7.57| | | (a) Heap Tate (7 [8] 5] 66] 5] 95[ a] e[35]<0[ =| 6a] 77[25| 50 a] o]so] 623] 1284 5 © 7 B 9 10111219 415 1617 18 1920 (b) Sequentit representation Fig. 7.58 (a) Compare 70 with its parent, 48. Since 70 is greater than 48, interchange 70 and 48; the path will now look like Fig. 7.59(b). (b) Compare 70 with its new parent, 55. Since 70 is greater than 55, interchange 70 and 55; the path will now look like Fig. 7.59(c). 7 97 v7 a i << 2 ‘e “ _ ——_, _ —< “A ON / Ys oo” ee Pe a é a | Fig. 7.59 ITEM = 70 is Inserted 8Data Structures (©) Compare 70 with its new parent, 88. Since 70 does not exceed 88, ITEM = 70 is it iate place in H. Fae 7a) shoe ie final tee. A dotted line indicates that an exchange has taken place. Kemark: One must verify that the above procedure does always yield a heap as a final tree, that is, that nothing else has been disturbed. This is easy to see, and we leave this verification to the reader. Example 7.34 Suppose we want to build a heap H from the following list of numbers: 44, 30, 50, 22, 60, 55, 77, 55 This can be accomplished by inserting the eight numbers one after the other into an empty heap H using the above procedure. Figure 7.60(a) through (h) shows the respective pictures of the heap after each of the eight elements has been inserted. Again, the dotted line indicates that an exchange has taken place during the inser- tion of the given ITEM of information. “ 44 50, a aos 30 30 44 (a) ITEM = 44 (0) TEM = 90 (o) ITEM = 50 50, NN wo 44 Ny 22 (d) ITEM = 22 60 ZO NN 50, 55 y 22 30 44 Ss (f) ITEM = 55Trees The formal statement of our insertion procedure follows: Procedure 7.9: INSHEAP(TREE, N, ITEM) Ah - , : ae ae with N elements is stored in the array TREE, and an ITEM of ation is given. This procedure inserts ITEM as a new element of H. PTR gives the location EM as it ri of ITEM a m Toi ari ation of ITEM as it rises in the tree, and PAR denotes the 1, [Add new node to H and initialize PTR.] Set N :=N + 1 and PTR :=N, 2. [Find location to insert ITEM.] Repeat Steps 3 to 6 while PTR < 1 3. Set PAR := LPTR/2]. {Location of parent node.) 4. If ITEM < TREE[PAR]. then: Set TREE[PTR] := ITEM,-and Return. [End of If structure.] 5. Set TREE[PTR| := TREE[PAR]. [Moves node down.] 6. Set PTR := PAR. (Updates PTR.] IEnd of Step 2 loop.] 7. [Assign ITEM as the root of H.] Set TREE[I] := ITEM. 8. Return, Observe that ITEM is not assigned to an element of the array TREE until the appropriate place for ITEM is found. Step 7 takes care of the special case that ITEM rises to the root TREE(1]. Suppose an array A with N elements is given. By repeatedly applying Procedure 7.9 to A, that is, by executing Call INSHEAP(A, J, AD +.) ay A for J = 1, 2, ..., N- 1, we can build a heap H out of the Deleting the Root of a Heap is a heap with N elements, and suppose we want to delete the root R of H. This is Suppose H ii accomplished as follows: (1) Assign the root R to some variable ITEM. (2) Replace the deleted node R by the last node Lof Hs necessarily a heap. . (3) (Reheap) Let L sink to its appropriate place in the procedure works befo 1 that H is’still a complete tree, but not 1 H so that H is finally @ heap. Agai ustrate the way re stating the procedure formally. ain we illustrate y