Mastering Algorithms With C - Kyle Loudon [91]
Of course, the process of searching a binary tree depends on nodes having been inserted in a similar way. Thus, to insert a node, we start at the root of the tree and descend level by level, moving left or right as appropriate. When we reach the end of a branch, we make the insertion. For example, to insert 65 into the tree of Figure 9.7, we start at the root and move to the right since 65 is greater than 20, then to the right again since 65 is greater than 53, and then to the left since 65 is less than 79. This point is the end of a branch, so we insert the key as the left child of 79. Duplicate keys are not allowed.
Figure 9.7. A binary search tree, including the paths traced while locating 15 and inserting 65
Binary search trees are efficient structures for searching because in the worst case, we only end up searching the data in one branch, instead of having to search every piece of data. Thus, searching becomes an O (lg n) operation, where n is the number of nodes in the tree, provided the tree is kept balanced. Recall that keeping a tree balanced means that it will be as short as possible for a given number of nodes. Keeping a binary search tree balanced is important because it means that no branch we search will be exceptionally long.
To understand further the importance of keeping a binary search tree balanced, consider what happens as a binary search tree becomes more and more unbalanced. As this occurs, searching for a node approaches O (n), which is no better than searching from one end of the data to the next. For example, imagine a binary search tree containing 216 words from a dictionary inserted in alphabetical order (see Figure 9.8). In this case, the tree consists of a single branch to the right, and searching for a word could require inspecting as many as 216 words. However, if we insert the words in a random fashion, the tree should end up at least somewhat balanced, and we can expect to traverse closer to lg 216 = 16 words in the worst case. Since normally the order in which nodes are inserted and removed is not something we can control, we cannot rely on this method to keep a tree balanced. Instead, we must take a more proactive approach.
Figure 9.8. A poorly balanced binary search tree consisting of a single branch to the right
Interface for Binary Search Trees
Name
bistree_init
Synopsis
void bistree_init(BisTree *tree, void (*compare)(const void *key1,
const void *key2), void (*destroy)(void *data));
Return Value
None.
Description
Initializes the binary search tree specified by tree. This operation must be called for a binary search tree before the tree can be used with any other operation. The function pointer compare specifies a user-defined function to compare elements. This function should return 1 if key1 > key2, if key1 = key2, and -1 if key1 < key2. The destroy argument provides a way to free dynamically allocated data when bistree_destroy is called. It works in a manner similar to that described for bitree_destroy. For a binary search tree containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
bistree_destroy
Synopsis
void bistree_destroy(BisTree *tree);
Return Value
None.
Description
Destroys the binary search tree specified by tree. No other operations are permitted after calling bistree_destroy unless bistree_init is called again. The bistree_destroy operation removes all nodes from a binary search tree and calls the function passed as destroy to bistree_init once for each node as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of nodes in the binary search tree.
Name
bistree_insert
Synopsis
int bistree_insert(BisTree *tree, const void *data);
Return Value
0 if inserting the node is successful, 1 if the node is already in the tree, or -1 otherwise.
Description
Inserts a node into the binary search tree specified by tree. The new node contains a pointer