+1 (315) 557-6473 

Program To Implement Red Black Tree and Binary Tree Using Java Programming Language Assignment Solutions.


Instructions

Objective
Write a java programming assignment to implement red black tree and binary tree.

Requirements and Specifications

Implement red black tree and binary tree in Java programming language

Source Code

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.stream.Collectors;

import org.junit.Assert;

import org.junit.Test;

import static org.junit.Assert.*;

/**

 * Binary Search Tree implementation with a Node inner class for representing

 * the nodes within a binary search tree. You can use this class' insert

 * method to build a binary search tree, and its toString method to display

 * the level order (breadth first) traversal of values in that tree.

 */

public class BinarySearchTree> {

    /**

     * This class represents a node holding a single value within a binary tree

     * the parent, left, and right child references are always be maintained.

     */

    protected static class Node {

        public T data;

        public Node parent; // null for root node

        public Node leftChild;

        public Node rightChild;

        public Node(T data) { this.data = data; }

        /**

         * @return true when this node has a parent and is the left child of

         * that parent, otherwise return false

         */

        public boolean isLeftChild() {

            return parent != null && parent.leftChild == this;

        }

        /**

         * This method performs a level order traversal of the tree rooted

         * at the current node. The string representations of each data value

         * within this tree are assembled into a comma separated string within

         * brackets (similar to many implementations of java.util.Collection).

         * @return string containing the values of this tree in level order

         */

        @Override

        public String toString() { // display subtree in order traversal

            String output = "[";

            LinkedList> q = new LinkedList<>();

            q.add(this);

            while(!q.isEmpty()) {

                Node next = q.removeFirst();

                if(next.leftChild != null) q.add(next.leftChild);

                if(next.rightChild != null) q.add(next.rightChild);

                output += next.data.toString();

                if(!q.isEmpty()) output += ", ";

            }

            return output + "]";

        }

    }

    protected Node root; // reference to root node of tree, null when empty

    /**

     * Performs a naive insertion into a binary search tree: adding the input

     * data value to a new node in a leaf position within the tree. After

     * this insertion, no attempt is made to restructure or balance the tree.

     * This tree will not hold null references, nor duplicate data values.

     * @param data to be added into this binary search tree

     * @throws NullPointerException when the provided data argument is null

     * @throws IllegalArgumentException when the tree already contains data

     */

    public void insert(T data) throws NullPointerException,

          IllegalArgumentException {

        // null references cannot be stored within this tree

        if(data == null) throw new NullPointerException(

            "This RedBlackTree cannot store null references.");

        Node newNode = new Node<>(data);

        if(root == null) { root = newNode; } // add first node to an empty tree

        else insertHelper(newNode,root); // recursively insert into subtree

    }

    /**

     * Recursive helper method to find the subtree with a null reference in the

     * position that the newNode should be inserted, and then extend this tree

     * by the newNode in that position.

     * @param newNode is the new node that is being added to this tree

     * @param subtree is the reference to a node within this tree which the

     * newNode should be inserted as a descenedent beneath

     * @throws IllegalArgumentException when the newNode and subtree contain

     * equal data references (as defined by Comparable.compareTo())

     */

    private void insertHelper(Node newNode, Node subtree) {

        int compare = newNode.data.compareTo(subtree.data);

        // do not allow duplicate values to be stored within this tree

        if(compare == 0) throw new IllegalArgumentException(

            "This RedBlackTree already contains that value.");

        // store newNode within left subtree of subtree

        else if(compare < 0) {

            if(subtree.leftChild == null) { // left subtree empty, add here

                subtree.leftChild = newNode;

                newNode.parent = subtree;

            // otherwise continue recursive search for location to insert

            } else insertHelper(newNode, subtree.leftChild);

        }

        // store newNode within the right subtree of subtree

        else {

            if(subtree.rightChild == null) { // right subtree empty, add here

                subtree.rightChild = newNode;

                newNode.parent = subtree;

            // otherwise continue recursive search for location to insert

            } else insertHelper(newNode, subtree.rightChild);

        }

    }

    /**

     * This method performs a level order traversal of the tree. The string

     * representations of each data value within this tree are assembled into a

     * comma separated string within brackets (similar to many implementations

     * of java.util.Collection, like java.util.ArrayList, LinkedList, etc).

     * @return string containing the values of this tree in level order

     */

    @Override

    public String toString() { return root.toString(); }

