Write a method for the RedBlackTree class of Worked Example 17.2 that checks that the tree fulfills the rules for a red-black tree.

Data from worked example 17.2

  The code for fixing up a double-red violation is quite long. Recall that there are four possible arrangements of the double red nodes:

Transcribed Image Text:

WORKED EXAMPLE 17.2 Implementing a Red-Black Tree Problem Statement Implement a red-black tree using the algorithm for adding and removing elements from Section 17.5. Read that section first if you have not done so already. The Node Implementation The nodes of the red-black tree need to store the "color", which we represent as the cost of traversing the node: static final int BLACK = 1; static final int RED = 0; private static final int NEGATIVE RED = -1; private static final int DOUBLE BLACK = 2; static class Mode { public Comparable data; public Node left; public Node right; public Node parent; public int color; } The first two color constants and the Mode class have package visibility. We will add a test class to the same package, which is discussed later in this worked example. Nodes in a red-black tree also have a link to the parent. When adding or moving a node, it is important that the parent and child links are synchronized. Because this synchronization is tedious and error-prone, we provide several helper methods: public class RedBlackTree { static class Mode {