(^8) | Chapter 1: Algorithms Matter
Algorithms to the Rescue
A balanced binary tree is a binary search tree for which the length of all paths
from the root of the tree to any leaf node is as close to the same number as
possible. Let’s definedepth(Li) to be the length of the path from the root of the
tree to a leaf nodeLi. In a perfectly balanced binary tree withnnodes, for any two
leaf nodes,L 1 andL 2 , the absolute value of the difference, |depth(L 2 )–depth
(L 1 )|≤1; alsodepth(Li)≤log(n) for any leaf nodeLi.Gary went to one of his algo-
rithms books and decided to modify Graham’s code so that the tree of allocation
records would be balanced by making it a red-black binary tree. Red-black trees
(Cormen et al., 2001) are an efficient implementation of a balanced binary tree in
which given any two leaf nodes L 1 and L 2 , depth(L 2 )/depth(L 1 )≤2; also
depth(Li)≤2log 2 (n+1) for any leaf nodeLi. In other words, a red-black tree is roughly
balanced, to ensure that no path is more than twice as long as any other path.
The changes took a few hours to write and test. When he was done, Gary showed
Graham the result. They ran each of the three programs shown previously.
Figure 1-2. Constructing two sample binary trees
- Throughout this book, all logarithms are computed in base 2.
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