    /**

     * Performs the rotation operation on the provided nodes within this BST.

     * When the provided child is a leftChild of the provided parent, this

     * method will perform a right rotation (sometimes called a left-right

     * rotation). When the provided child is a rightChild of the provided

     * parent, this method will perform a left rotation (sometimes called a

     * right-left rotation). When the provided nodes are not related in one

     * of these ways, this method will throw an IllegalArgumentException.

     * @param child is the node being rotated from child to parent position

     * (between these two node arguments)

     * @param parent is the node being rotated from parent to child position

     * (between these two node arguments)

     * @throws IllegalArgumentException when the provided child and parent

     * node references are not initially (pre-rotation) related that way

     */

    private void rotate(Node child, Node parent) throws IllegalArgumentException {

        if (child == null || parent== null || child.parent != parent) {

            throw new IllegalArgumentException();

        }

        if (child.isLeftChild()) {

            Node childRightChild = child.rightChild;

            if (childRightChild != null) {

                childRightChild.parent = parent;

            }

            parent.leftChild = childRightChild;

            if (parent.parent == null) {

                root = child;

            }

            else {

                if (parent.isLeftChild()) {

                    parent.parent.leftChild = child;

                }

                else {

                    parent.parent.rightChild = child;

                }

            }

            parent.parent = child;

            child.rightChild = parent;

        }

        else {

            Node childLeftChild = child.leftChild;

            if (childLeftChild != null) {

                childLeftChild.parent = parent;

            }

            parent.rightChild = childLeftChild;

            if (parent.parent == null) {

                root = child;

            }

            else {

                if (parent.isLeftChild()) {

                    parent.parent.leftChild = child;

                }

                else {

                    parent.parent.rightChild = child;

                }

            }

            parent.parent = child;

            child.leftChild = parent;

        }

    }

    // For the next two test methods, review your notes from the Module 4: Red

    // Black Tree Insertion Activity. Questions one and two in that activity

    // presented you with an initial BST and then asked you to trace the

    // changes that would be applied as a result of performing different

    // rotations on that tree. For each of the following tests, you'll first

    // create the initial BST that you performed each of these rotations on.

    // Then apply the rotations described in that activity: the right-rotation

    // in the Part1 test below, and the left-rotation in the Part2 test below.

    // Then ensure that these tests fail if and only if the level ordering of

    // tree values dose not match the order that you came up with in that

    // activity.

    @Test

    public void week04ActivityTestPart1() {

        // Module 04: Red Black Tree Insert Activity - Step 1 (right rotation).

        BinarySearchTree tree = new BinarySearchTree<>();

        List dataOrder = new ArrayList<>();

        dataOrder.add(42);

        dataOrder.add(25);

        dataOrder.add(67);

        dataOrder.add(16);

        dataOrder.add(32);

        dataOrder.add(57);

        dataOrder.add(82);

        for (Integer i : dataOrder) {

            tree.insert(i);

        }

        System.out.println(tree);

        String expectedString = "[" + dataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";

        Assert.assertEquals(expectedString, tree.toString());

        tree.rotate(tree.root.leftChild, tree.root);

        List rotatedDataOrder = new ArrayList<>();

        rotatedDataOrder.add(25);

        rotatedDataOrder.add(16);

        rotatedDataOrder.add(42);

        rotatedDataOrder.add(32);

        rotatedDataOrder.add(67);

        rotatedDataOrder.add(57);

        rotatedDataOrder.add(82);

        System.out.println(tree);

        expectedString = "[" + rotatedDataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";

        Assert.assertEquals(expectedString, tree.toString());

    }

    @Test

    public void week04ActivityTestPart2() {

        // Module 04: Red Black Tree Insert Activity - Step 1 (right rotation).

        BinarySearchTree tree = new BinarySearchTree<>();

        List dataOrder = new ArrayList<>();

        dataOrder.add(42);

        dataOrder.add(25);

        dataOrder.add(67);

        dataOrder.add(16);

        dataOrder.add(32);

        dataOrder.add(57);

        dataOrder.add(82);

        for (Integer i : dataOrder) {

            tree.insert(i);

        }

        System.out.println(tree);

        String expectedString = "[" + dataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";

        Assert.assertEquals(expectedString, tree.toString());

        tree.rotate(tree.root.leftChild.rightChild, tree.root.leftChild);

        List rotatedDataOrder = new ArrayList<>();

        rotatedDataOrder.add(42);

        rotatedDataOrder.add(32);

        rotatedDataOrder.add(67);

        rotatedDataOrder.add(25);

        rotatedDataOrder.add(57);

        rotatedDataOrder.add(82);

        rotatedDataOrder.add(16);

        System.out.println(tree);

        expectedString = "[" + rotatedDataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";

        Assert.assertEquals(expectedString, tree.toString());

    }

}