Previous Section
 < Free Open Study > 
Next Section


8.7 Comparing Binary Search Trees and Linear Lists

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 array-based list and the linked list. Like a sorted array-based 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.

Big-O Comparisons

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 case-if the order in which the elements were inserted results in a short, bushy tree-we can find any node in the tree with at most log2N + 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 case-if the elements were inserted in order from smallest to largest, or vice versa-the 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 worst-case analysis, the complexity of the tree operations is identical to the comparable linked-list 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(log2N)] plus tasks that are O(1)-for instance, creating a node, resetting pointers, or copying data. These operations are all described as O(log2N). 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(log2N) operation. (Actually, the two tasks add up to log2N 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(log2N).

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 array-based 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 array-based implementation is based on a binary search.

Table 8.2: Big-O Comparison of List Operations
 

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(log2N)

O(log2N)

O(N)

Process

O(1)

O(1)

O(1)

Total

O(log2N)

O(log2N)

O(N)

InsertItem

     

Find

O(log2N)

O(log2N)

O(N)

Process

O(1)

O(N)

O(1)

Total

O(log2N)

O(N)

O(N)

DeleteItem

     

Find

O(log2N)

O(log2N)

O(N)

Process

O(1)

O(N)

O(1)

Total

O(log2N)

O(N)

O(N)


[*]If the items in the array-based list could possibly contain pointers, the items must be deallocated, making this an O(N) operation.



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