Algorithms in a Nutshell

Binary Tree Search | 133

Searching

To insert a node into a red-black tree, we need to find the appropriate place in the

tree where the new node will be placed. When we add the value of 14 to the tree

shown in Figure 5-10, a new node containing 14 will become the right-child of the

leaf node containing the value 13 (labeled “Step 1” in Figure 5-11). Once inserted,

the properties of the red-black tree are violated so the tree must adjust itself. In

Step 2 the colors of the nodes are updated to ensure condition 4 of red-black trees.

In Step 3 the tree is rotated to the right to ensure condition 5 of red-black trees.

Finally, in Step 4 the colors of the nodes are updated to ensure condition 4 of red-

black trees.

Figure 5-11. The four steps in adding key 14 to the red-black tree

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