Mastering Algorithms With C - Kyle Loudon [102]
Q: In a binary search tree, the successor of some node x is the next largest node after x. For example, in a binary search tree containing the keys 24, 39, 41, 55, 87, 92, the successor of 41 is 55. How do we find the successor of a node in a binary search tree? What is the runtime complexity of this operation?
A: To determine the successor of some node x in a binary search tree, first we locate x. Next, we follow its right pointer, and then from this node, follow as many left pointers as possible until the end of the branch is reached. The node at the end of this branch is the successor of x. The runtime complexity of locating either x or its successor is O (lg n).
Q: In a binary search tree, recall that to insert a node, we trace a specific path to determine the proper point at which to actually insert it. As more and more nodes are inserted into a tree, certain areas within the tree become restricted to certain values. Ultimately, this is why a tree falls out of balance and rotations are performed. In the binary search tree of Figure 9.14, what are the possible values for a node inserted at x?
A: In Figure 9.14, any node we insert at x must contain a value greater than 44 and less than 49 because any node to the left of 49 must be less than 49. On the other hand, the only way for a node to end up in the right subtree of 44 is to be greater than 44.
Figure 9.14. A balanced binary search tree
Related Topics
k-ary trees
Trees that have a branching factor of k. Branching factors of more than two children per node are useful when modeling certain situations, such as the 1-to-n relationship of a parent window and its children in a graphical windowing system, or a directory structure in a file system.
Red-black trees
Binary search trees that keep themselves approximately balanced by maintaining a color with each node, which is either red or black. By enforcing a policy about how nodes can be colored along a branch, red-black trees ensure that no branch will ever become more than twice as long as any other. The worst-case running time of searching a red-black tree is T (n) = 2k lg n, where n is the number of nodes in the tree, k is some constant, and T (n) = k lg n is the time to search a perfectly balanced tree.
Tries
Search trees used primarily to search sets of variable-length strings. Conceptually, the nodes at each level in a trie (pronounced "try") represent all characters found at a particular position in the strings being searched. For example, the nodes immediately below the root represent all possible characters in position 1 of the strings, the next level represents all possible characters in position 2, and so forth. Thus, to look up a string, we start at the root and at each level follow the pointer to the node containing the next character in the string we are searching for. This procedure results in search times that are dependent on the size of the search string rather than the number of strings being searched.
B-trees, B+-trees, and B*-trees
Search trees typically used by database systems to improve the performance of accessing data stored on secondary storage devices. Generally, node size is optimized to coincide with the block size of the secondary storage device. All types of B-trees are balanced and typically have a large branching factor. This reduces the number of levels that must be traversed to get at a particular record, thus saving costly accesses to I/O.
Chapter 10. Heaps and Priority Queues
Many problems rely on being able to determine quickly the largest or smallest element from a set that is undergoing frequent insertions