Algorithms in a Nutshell

(^132) | Chapter 5: Searching
Now we want to add a node with a key of 14. Using the standard semantics of
binary trees, 14 will be inserted as the right child of the node with value 13. The
red-black tree insertion algorithm modifies the tree as shown in Figure 5-11; we
describe this process in the “Solution” section, next.
Solution
Searching a red-black tree is no different than searching any binary tree. The code
to search for a value stored in a red-black tree is shown in Example 5-9. Starting at
the root, we inspect each node for the given key value, traversing to the left child
if the key is smaller than the node’s key, and traversing to the right child if the key
is larger than the node’s key.
The key to the red-black tree algorithm is maintaining the red-black conditions
when values are inserted and deleted. We describe the insertion process here; the
deletion procedure is sufficiently complex that we leave the details for the imple-
mentation, which you can find in thealgs.model.tree.BalancedTreeclass. Further
details can be found in (Cormen et al. 2001).
Figure 5-10. Sample red-black tree
Example 5-9. Java implementation of search
public V search(K k) {
BalancedBinaryNode<K,V> p = root;
while (p != null) {
int cmp = compare(k, p.key);
if (cmp == 0) {
return p.value;
} else if (cmp < 0) {
p = p.left;
} else {
p = p.right;
}
}
// not found
return null;
}
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use