For this assignment, you will be implementing a version of a Red-Black Tree. You

ID: 3859537 • Letter: F

Question

For this assignment, you will be implementing a version of a Red-Black Tree. Your Red-Black tree will be implemented as a Map where each node will store a key (which must be unique) and a value. You must implement your Tree to be generic (keys can be any type that is a subclass of Comparable, and the value can be any type). You are not allowed to use any sorting algorithms in your implementation.

The Node Class

Your node class should include member variables for the key and value you want to store in the node as well as member variables which are pointers to the left and right subtrees, and the parent of the node.

You will also want to keep track of the color of the node.

Add any additional methods / constructors you feel will help. If you are unsure of your design you MUST talk to me ahead of time for approval.

The RBTree Class

The RBTree class should have a member variable that points to the root node of the entire tree.

The RBTree class should have a constant member variable Node with a value of null for its key, null for its value, and all of its pointers are also null. This will be your special NIL leaf that is required of the RBTree. This special node should only have one instantiation in memory (I will be looking for this.)

Add whatever constructors you feel are necessary.

You will want to include the following functionality:a way to find the grandparent of any given node

remember to check for cases where a node might not have a grandparent.

a way to find the uncle of any given node

remember to check for cases where a node might not have an uncle.

a left rotate function

remember to update the parent pointer of each node that changes

remember to connect the correct node back into the tree after the rotation

a right rotate function

remember to update the parent pointer of each node that changes

remember to connect the correct node back into the tree after the rotation

a function to start the insertion process of a new node. (most likely a helper method that calls other methods.)

a function the performs a normal binary search tree insertion (this will be used by your insert method)

a function which checks to see if the tree violates any of the rules of a RB tree and makes the necessary corrections

use the algorithm from the lecture slides.

this will be used by your insert method

add functions for all of the traversals. these functions should return an ArrayList of Nodes in the correct order. you should also incorporate these into your gui (have buttons that can show the results of each traversal).

NOTE: You must implement these WITHOUT using recursion.

preorder: HINT: You will need to use a Stack to implement preorder nonrecursively. Research how to use the Stack class in Java.

inorder: HINT: You will need to use a Stack to implement inorder nonrecursively. Research how to use the Stack class in Java.

postorder: HINT: You will need to use a Stack and a Set to implement postorder nonrecursively. The Set will store nodes that have already been visited. Also you will need to keep track of if you are returning from the left or right subtree.

breadth-first: HINT: You will need to use a Queue to implement breadth-first. Research how to use a Queue in Java.

add any other functionality you feel is necessary. If you are unsure of something be sure to have your design approved by me ahead of time.

Think very carefully about what should be public, private, and protected in your implementation. I will be deducting points when things have the wrong access modifiers.

Explanation / Answer

Recursive:

These are the methods used to print different tree traversals in recursive mode

   public void printInorder() {
       printInOrderRec(root);
       System.out.println("");
   }

   private void printInOrderRec(Node currRoot) {
       if (currRoot == null) {
           return;
       }
       printInOrderRec(currRoot.left);
       System.out.print(currRoot.key + ", ");
       printInOrderRec(currRoot.right);
   }

   public void printPreorder() {
       printPreOrderRec(root);
       System.out.println("");
   }

   private void printPreOrderRec(Node currRoot) {
       if (currRoot == null) {
           return;
       }
       System.out.print(currRoot.key + ", ");
       printPreOrderRec(currRoot.left);
       printPreOrderRec(currRoot.right);
   }

   public void printPostorder() {
       printPostOrderRec(root);
       System.out.println("");
   }

   private void printPostOrderRec(Node currRoot) {
       if (currRoot == null) {
           return;
       }
       printPostOrderRec(currRoot.left);
       printPostOrderRec(currRoot.right);
       System.out.print(currRoot.key + ", ");
   }

Non-Recursive:

package rebt;

import java.util.Scanner;
import java.util.Stack;

