Chapter 17, Problem 11PE

Program Plan Intro

Implementing RedBlackTree

Program plan:

RedBlackTree.java:

• Define the class “RedBlackTree”.
  • Declare “Node” to access the package and variables.
  • Defining the “RedBlackTree()” constructor.
    • Generate empty tree.
  • Defining the “isValid()” method.
    • This function returns a Boolean value by visiting very node.
  • Defining the “exitCount()” function.
    • This computes the exit cost for n-nodes.
    • Returns the value of exit cost.
  • Define a “add()” method which incorporates comparable class.
    • This function used to add a node to the tree.
  • Define a “find()” function.
    • This finds a node in the tree.
    • Return a Boolean value true, if the node is found, otherwise returns a false.
  • Define a “remove()” function.
    • This function removes an object from the tree.
  • Define a method “toString()”.
    • This function gets the information of the subtree.
    • Returns all the elements in inorder method.
  • Define a static method “toString()”, which gets the information of the subtree with given root node.
    • Returns all the elements in inorder with a space between each element.
  • Define a class “Node”.
    • Define a constructor “Node()”.
      • This develops a red node with no information.
        • Define a “setLeftChild()”.
        • • This function used to set the left child.
          • Then update its parent reference data.
        • Define a “setLeftRight()”.
        • • This function used to set the right child.
          • Then update its parent reference data.
        • Define a “addNode()” function.
        • • This function adds a node as descendant.
  • Define a “replacewith()” function.
    • This function updates the parent’s and replace the node’s link.
    • Then update the root reference.
  • Define a “fixAfterAdd()” function.
    • This restores the tree after a new node added.
  • Define a “fixBeforeRemove()” function.
    • This function fixes the tree after a node is removed.
  • Define a “bubbleUp()” function.
    • This function moves a charge from two children of a parent.
  • Define a “bubbleUpFix()” function.
    • This function fixes the negative-red or doble-red violation that caused by bubble up.
    • Returns a true value if the tree is fixed.
  • Define a “fixDoubleRed()” function.
    • This function fixes the double red violation.
  • Define a “fixNegativeRed()” function.
    • This function used to fix the negative red violation.

RedBlackTreeTester.java:

• Define “RedBlackTreeTester” class.
  • Define the “main()” function.
    • Create an object “t” for “RedBlackTreeTester”.
    • Add the tree elements using the object “t”.
    • Now print the output by calling the member functions of “RedBlackTreeTester”.