< Free Open Study > 
A binary search tree is an appropriate structure for many of the same applications discussed previously in conjunction with other sorted list structures. The special advantage of using a binary search tree is that it facilitates searching, while conferring the benefits of linking the elements. It provides the best features of both the sorted arraybased list and the linked list. Like a sorted arraybased list, it can be searched quickly, using a binary search. Like a linked list, it allows insertions and deletions without having to move data. Thus this structure is particularly suitable for applications in which search time must be minimized or in which the nodes are not necessarily processed in sequential order.
As usual, a tradeoff exists. The binary search tree, with its extra pointer in each node, takes up more memory space than a singly linked list does. In addition, the algorithms for manipulating the tree are somewhat more complicated. If all of the list's uses involve sequential rather than random processing of the elements, the tree may not be as good a choice as a linked list.
Suppose we have 100,000 customer records in a list. If our main activity is to send out updated monthly statements to the customers and if the order in which the statements are printed matches the order in which the records appear on the list, a linked list would be suitable. But suppose we decide to keep a terminal available to give out account information to the customers whenever they ask. If the data are kept in a linked list, the first customer on the list can be given information almost instantly, but the last customer has to wait while the application examines the other 99,999 records. When direct access to the records is a requirement, a binary search tree represents a more appropriate structure.
Finding the node to process (FindNode), as we would expect in a structure dedicated to searching, is the most interesting operation to analyze. In the best caseif the order in which the elements were inserted results in a short, bushy treewe can find any node in the tree with at most log_{2}N + 1 comparisons. We would expect to locate a random element in such a tree much faster than we could find such an element in a sorted linked list. In the worst caseif the elements were inserted in order from smallest to largest, or vice versathe tree won't really be a tree at all; it is a linear list, linked through either the left or right data members. This structure is called a "degenerate" tree. In this case, the tree operations should perform much the same as the operations on a linked list. Therefore, in a worstcase analysis, the complexity of the tree operations is identical to the comparable linkedlist operations. In the following analysis, however, we assume that the items are inserted into the tree in random order to produce a balanced tree.
The InsertItem, DeleteItem, and RetrieveItem operations basically involve finding the node [O(log_{2}N)] plus tasks that are O(1)for instance, creating a node, resetting pointers, or copying data. These operations are all described as O(log_{2}N). The DeleteItem operation consists of finding the node plus DeleteNode. In the worst case (deleting a node with two children), DeleteNode must find the replacement value, an O(log_{2}N) operation. (Actually, the two tasks add up to log_{2}N comparisons, because if the delete node is higher in the tree, fewer comparisons are needed to find it, and more comparisons may be needed to find its replacement node.) Otherwise, if the deleted node has zero or one child, DeleteNode is an 0(1) operation. Thus DeleteItem may also be described as O(log_{2}N).
The observer operations IsFull and IsEmpty have O(1) complexity because the number of items in the structure does not affect these operations. LengthIs, however, is different. As we said in Chapter 5, the length data member must be present in arraybased implementations, but is a design choice in linked implementations. In the implementations in Chapter 5, we chose to keep a length field rather than counting the number of items when the LengthIs member function is called. In our tree implementation, we have the same choice; we chose to count the number of items on the list when LengthIs is called. Therefore, the order of the tree implementation is O(N).
The MakeEmpty, Print, and destructor operations require the tree to be traversed, processing each element once. Thus they have O(N) complexity. Table 8.2 compares the orders of magnitude for the tree and list operations as we have coded them. The binary search tree operations are based on a random insertion order of the items; the find operation in the arraybased implementation is based on a binary search.
Binary Search Tree 
Arra Based Linear List 
Linked List 




Class constructor 
O(1) 
O(1) 
O(1) 
Destructor 
O(N) 
O(1)^{[*]} 
O(N) 
MakeEmpty 
O(N) 
O(1)^{[*]} 
O(N) 
LengthIs 
O(N) 
O(1) 
O(1) 
IsFull 
O(1) 
O(1) 
O(1) 
IsEmpty 
O(1) 
O(1) 
O(1) 
RetrieveItem 

Find 
O(log_{2}N) 
O(log_{2}N) 
O(N) 
Process 
O(1) 
O(1) 
O(1) 
Total 
O(log_{2}N) 
O(log_{2}N) 
O(N) 
InsertItem 

Find 
O(log_{2}N) 
O(log_{2}N) 
O(N) 
Process 
O(1) 
O(N) 
O(1) 
Total 
O(log_{2}N) 
O(N) 
O(N) 
DeleteItem 

Find 
O(log_{2}N) 
O(log_{2}N) 
O(N) 
Process 
O(1) 
O(N) 
O(1) 
Total 
O(log_{2}N) 
O(N) 
O(N) 


< Free Open Study > 
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) 