public class RedBTree {

private final int COLOR_RED = 0;
private final int COLOR_BLACK = 1;

private class Node {

       int key = -1;
       int color = COLOR_BLACK;
       Node left = nil;
       Node right = nil;
       Node parent = nil;

       Node(int key) {
           this.key = key;
       }
   }

private final Node nil = new Node(-1);
private Node root = nil;

   public void printTree(Node node) {
       if (node == nil) {
           return;
       }
       printTree(node.left);
       System.out.print(((node.color == COLOR_RED) ? "Color: Red " : "Color: Black ") + "Key: " + node.key
               + " Parent: " + node.parent.key + " ");
       printTree(node.right);
   }

   private Node findNode(Node findNode, Node node) {
       if (root == nil) {
           return null;
       }

       if (findNode.key < node.key) {
           if (node.left != nil) {
               return findNode(findNode, node.left);
           }
       } else if (findNode.key > node.key) {
           if (node.right != nil) {
               return findNode(findNode, node.right);
           }
       } else if (findNode.key == node.key) {
           return node;
       }
       return null;
   }

   private void insertNode(Node node) {
       Node temp = root;
       if (root == nil) {
           root = node;
           node.color = COLOR_BLACK;
           node.parent = nil;
       } else {
           node.color = COLOR_RED;
           while (true) {
               if (node.key < temp.key) {
                   if (temp.left == nil) {
                       temp.left = node;
                       node.parent = temp;
                       break;
                   } else {
                       temp = temp.left;
                   }
               } else if (node.key >= temp.key) {
                   if (temp.right == nil) {
                       temp.right = node;
                       node.parent = temp;
                       break;
                   } else {
                       temp = temp.right;
                   }
               }
           }
           setup(node);
       }
   }

   // Takes as argument the newly inserted node
   private void setup(Node node) {
       while (node.parent.color == COLOR_RED) {
           Node uncle = nil;
           if (node.parent == node.parent.parent.left) {
               uncle = node.parent.parent.right;

               if (uncle != nil && uncle.color == COLOR_RED) {
                   node.parent.color = COLOR_BLACK;
                   uncle.color = COLOR_BLACK;
                   node.parent.parent.color = COLOR_RED;
                   node = node.parent.parent;
                   continue;
               }
               if (node == node.parent.right) {
                   // Double rotation needed
                   node = node.parent;
                   rotateLeft(node);
               }
               node.parent.color = COLOR_BLACK;
               node.parent.parent.color = COLOR_RED;
               // if the "else if" code hasn't executed, this
               // is a case where we only need a single rotation
               rotateRight(node.parent.parent);
           } else {
               uncle = node.parent.parent.left;
               if (uncle != nil && uncle.color == COLOR_RED) {
                   node.parent.color = COLOR_BLACK;
                   uncle.color = COLOR_BLACK;
                   node.parent.parent.color = COLOR_RED;
                   node = node.parent.parent;
                   continue;
               }
               if (node == node.parent.left) {
                   // Double rotation needed
                   node = node.parent;
                   rotateRight(node);
               }
               node.parent.color = COLOR_BLACK;
               node.parent.parent.color = COLOR_RED;
               // if the "else if" code hasn't executed, this
               // is a case where we only need a single rotation
               rotateLeft(node.parent.parent);
           }
       }
       root.color = COLOR_BLACK;
   }

   void rotateLeft(Node node) {
       if (node.parent != nil) {
           if (node == node.parent.left) {
               node.parent.left = node.right;
           } else {
               node.parent.right = node.right;
           }
           node.right.parent = node.parent;
           node.parent = node.right;
           if (node.right.left != nil) {
               node.right.left.parent = node;
           }
           node.right = node.right.left;
           node.parent.left = node;
       } else {// Need to rotate root
           Node right = root.right;
           root.right = right.left;
           right.left.parent = root;
           root.parent = right;
           right.left = root;
           right.parent = nil;
           root = right;
       }
   }

