Complete the provided Red-Black tree program by implementing the method “rebalanceTree” in “RedBlackTree.java”
Complete the code in “SegmentTree.java” and “SegmentNode.java”.
__MACOSX/._homework 4 homework 4/Tree.java homework 4/Tree.java /* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package binarytrees; public class Tree { protected TNode root; /* creates a new empty Tree with a null root */ public Tree() { this.root = null; } /* Returns the root node of this tree */ public TNode getRoot() { return this.root; } /* Updates the root node of this tree */ public void setRoot( TNode root ) { this.root = root; } /* Performs a left rotation at node oldRoot */ void leftRotate(TNode oldRoot) { if( oldRoot==null || oldRoot.getRight()==null ) throw new NullPointerException("ERROR - Attempt to rotate using null pointers"); TNode newRoot = oldRoot.getRight(); TNode oldRootParent = oldRoot.getParent(); if( oldRootParent != null) { if ( oldRootParent.getRight() == oldRoot ) oldRootParent.setRight( newRoot ); else oldRootParent.setLeft( newRoot ); } else{ this.root = newRoot; newRoot.pParent = null; } oldRoot.setRight( newRoot.getLeft() ); newRoot.setLeft( oldRoot ); } /* Performs a right rotation at node oldRoot */ void rightRotate(TNode oldRoot) { if( oldRoot==null || oldRoot.getLeft()==null ) throw new NullPointerException("ERROR - Attempt to rotate using null pointers"); TNode newRoot = oldRoot.getLeft(); TNode oldRootParent = oldRoot.getParent(); if( oldRootParent != null) { if ( oldRootParent.getLeft() == oldRoot ) oldRootParent.setLeft( newRoot ); else oldRootParent.setRight( newRoot ); } else{ this.root = newRoot; newRoot.pParent = null; } oldRoot.setLeft( newRoot.getRight() ); newRoot.setRight( oldRoot ); } } __MACOSX/homework 4/._Tree.java homework 4/Pair.java homework 4/Pair.java package binarytrees; public class Pair <>< s > , T extends Comparable < t >> { S x; T y; /* creates a Pair from the given x, y values */ public Pair(S x, T y) { this.x = x; this.y = y; } /* * Compares the x in the given Pair to the x in this Pair * Returns -1 if this Pair comes first * Returns 0 if these pairs have equal x values * Returns 1 if the given Pair comes first */ public int compareTo(Pair < s, t > node) { if (this.x.compareTo(node.x) == 0) return this.y.compareTo(node.y); return this.x.compareTo(node.x); } public boolean equals(Pair < s, t > node) { return this.compareTo(node) == 0; } @Override @SuppressWarnings("unchecked") //Suppresses warning for cast to Pair public boolean equals(Object aThat) { if (this == aThat) //Shortcut the future comparisons if the locations in memory are the same return true; if (!(aThat instanceof Pair)) return false; Pair < s, t > that = (Pair < s, t > ) aThat; return this.equals(that); //Use above equals method } @Override public int hashCode() { final int prime = 31; int hash = 7; hash = prime * hash + ((x == null) ? 0 : x.hashCode()); hash = prime * hash + ((y == null) ? 0 : y.hashCode()); return hash; /* generate a good hash code for this Pair using prime numbers */ } /* Returns a String representing this Pair */ public String toString() { return "(" + x + ", " + y + ")"; } } __MACOSX/homework 4/._Pair.java homework 4/SegmentNode.java homework 4/SegmentNode.java package binarytrees; /* * Node for segment trees which contains info of type T */ public class SegmentNode extends TNode implements Comparable < segmentnode > { protected Pair < integer, integer =""> range; /* the range of this node (you can change this if you want) */ /* TODO: Add a variable to track the number of line segments that cover this node's range (but not its parent's range) */ /* Constructor to build new nodes. Nodes are created with all pointers as null and with the specified range */ public SegmentNode(Pair < integer, integer > range) { //Set the parent, left, and right connections to NULL using constructor of TNode super(); this.range = range; } public SegmentNode(Integer x, Integer y) { //Set the parent, left, and right connections to NULL using constructor of TNode super(); this.range = new Pair < integer, integer > (x, y); } /* * Compares the data in the given node to the data in this node * Returns -1 if this node comes first * Returns 0 if these nodes have equal keys * Returns 1 if the given node comes first * * You can change the following methods if you really want to but I found them handy */ public int compareTo(SegmentNode node) { return range.compareTo(node.range); } public boolean equals(SegmentNode node) { return this.compareTo(node) == 0; } @Override //Useful for using HashSet public boolean equals(Object aThat) { if (this == aThat) //Shortcut the future comparisons if the locations in memory are the same return true; if (!(aThat instanceof SegmentNode)) return false; SegmentNode that = (SegmentNode) aThat; return this.equals(that); //Use above equals method } @Override //Useful for using HashSet public int hashCode() { return range.hashCode(); } /* Returns the left child of this node */ public SegmentNode getLeft() { return (SegmentNode) super.getLeft(); } /* Returns the right child of this node */ @SuppressWarnings("unchecked") //Suppresses warning for this cast public SegmentNode getRight() { return (SegmentNode) super.getRight(); } /* Sets the left child of this node to the given node */ public void setLeft(SegmentNode node) { super.setLeft(node); } /* Sets the right child of this node to the given node */ public void setRight(SegmentNode node) { super.setRight(node); } /* TODO: * *Inserts the given line segment into the segment tree rooted at this node */ protected void insertLineSegment(Pair < integer, integer > lineSegment) { return; //Currently does nothing } /* TODO: * * Returns the number of line segments that intersect the query point */ protected int lineStabQuery(int point) { return -1; /* replace this once you're calculating the correct value */ } /* Prints the tree starting at this node. The int is to track the current level of the tree we're on. */ public void drawTree(int level) { if (this == null) return; SegmentNode lchild = this.getLeft(); SegmentNode rchild = this.getRight(); if (lchild != null) lchild.drawTree(level + 1); for (int i = 0; i < level; i++) { system.out.print(" ");="" }="" system.out.println(this); //todo (optional): for this print to be more useful you should complete tostring below.="" if (rchild !=" null)" rchild.drawtree(level + 1);="" }="" public string tostring() {="">
"; /* TODO (Optional): Return a string with the data in this node. Useful for debugging. */ } } __MACOSX/homework 4/._SegmentNode.java homework 4/SegmentTree.java homework 4/SegmentTree.java package binarytrees; import java.util.*; public class SegmentTree extends Tree { /* TODO: * * creates a Segment Tree from the input array of 1d line segments */ public SegmentTree(ArrayList <>< integer, integer >> lineSegments) { super(); /* I used HashSet to figure out the unique set of points given by the line segments */ /* You can assume the Pairs (x,y) given in lineSegments will all be of the form x<=y * /* i put my unique points into an arraylist and used collections.sort to sort them but you can try a different approach */="" buildbalancedtreefromarray( /* pass in your sorted data */ );="" /* insert the line segments into your tree */="" //this.getroot().drawtree( 0 ); /* you can use this to draw your tree */="" }="" /* todo:="" * ="" * builds a balanced tree from a given sorted array="" */="" protected void buildbalancedtreefromarray( /* i used a linked list of segmentnodes but you might find a different ds easier to work with */ ) {="" }="" /* returns the number of line segments that intersect the query point */="" public int linestabquery(int point) {="" return this.getroot().linestabquery(point);="" }="" /* returns the root node of this tree */="" public segmentnode getroot() {="" return (segmentnode) this.root;="" }="" }="" __macosx/homework="" 4/._segmenttree.java="" homework="" 4/driver.java="" homework="" 4/driver.java="" import binarytrees.*; ="" import java.util.*;="" public class driver {="" ="" public static final int max_value =" 500000;" public static void main(string[] args) {="" system.out.println("test red-black tree: ");="" system.out.println("---------------------");="" testtreerebalancestring( 20, true );="" testtreerebalancestring( max_value, false );="" testtreerebalanceinteger( 20, true );="" testtreerebalanceinteger( max_value, false );="" system.out.println( );="" ="" system.out.println("test huffman tree: ");="" system.out.println("---------------------");="" string testhuffman =" "aabacccadadadadda";" huffmantree t =" new HuffmanTree( testHuffman );" system.out.println( t );="" system.out.println( );="" system.out.println( );="" ="" system.out.println("test segment tree: ");="" system.out.println("---------------------");="" int[] startpoints =" { 0, -7, -7, -10, -10, -2, -2, 5, 5, 43, 9, 9, 14, 14, -2, 43, -2, 26 };" int[] endpoints =" { 25, 25, -2, -2, 5, 5, 26, 26, 52, 52, 46, 25, 25, 18, 18, 46, 38, 38 };"><>> lineSegments = new ArrayList<>>( ); for(int i=0; i(startPoints[i],endPoints[i]) ); SegmentTree S = new SegmentTree( lineSegments ); int[] queryPoints = { -10, -7, -2, 0, 5, 9, 14, 18, 25, 26, 38, 43, 46, 52 }; if( S.getRoot()!=null ) for(int i=0; i t = new RedBlackTree(); // Time the insert function start = System.currentTimeMillis(); for (i = 1; i < numinserts; i++) {="" data =" createName( i, (int)Math.log(numInserts) );" t.insertredblack( data );="" if( check ){="" system.out.println("insert #" + i + " inserting " + data);="" //uncomment the following line to print errors if your tree violates one of the 5 properties="" //t.checkredblacktree( );="" //uncomment the following lines to print your tree ="" //t.drawtree( );="" //system.out.println();="" }="" }="" end =" System.currentTimeMillis();" if( check )="" system.out.println("time to insert " + numinserts + " numbers with debugging (in seconds): " + ((end - start) / 1000.0));="" else ="" system.out.println("time to insert " + numinserts + " numbers without debugging (in seconds): " + ((end - start) / 1000.0));="" system.out.println( );="" }="" ="" static string createname( int key, int digits )="" {="" int i;="" string str =" "";" for (i =" digits; i "> 0 ; i--) { str += (char) ('0' + key%10); key = key / 10; } return str; } public static void testTreeRebalanceInteger( int numInserts, boolean check ) { int i = 0; Integer data; long start, end; Random random = new Random(); //Create Red-Black Tree that contains Strings RedBlackTree t = new RedBlackTree(); // Time the insert function start = System.currentTimeMillis(); for (i = 1; i < numinserts; i++) {="" data =" random.nextInt(); " t.insertredblack( data );="" if( check ){="" system.out.println("insert #" + i + " inserting " + data);="" //uncomment the following line to print errors if your tree violates one of the 5 properties="" //t.checkredblacktree( );="" //uncomment the following lines to print your tree ="" //t.drawtree( );="" //system.out.println();="" }="" }="" end =" System.currentTimeMillis();" if( check )="" system.out.println("time to insert " + numinserts + " numbers with debugging (in seconds): " + ((end - start) / 1000.0));="" else ="" system.out.println("time to insert " + numinserts + " numbers without debugging (in seconds): " + ((end - start) / 1000.0));="" system.out.println( );="" }="" ="" }="" __macosx/homework="" 4/._driver.java="" homework="" 4/redblacktree.java="" homework="" 4/redblacktree.java="" package binarytrees;=""><>> extends Tree { /* creates a new empty Tree and returns a pointer to it */ public RedBlackTree() { //Set the root to NULL using constructor of Tree super(); } /* Returns the root node of this tree */ @SuppressWarnings("unchecked") //Suppresses warning for this cast public RedBlackNode getRoot() { return (RedBlackNode)this.root; } /* Stores the passed String in the Tree */ public void insertRedBlack( T info ) { boolean flag = true; RedBlackNode current = this.getRoot(); RedBlackNode newNode = new RedBlackNode( info ); if(current == null) { this.setRoot( newNode ); flag = false; } // find the location to insert at while(flag) { if( newNode.compareTo( current )==0 ) { return; // ignore insertion of duplicates } else if( newNode.compareTo( current )<0 ) {="" if( current.getleft() ="= null)" {="" current.setleft( newnode );="" flag =" false;" }="" else // still not at bottom of tree="" {="" current =" current.getLeft();" }="" }="" else="" {="" if (current.getright() ="= null)" {="" current.setright( newnode );="" flag =" false;" }="" else // still not at bottom of tree="" {="" current =" current.getRight();" }="" }="" }="" rebalancetree( newnode );="" }="" ="" /* checks if this tree is correctly formatted. prints when errors occur. */="" public void checkredblacktree( ){="" /*int blackheight ="*/ this.getRoot().checkRedBlackStructure( );" ="" if( this.getroot().color ="= Color.RED )" system.out.println( "error - root node is red" );="" }="" ="" /* todo="" * rebalancetree="" * input: node to start fixing the tree from (climbing up towards the root)="" * output: none="" * ="" * modifies the tree to ensure it follows the 5 rules of red-black trees="" */=""> x ) { /* Check if x is the root and recolor it if it's RED (you can return after fixing it) */ // loop that rebalances up the tree until you reach the root /* while ( fill in your condition ) */ { /* Check if parent is the root and recolor it if it's RED (you can return after fixing it) */ //if this node and its parent are both red, do the following: //if case 1 - recolor parent and parent's sibling node //if case 2 & 3 - fix the zigzag/straight cases with rotations/recolors (you can return after fixing them) //move up the tree } } /* Prints the tree starting at the root of this tree. */ public void drawTree( ){ RedBlackNode root = this.getRoot(); root.drawTree( 0 ); } } __MACOSX/homework 4/._RedBlackTree.java homework 4/RedBlackNode.java homework 4/RedBlackNode.java package binarytrees; /* * Node for red-black trees which contains info of type T */ enum Color { RED, BLACK; } public class RedBlackNode<>> extends TNode { protected Color color; protected T info; /* my stored data */ /* Constructor to build new nodes. Nodes are created as red and contain the given info. */ public RedBlackNode( T info ){ //Set the parent, left, and right connections to NULL using constructor of TNode super( ); //All nodes start as red this.color = Color.RED; this.info = info; } /* * Compares the data in the given node to the data in this node * Returns -1 if this node comes first * Returns 0 if these nodes have equal keys * Returns 1 if the given node comes first */ public int compareTo( RedBlackNode node ){ return info.compareTo( node.info ); } /* Returns the left child of this node */ @SuppressWarnings("unchecked") //Suppresses warning for this cast public RedBlackNode getLeft( ) { return (RedBlackNode)super.getLeft(); } /* Returns the right child of this node */ @SuppressWarnings("unchecked") //Suppresses warning for this cast public RedBlackNode getRight( ) { return (RedBlackNode)super.getRight(); } /* Returns the parent of this node */ @SuppressWarnings("unchecked") //Suppresses warning for this cast public RedBlackNode getParent( ) { return (RedBlackNode)super.getParent(); } /* Returns the sibling of this node */ @SuppressWarnings("unchecked") //Suppresses warning for this cast public RedBlackNode getSibling( ) { return (RedBlackNode)super.getSibling(); } /* Sets the left child of this node to the given node */ public void setLeft( RedBlackNode node ) { super.setLeft( node ); } /* Sets the right child of this node to the given node */ public void setRight( RedBlackNode node ) { super.setRight( node ); } /* Checks if this Tree is correctly formatted. Prints when errors occur. Returns the number of black nodes on path down to leaf. */ public int checkRedBlackStructure( ){ if( this == null ) return 1; int leftcnt = 0; int rightcnt = 0; RedBlackNode lchild = this.getLeft(); RedBlackNode rchild = this.getRight(); if( lchild != null ) leftcnt = lchild.checkRedBlackStructure( ); if( rchild != null ) rightcnt = rchild.checkRedBlackStructure( ); if( leftcnt != rightcnt ) System.out.println( "ERROR - left and right nodes have different black height. Left count = " + leftcnt + " Right count = " + rightcnt ); if( (lchild != null && this.color == Color.RED && lchild.color == Color.RED) || (rchild != null && this.color == Color.RED && rchild.color == Color.RED) ) System.out.println( "ERROR - red node with red child."); if( this.color == Color.BLACK ) return leftcnt + 1; else return leftcnt; } /* Prints the tree starting at this node. The int is to track the current level of the tree we're on. */ public void drawTree( int level ){ if( this == null ) return ; RedBlackNode lchild = this.getLeft(); RedBlackNode rchild = this.getRight(); if( lchild != null ) lchild.drawTree( level+1 ); for( int i=0; i charFreq = new HashMap(); for ( char ch: text.toCharArray() ) { int cnt = 0; if( charFreq.containsKey(ch) ) cnt = charFreq.get(ch); charFreq.put(ch, cnt+1); } //Add the characters to a priority queue based on frequency PriorityQueue pq = new PriorityQueue(); for(Map.Entry entry : charFreq.entrySet()) { Character key = entry.getKey(); Integer freq = entry.getValue(); pq.add( new HuffmanNode(key.toString(),freq) ); } //Merge nodes of the Huffman Tree until the PQ contains only one node HuffmanNode curL = pq.remove(); while( !pq.isEmpty() ) { HuffmanNode curR = pq.remove(); HuffmanNode mergedNode = new HuffmanNode( curL.getCharacters()+curR.getCharacters(), curL.getFrequency()+curR.getFrequency() ); mergedNode.setLeft( curL ); mergedNode.setRight( curR ); pq.add( mergedNode ); curL = pq.remove(); } this.setRoot( curL ); this.compressedText = ""; for ( char ch: text.toCharArray() ) this.compressedText += this.charToHuffmanString( ch ); } /* Returns the root node of this tree */ public HuffmanNode getRoot() { return (HuffmanNode)this.root; } /* Sets the root node of this tree to the node */ public void setRoot( HuffmanNode node ) { super.setRoot( node ); } /* Get original input String provided to the construtor */ public String getOriginalText( ) { return text; } /* Get Huffman code for the input String computed by the construtor */ public String getHuffmanCoding( ) { return compressedText; } /* finds the Huffman code for the char c in the */ public String charToHuffmanString( char c ) { HuffmanNode root = this.getRoot(); return root.charToHuffmanString( c ); } /* Prints the tree starting at the root of this tree. */ public void drawTree( ){ HuffmanNode root = this.getRoot(); root.drawTree( 0 ); } public String toString() { return text + " encodded as " + compressedText; } } __MACOSX/homework 4/._HuffmanTree.java homework 4/HuffmanNode.java homework 4/HuffmanNode.java package binarytrees; public class HuffmanNode extends TNode implements Comparable{ protected String characters; /* the chars associated with this node */ protected int frequency; /* the total frequency of the stored chars */ public HuffmanNode( String characters, int frequency ){ //Set the parent, left, and right connections to NULL using constructor of TNode super( ); this.characters = characters; this.frequency = frequency; } /* Returns the String of the characters associated with this Huffman node */ public String getCharacters( ) { return this.characters; } /* Returns the frequency of the characters associated with this Huffman node */ public int getFrequency( ) { return this.frequency; } /* Returns the left child of this node */ public HuffmanNode getLeft( ) { return (HuffmanNode)super.getLeft(); } /* Returns the right child of this node */ public HuffmanNode getRight( ) { return (HuffmanNode)super.getRight(); } /* Returns the parent of this node */ public HuffmanNode getParent( ) { return (HuffmanNode)super.getParent(); } /* Sets the left child of this node to node */ public void setLeft( HuffmanNode node ) { super.setLeft( node ); } /* Sets the right child of this node to node */ public void setRight( HuffmanNode node ) { super.setRight( node ); } /* finds the Huffman code for the char c in the Huffman Tree */ protected String charToHuffmanString( char c ) { HuffmanNode left = this.getLeft(); HuffmanNode right = this.getRight(); if( left==null && right==null ) return ""; if( left.characters.indexOf( c ) != -1 ) { return "0" + left.charToHuffmanString(c); } else if( right.characters.indexOf( c ) != -1 ) { return "1" + right.charToHuffmanString(c); } else return ""; } /* Prints the tree starting at this node. The int is to track the current level of the tree we're on. */ public void drawTree( int level ){ if( this == null ) return ; HuffmanNode lchild = this.getLeft(); HuffmanNode rchild = this.getRight(); if( lchild != null ) lchild.drawTree( level+1 ); for( int i=0; i< node.frequency ) return -1;="" else if( this.frequency ="= node.frequency )" return 0;="" else ="" return 1;="" }="" }="" __macosx/homework="" 4/._huffmannode.java="" cs5463="" foundations="" of="" software="" homework="" 4="" due="" 4/14/21="" before="" 11:59pm="" (central="" time)="" 1.="" coding="" -="" red-black="" tree="" balancing="" (10="" points)="" complete="" the="" provided="" red-black="" tree="" program="" by="" implementing="" the="" method="" “rebalancetree”="" in="" “redblacktree.java”.="" 2.="" coding="" -="" segment="" tree="" (10="" points)="" complete="" the="" code="" in="" “segmenttree.java”="" and="" “segmentnode.java”.="" 3.="" b-trees="" (4="" points)="" (1)="" (2="" points)="" show="" the="" results="" of="" inserting="" the="" keys="" e,f,g,="" u,="" v,w,h="" in="" order="" into="" the="" b-tree="" shown="" below.="" assume="" this="" b-tree="" has="" minimum="" degree="" k="2." draw="" only="" the="" configurations="" of="" the="" tree="" just="" before="" some="" node(s)="" must="" split,="" and="" also="" draw="" the="" final="" configuration.="" b,d,j="" c="" ni="" p="" m="" o,q="" r,s,ta="" k,l="" (2)="" (2="" points)="" suppose="" you="" have="" a="" b-tree="" of="" height="" h="" and="" minimum="" degree="" k.="" what="" is="" the="" largest="" number="" of="" keys="" that="" can="" be="" stored="" in="" such="" a="" b-tree?="" prove="" that="" your="" answer="" is="" correct.="" (hint:="" your="" answer="" should="" depend="" on="" k="" and="" h.="" this="" is="" similar="" to="" theorem="" we="" proved="" in="" the="" b-tree="" notes).="" 4.="" choose="" function="" (4="" points)="" given="" n="" and="" k="" with="" n="" �="" k="" �="" 0,="" we="" want="" to="" compute="" the="" choose="" function="" ⇣="" n="" k="" ⌘="" using="" the="" following="" recurrence:="" base="" cases:="" ⇣="" n="" 0="" ⌘="1" and="" ⇣="" n="" n="" ⌘="1," for="" n="" �="" 0="" recursive="" case:="" ⇣="" n="" k="" ⌘="⇣" n�1="" k�1="" ⌘="" +="" ⇣="" n�1="" k="" ⌘="" ,="" for="" n=""> k > 0 (1) (1 point) Compute ⇣ 5 3 ⌘ using repeated calls to the above recurrence. (2) (2 points) Give pseudo-code for a bottom-up dynamic programming algorithm to compute ⇣ n k ⌘ using the above recurrence.