   void rotateRight(Node node) {
       if (node.parent != nil) {
           if (node == node.parent.left) {
               node.parent.left = node.left;
           } else {
               node.parent.right = node.left;
           }

           node.left.parent = node.parent;
           node.parent = node.left;
           if (node.left.right != nil) {
               node.left.right.parent = node;
           }
           node.left = node.left.right;
           node.parent.right = node;
       } else {// Need to rotate root
           Node left = root.left;
           root.left = root.left.right;
           left.right.parent = root;
           root.parent = left;
           left.right = root;
           left.parent = nil;
           root = left;
       }
   }

   // Deletes whole tree
   void deleteTree() {
       root = nil;
   }

// Deletion Code .

   // This operation doesn't care about the new Node's connections
   // with previous node's left and right. The caller has to take care
   // of that.
   void transplant(Node target, Node with) {
       if (target.parent == nil) {
           root = with;
       } else if (target == target.parent.left) {
           target.parent.left = with;
       } else
           target.parent.right = with;
       with.parent = target.parent;
   }

   boolean deleteNode(Node z) {
       if ((z = findNode(z, root)) == null)
           return false;
       Node x;
       Node y = z; // temporary reference y
       int y_original_color = y.color;

       if (z.left == nil) {
           x = z.right;
           transplant(z, z.right);
       } else if (z.right == nil) {
           x = z.left;
           transplant(z, z.left);
       } else {
           y = treeMinimum(z.right);
           y_original_color = y.color;
           x = y.right;
           if (y.parent == z)
               x.parent = y;
           else {
               transplant(y, y.right);
               y.right = z.right;
               y.right.parent = y;
           }
           transplant(z, y);
           y.left = z.left;
           y.left.parent = y;
           y.color = z.color;
       }
       if (y_original_color == COLOR_BLACK)
           deleteFixup(x);
       return true;
   }

   public void printInorder() {
       printInOrderRec();
       System.out.println("");
   }

   private void printInOrderRec() {
       if (root == null) {
           return;
       }

       // keep the nodes in the path that are waiting to be visited
       Stack<Node> stack = new Stack<Node>();
       Node node = root;

       // first node to be visited will be the left one
       while (node != null) {
           stack.push(node);
           node = node.left;
       }

// traverse the tree
while (stack.size() > 0) {

           // visit the top node
           node = stack.pop();
           System.out.print(node.key + " ");
           if (node.right != null) {
               node = node.right;

               // the next node to be visited is the leftmost
               while (node != null) {
                   stack.push(node);
                   node = node.left;
               }
           }
       }
   }

   public void printPreorder() {
       printPreOrderRec(root);
       System.out.println("");
   }

   private void printPreOrderRec(Node currRoot) {
       if (currRoot == null) {
           return;
       }
       preorder();
   }

   private void preorder() {
       Stack<Node> stack = new Stack<Node>();
       Node node = root;
       stack.push(node);
       while (!stack.empty()) {
           node = stack.pop();
           System.out.print(node.key + " ");
           if (node.right != null)
               stack.push(node.right);
           if (node.left != null)
               stack.push(node.left);
       }
   }

   public void printPostorder() {
       postorder();
       System.out.println("");
   }

   private void postorder() {
       if (root == null)
           return;

       // final Stack<BinarySearchTreeNodes> stack = new
       // Stack<BinarySearchTreeNodes>();
       // BinarySearchTreeNodes node = root;
       Stack<Node> stack = new Stack<Node>();
       Node node = root;

       while (!stack.isEmpty() || node != null) {
           while (node != null) {
               if (node.right != null)
                   stack.add(node.right);
               stack.add(node);
               node = node.left;
           }

node = stack.pop();

           if (node.right != null && !stack.isEmpty() && node.right == stack.peek()) {
               Node nodeRight = stack.pop();
               stack.push(node);
               node = nodeRight;
           } else {
               System.out.print(node.key + " ");
               node = null;
           }
       }
   }

   void deleteFixup(Node x) {
       while (x != root && x.color == COLOR_BLACK) {
           if (x == x.parent.left) {
               Node w = x.parent.right;
               if (w.color == COLOR_RED) {
                   w.color = COLOR_BLACK;
                   x.parent.color = COLOR_RED;
                   rotateLeft(x.parent);
                   w = x.parent.right;
               }
               if (w.left.color == COLOR_BLACK && w.right.color == COLOR_BLACK) {
                   w.color = COLOR_RED;
                   x = x.parent;
                   continue;
               } else if (w.right.color == COLOR_BLACK) {
                   w.left.color = COLOR_BLACK;
                   w.color = COLOR_RED;
                   rotateRight(w);
                   w = x.parent.right;
               }
               if (w.right.color == COLOR_RED) {
                   w.color = x.parent.color;
                   x.parent.color = COLOR_BLACK;
                   w.right.color = COLOR_BLACK;
                   rotateLeft(x.parent);
                   x = root;
               }
           } else {
               Node w = x.parent.left;
               if (w.color == COLOR_RED) {
                   w.color = COLOR_BLACK;
                   x.parent.color = COLOR_RED;
                   rotateRight(x.parent);
                   w = x.parent.left;
               }
               if (w.right.color == COLOR_BLACK && w.left.color == COLOR_BLACK) {
                   w.color = COLOR_RED;
                   x = x.parent;
                   continue;
               } else if (w.left.color == COLOR_BLACK) {
                   w.right.color = COLOR_BLACK;
                   w.color = COLOR_RED;
                   rotateLeft(w);
                   w = x.parent.left;
               }
               if (w.left.color == COLOR_RED) {
                   w.color = x.parent.color;
                   x.parent.color = COLOR_BLACK;
                   w.left.color = COLOR_BLACK;
                   rotateRight(x.parent);
                   x = root;
               }
           }
       }
       x.color = COLOR_BLACK;
   }

   Node treeMinimum(Node subTreeRoot) {
       while (subTreeRoot.left != nil) {
           subTreeRoot = subTreeRoot.left;
       }
       return subTreeRoot;
   }

   public void consoleUI() {
       Scanner scan = new Scanner(System.in);
       while (true) {
           System.out.println(" 1.- Add items " + "2.- Delete items " + "3.- Find items " + "4.- Print tree "
                   + "5.- Print Prerder Traversal tree " + "6.- Print Inorder Traversal tree "
                   + "7.- Print Postorder Traversal tree " + "8.- Delete tree ");
           int choice = scan.nextInt();

           int item;
           Node node;
           switch (choice) {
           case 1:
               item = scan.nextInt();
               while (item != -999) {
                   System.out.println("Enter -999 to stop inserting:");
                   node = new Node(item);
                   insertNode(node);
                   item = scan.nextInt();
               }
               printTree(root);
               break;
           case 2:
               item = scan.nextInt();
               while (item != -999) {
                   node = new Node(item);
                   System.out.print(" Deleting item " + item);
                   if (deleteNode(node)) {
                       System.out.print(": deleted!");
                   } else {
                       System.out.print(": does not exist!");
                   }
                   item = scan.nextInt();
               }
               System.out.println();
               printTree(root);
               break;
           case 3:
               item = scan.nextInt();
               while (item != -999) {
                   node = new Node(item);
                   System.out.println((findNode(node, root) != null) ? "found" : "not found");
                   item = scan.nextInt();
               }
               break;
           case 4:
               printTree(root);
               break;
           case 5:
               printPreorder();
               break;
           case 6:
               printInorder();
               break;
           case 7:
               printPostorder();
               break;
           case 8:
               deleteTree();
               System.out.println("Tree deleted!");
               break;
           }
       }
   }

   public static void main(String[] args) {
       RedBTree rbt = new RedBTree();
       rbt.consoleUI();
   }
}

Ouput: