Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

import java.util.ArrayList; enum TREETYPE {BST, AVL, SPLAY}; public class WirelessPower…

  1. User

    import java.util.ArrayList;

    enum TREETYPE {BST, AVL, SPLAY};

    public class WirelessPower { public int DEFAULT_HEIGHT = 0; public int DEFAULT_ID = 0; public int MINID = 10000; public int MAXID = 99999; public int MINLAT = -90; public int MAXLAT = 90; public int MINLONG = -180; public int MAXLONG = 180;

    /**

    • The constructor performs the required initializations. It creates an empty object. It also
    • specifies the type of the tree. The tree can be a regular BST which does not perform any
    • re-structuring. It can be an AVL tree which re-balances the tree after every insertion or removal.
    • The third type is a Splay tree which splays the accessed node to the tree root.
    • @param type one of the enumerators ot TREETYPE */ public WirelessPower(TREETYPE type) { this.m_type = type; // Initalize m_type to type of tree m_root = null; // Initalzing root of the tree to null }

    /**

    • @return the enumerated type of TREETYPE */ TREETYPE getType() {

      return m_type; // returning the type of tree. }

    /**

    • Copy constructor for WirelessPower */ public WirelessPower(WirelessPower rhs) { //Copying the type of tree m_type = rhs.m_type; //Deep copy of the tree. m_root = copyOfTree(rhs.m_root); }

    /**

    • This function inserts a Customer object into the tree in the proper position.
    • The Customer::m_id should be used as the key to traverse the WirelessPower tree
    • and abide by BST traversal rules. The comparison operators (>, <, ==, !=) work with
    • the int type in C++. A Customer id is a unique number in the range MINID - MAXID.
    • We do not allow a duplicate id or an object with invalid id in the tree.
    • Note:
    • • In the WirelessPower tree data structure every node is a Customer object which is
    •  represented as a pointer to the Customer object. Therefore, for every insertion we 
      
    •  need to allocate memory and use the information of customer to initialize the new node. 
      
    •  Memory allocation takes place in the WirelessPower class.
      
    • • If the tree type is BST, after an insertion, we should update the height for all nodes
    •  in the insertion path.
      
    • • If the tree type is AVL, after an insertion, we should update the height of each node in
    •  the insertion path as well as check for an imbalance at each node in this path.
      
    • • If the tree type is SPLAY, after and insertion, we need to splay the inserted node
    •  and bring it to the root of the tree while the tree preserves the BST property as well as updating the node heights.
      

    */ // aCustomer here is the ID.. public void insert(Customer aCustomer) {

    //ArrayList to keep Track of nodes. ArrayList tempNodes = new ArrayList<>();

    // Check for valid range of ID
    if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) {
        return;
    }
    
    // Check if tree is empty 
    if (isEmpty()) {
        // Create a new customer node and set it as the root since tree is empty
        m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
    
        return;
    }
    // To determine which type of insertion to use / rebalance as well
    switch (getType()) {
        case BST:
            m_root = insertBST(m_root, aCustomer,tempNodes);
            balance(tempNodes);
            break;
        case AVL:
            m_root = insertAVL(m_root, aCustomer,tempNodes);
            balance(tempNodes);
            break;
        case SPLAY:
           // m_root = insertBST(m_root, aCustomer);
            m_root = splay(m_root, aCustomer);
            break;
    }
    

    }

    /**

    • The clear function makes it an empty tree. */ public void clear() { m_root = null; }

    /**

    • The remove function traverses the tree to find a node with the id and removes

    • it from the tree. In the case of BST or AVL tree the remove function should also update

    • the heights for all nodes in the removal path. If the tree type is SPLAY, the remove

    • function does not remove the node. */ public void remove(int id) { ArrayList tempNodes = new ArrayList<>();

      switch (getType()) { case BST: m_root = deleteRecursively(m_root, id,tempNodes);

           break;
       case AVL:
           m_root = deleteRecursively(m_root, id,tempNodes);
      
           break;
       case SPLAY:
           //Do nothing if SPLAY tree
           break;
      

      } }

    /**

    • This function sets the type of an existing WirelessPower object. Once the type is changed,
    • the function should re-structure the tree according to the following rules:
    • • If the type is changed from BST or SPLAY to AVL, the function should reconstruct the
    •  tree as an AVL tree. In the case of reconstruction the nodes are transferred from the 
      
    •  old tree to the new tree. There should not be any reallocation of memory.
      
    • • If the type is changed from AVL to BST or Splay, there is no need for reconstruction.
    •  After change the tree operations will perform according to the new type.
      
    • • Any change between BST and SPLAY types will not trigger a reconstruction. After
    •  change the tree operations will perform according to the new type.
      

    */ public void setType(TREETYPE type) { //If the new type is the same as current just return //Nothing to do. if(m_type == type) { return; }

    switch(m_type) {
        //AVL doesn't need to be reconstructed to BST or SPLAY
        case AVL:
        //Just update the variable to tree type instead.
        if (type == TREETYPE.BST || type == TREETYPE.SPLAY) {
            m_type =type; // Update the type
        }
        break;
        case BST:
            if(type == TREETYPE.AVL){
                BstToAVL();
                m_type = type;
            } else {
                m_type = type;
            }
        break;
        case SPLAY:
            if(type == TREETYPE.AVL) {
                BstToAVL();
                m_type = type;
            }
        break;
        default:
        break;
    }
    

    }

    /**

    • creates an exact deep copy of the rhs. */ public Customer copy(WirelessPower rhs) { //Create a new customer root to hold for the copy of tree //But first check if it's empty. if(rhs.m_root == null) { return null; } //Copying the nodes recursively. Customer nRoot = copyOfTree(rhs.m_root); return nRoot; }

    public String dumpTree() { String result = ""; result = dump(m_root, result); return result; }

    public String dump(Customer aCustomer, String result) { if (aCustomer == null) { return result; } //System.out.print("Customer: "+aCustomer.getID()+" result: "+result); result += "("; result = dump(aCustomer.m_left, result);// first visit the left child result += aCustomer.m_id + ":" + aCustomer.m_height;// second visit the node itself result = dump(aCustomer.m_right, result);// third visit the right child result += ")"; return result; }

    // *********************************************************************************************** // Used for testing - provided for you // *********************************************************************************************** public Customer getRoot() { return m_root; }

    public String listCustomers() { String result = ""; result = list(m_root, result); return result.trim(); }

    private String list(Customer aCustomer, String result) { if (aCustomer == null) { return result; } //System.out.println("Customer: " + aCustomer.getID() + " result: " + result); result = list(aCustomer.m_left, result);// first visit the left child // second visit the node itself result += aCustomer.m_id + ":" + aCustomer.getLatitude() + ":" + aCustomer.getLongitude() + "\n"; result = list(aCustomer.m_right, result);// third visit the right child return result; }

    private Customer m_root; //the root of the BST private TREETYPE m_type; // the type of tree, BST, AVL or SPLAY

    // *************************************************** // Any private helper functions must be delared here! // ***************************************************

    //Function to check if tree is empty. private boolean isEmpty() { return m_root == null; }

    //Helper function to recursively copy a tree structure private Customer copyOfTree(Customer node){ //Base case if(node == null) { return null; } //Creating a new customer with the same properties.. Customer newCustomer = new Customer(node.getID(),node.getLatitude(),node.getLongitude());

    //Recursively copy the left and right child
    newCustomer.setLeft(copyOfTree(node.getLeft()));
    newCustomer.setRight(copyOfTree(node.getRight()));
    //Also copying the height
    newCustomer.setHeight((node.getHeight()));
    
    return newCustomer;
    

    }

    //Calculate balance factor. private int getBalance(Customer node) { // Base case if (node == null) { return 0; }

    int leftHeight = getHeight(node.getLeft());
    int rightHeight = getHeight(node.getRight());
    
    return leftHeight - rightHeight; 
    

    }

    //AVL Balance private Customer balance(ArrayList node) { // Traverse from bottom (the most recently inserted node) to the root for (int i = node.size() - 1; i >= 0; i--) { Customer currNode = node.get(i); // Update the height of the current node updateHeight(currNode);

        // Balance the current node and set it to its parent
        Customer balancedNode = performRotation(currNode);
        
        // Update the current node's reference in the parent
        if (i > 0) {
            Customer parentNode = node.get(i - 1);
            if (parentNode.getLeft() == currNode) {
                parentNode.setLeft(balancedNode);
            } else {
                parentNode.setRight(balancedNode);
            }
        } else {
            return balancedNode; // Return the new root if we're at the top
        }
    }
    return node.get(0); // Return the root node at the end
    

    }

    private Customer performRotation(Customer node) { // Left Left Case if (getBalance(node) > 1 && getBalance(node.getLeft()) >= 0) { return rightRotate(node); } // Left Right Case if (getBalance(node) > 1 && getBalance(node.getLeft()) < 0) { node.setLeft(leftRotate(node.getLeft())); return rightRotate(node); } // Right Right Case if (getBalance(node) < -1 && getBalance(node.getRight()) <= 0) { return leftRotate(node); } // Right Left Case if (getBalance(node) < -1 && getBalance(node.getRight()) > 0) { node.setRight(rightRotate(node.getRight())); return leftRotate(node); } return node; // Return node if no rotations were needed }

    //Perform right rotation for AVL tree. private Customer rightRotate (Customer y) { //Making x the new root of the subtree. Customer x = y.getLeft(); //Storing the right child of x. Customer temp = x.getRight();

    //Rotate to ->
    //y becomes the right child of x
    x.setRight(y);
    //temp(the right child of x) becomes the left child
    //Of y
    y.setLeft(temp);
    
    //Now we update the heights.
    updateHeight(y);
    updateHeight(x);
    
    //New root
    return x;
    

    }

    //Perform left rotation for AVL tree. private Customer leftRotate(Customer y) { //Making x the new root of the subtree. Customer x = y.getRight(); //Storing the left child of x Customer temp = x.getLeft();

    //Rotate to <- 
    //y become the left child of x.
    x.setLeft(y);
    //temp(the left child of x) becomes the right child
    //Of Y
    y.setRight(temp);
    
    //Update height
    updateHeight(y);
    updateHeight(x);
    
    return x;
    

    }

    //Rotate function for splay to the left. private Customer leftRotateSplay(Customer x) {

    // No rotation possible for these two cases 
    if(x == null) {
        return x;
    }
    
    if(x.getRight() == null) {
        return x;
    }
    //Y is the new root after totation
    Customer y = x.getRight();
    //Move the left child of y to be the right child of x 
    x.setRight(y.getLeft());
    //Rotatiing here
    y.setLeft(x);
    
    updateHeight(x);
    updateHeight(y);
    return y;
    

    }

    //Rotate function for splay to the right private Customer rightRotateSplay (Customer x ) {

    // No rotation possible for these two cases 
    if(x == null) {
        return x;
    }
    
    if(x.getLeft() == null) {
        return x;
    }
    
    //Y is the new root after rotation
    Customer y = x.getLeft();
    //Move the right child of y to be the left child of x
    x.setLeft(y.getRight());
    //Rotating here
    y.setRight(x);
    
    updateHeight(x);
    updateHeight(y);
    return y; 
    

    }

    //Updates the height of tree. private void updateHeight(Customer node) { if (node != null) { // Calculate the height of left and right children int leftHeight = getHeight(node.getLeft()); int rightHeight = getHeight(node.getRight());

    // Update the height of the current node
    node.setHeight(1 + Math.max(leftHeight, rightHeight));
    

    } }

    // Get the height of a node private int getHeight(Customer node) { if (node == null) { return -1; // } else { return node.getHeight(); } }

    //Deletes nodes from a tree recursively. private Customer deleteRecursively(Customer node, int id, ArrayList pathNodes) { if (node == null) { return null; // Node not found, return null }

    // Add the current node to the path
    pathNodes.add(node);
    
    if (id < node.getID()) {
        node.setLeft(deleteRecursively(node.getLeft(), id, pathNodes));
    } else if (id > node.getID()) {
        node.setRight(deleteRecursively(node.getRight(), id, pathNodes));
    } else {
        // Node to be deleted found
        if (node.getLeft() == null) {
            return node.getRight(); // No left child, replace with right child
        } else if (node.getRight() == null) {
            return node.getLeft(); // No right child, replace with left child
        }
    
        // Node with two children: Get the inorder successor
        Customer temp = minValueNode(node.getRight());
    
        // Copy the inorder successor's data to this node
        node.setID(temp.getID());
        node.setLatitude(temp.getLatitude());
        node.setLongitude(temp.getLongitude());
    
        // Delete the inorder successor
        node.setRight(deleteRecursively(node.getRight(), temp.getID(), pathNodes));
    }
    
    // After deletion, update the height and rebalance
    updateHeight(node);
    return balance(pathNodes); // Rebalance after deletion
    

    }

    private Customer minValueNode(Customer node) { Customer current = node; while (current.getLeft() != null) { current = current.getLeft(); } return current; }

    //Help find the mininum private Customer findMin(Customer node) { //Go to the left most child in tree (Min) while(node.getLeft() != null & node.getLeft() != null) { node = node.getLeft(); } return node; }

    public void BstToAVL() { // Creating an ArrayList to hold the nodes in sorted order ArrayList nodeList = new ArrayList<>();

    // Filling the ArrayList with nodes in sorted order
    traverseInOrder(m_root, nodeList);
    
    // Converting the ArrayList to an AVL tree
    m_root = arrayToAVL(nodeList, 0, nodeList.size() - 1);
    

    }

    // Recursively build the AVL tree subtrees private Customer arrayToAVL(ArrayList nodeList, int start, int end) { // No elements left in our tree if (start > end) { return null; } // Find the middle of the ArrayList. int mid = (start + end) / 2; // Create a root node Customer node = nodeList.get(mid);

    // Create the left subtree 
    node.setLeft(arrayToAVL(nodeList, start, mid - 1));
    // Create the right subtree
    node.setRight(arrayToAVL(nodeList, mid + 1, end));
    
    return node;
    

    }

    // Traverse tree in order (Left subtree then root, then right subtree) // While storing the values into our ArrayList. private void traverseInOrder(Customer node, ArrayList nodeList) { // If node is null, no nodes left if (node == null) { return; } // Traverse left of subtree first traverseInOrder(node.getLeft(), nodeList); // Add the current node to our ArrayList nodeList.add(node); // Traverse right of subtree afterwards traverseInOrder(node.getRight(), nodeList); }

    //Helper function to insert a BST Tree. private Customer insertBST(Customer node, Customer aCustomer, ArrayList tempNodes) { //Base case if (node == null) { return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); }

    //If key already in the tree return the node.
    //No Duplicates.
    if(node.getID() == aCustomer.getID()) {
        return node;
    }
    
    //Adding current node to the list
    tempNodes.add(node);
    
    //Down the tree..
    if(aCustomer.getID() < node.getID()) {
        node.setLeft(insertBST(node.getLeft(), aCustomer, tempNodes));
    } else {
        node.setRight(insertBST(node.getRight(), aCustomer, tempNodes));
    }
    
    //Update the height of the ancestor node
    updateHeight(node);
    
    return node;
    

    }

    //AVL Insertion private Customer insertAVL(Customer node, Customer aCustomer, ArrayList tempNodes) { // If the tree is empty, create a new node and return it if (node == null) { return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); }

    // If the key already exists, return the node (no duplicates)
    if (node.getID() == aCustomer.getID()) {
        return node; // Early return to prevent infinite recursion on duplicates
    }
    
    // Add the current node to the list
    tempNodes.add(node);
    
    // Traverse the tree and insert the new customer
    if (aCustomer.getID() < node.getID()) {
        System.out.println("Going left: " + node.getID());
        node.setLeft(insertAVL(node.getLeft(), aCustomer, tempNodes));
    } else {
        System.out.println("Going right: " + node.getID());
        node.setRight(insertAVL(node.getRight(), aCustomer, tempNodes));
    }
    
    // Update the height of the ancestor node
    updateHeight(node);
    
    // Balance the node and return the potentially new root of this subtree
    return balance(tempNodes);
    

    }

    private Customer splay(Customer node, Customer aCustomer) { // Base case: if node is null or key is found if (node == null || node.getID() == aCustomer.getID()) { return node; }

    // Our ID is in the left subtree
    if (aCustomer.getID() < node.getID()) {
        // If left child is null return node (key not found)
        if (node.getLeft() == null) {
            return node;
        }
    
        // Zig-Zig (Left Left)
        if (aCustomer.getID() < node.getLeft().getID()) {
            // splay the left left grandchild
            node.getLeft().setLeft(splay(node.getLeft().getLeft(), aCustomer));
            // perform first right rotation
            node = rightRotateSplay(node);
        }
        // Zig-Zag (Left Right)
        else if (aCustomer.getID() > node.getLeft().getID()) {
            // splay the left right grandchild
            node.getLeft().setRight(splay(node.getLeft().getRight(), aCustomer));
            // perform left rotation on left child
            if (node.getLeft().getRight() != null) {
                node.setLeft(leftRotateSplay(node.getLeft()));
            }
        }
    
        //second right rotation if needed
        if (node.getLeft() == null) {
            // return the current node if the left child is null
            return node; 
        } else {
            return rightRotateSplay(node);
        }
    } else {
    // Our id in the right subtree
        // If right child is null return node (key not found)
        if (node.getRight() == null) {
            return node;
        }
        // Zag-Zag (Right Right)
        if (aCustomer.getID() > node.getRight().getID()) {
            //splay the right-right grandchild
            node.getRight().setRight(splay(node.getRight().getRight(), aCustomer));
            //first left rotation
            node = leftRotateSplay(node);
        } 
        // Zag-Zig (Right Left)
        else if (aCustomer.getID() < node.getRight().getID()) {
            // splay the right-left grandchild
            node.getRight().setLeft(splay(node.getRight().getLeft(), aCustomer));
            //right rotation on right child
            if (node.getRight().getLeft() != null) {
                node.setRight(rightRotateSplay(node.getRight()));
            }
        }
    
        if (node.getRight() == null) {
            return node; 
        } else {
            return leftRotateSplay(node); 
        }
    }
    

    }

    class Customer { int DEFAULT_HEIGHT = 0; int DEFAULT_ID = 0;

    Customer(int id, double lat, double longitude){
        m_id = id; m_latitude = lat; m_longitude = longitude;
        m_left = null; m_right = null; m_height = DEFAULT_HEIGHT;
    }
    //used for testing that ids are put in trees correctly
    Customer(int id){
        m_id = id; m_latitude = 0; m_longitude = 0;
        m_left = null; m_right = null; m_height = DEFAULT_HEIGHT;
    
    }
    int getHeight() {return m_height;}
    Customer getLeft() {return m_left;}
    Customer getRight() {return m_right;}
    int getID() {return m_id;}
    double getLatitude() {return m_latitude;}
    double getLongitude() {return m_longitude;}
    void setID(int id){m_id=id;}
    void setLatitude(double lat) {m_latitude=lat;}
    void setLongitude(double longitude) {m_longitude=longitude;}
    void setHeight(int height){m_height=height;}
    void setLeft(Customer left){m_left=left;}
    void setRight(Customer right){m_right=right;}
    String getLatStr() {
        String text = "";
        int latSeconds = (int)(Math.abs(m_latitude * 3600));
        int latDegrees = latSeconds / 3600;
        latSeconds = latSeconds % 3600;
        int latMinutes = latSeconds / 60;
        latSeconds %= 60;
        char latDirection = (m_latitude >= 0) ? 'N' : 'S';
        text = Integer.toString(latDegrees) + "\u00B0 " + Integer.toString(latMinutes) + "' " + 
                Integer.toString(latSeconds) + "\" " + latDirection;
        return text;
    }
    String getLongStr() {
        String text = "";
        int longSeconds = (int)(Math.abs(m_longitude * 3600));
        int longDegrees = longSeconds / 3600;
        longSeconds = longSeconds % 3600;
        int longMinutes = longSeconds / 60;
        longSeconds %= 60;
        char longDirection = (m_longitude >= 0) ? 'E' : 'W';
        text = Integer.toString(longDegrees) + "\u00B0 " + Integer.toString(longMinutes) + "' " + 
                Integer.toString(longSeconds) + "\" " + longDirection;
        return text;
    }
    
    //private data members
    private int m_id;
    private double m_latitude;
    private double m_longitude;
    private Customer m_left;    //the pointer to the left child in the BST
    private Customer m_right;   //the pointer to the right child in the BST
    private int m_height;        //the height of node in the BST
    

    } // end of class Customer } //end of class WirelessPower

    Im running into a problem with this code when running these test

    import static org.junit.jupiter.api.Assertions.*;

    import org.junit.jupiter.api.AfterEach; import org.junit.jupiter.api.BeforeEach; import org.junit.jupiter.api.Test;

    class WirelessPowerTestAVL { WirelessPower s1,s2,s3; WirelessPower.Customer d0,d1,d2,d3,d4,d5,d6,d7,d8,d9;

    @BeforeEach
    void setUp() throws Exception {
    	s2 = new WirelessPower(TREETYPE.BST);
    	s3 = new WirelessPower(TREETYPE.SPLAY);
    	s1 = new WirelessPower(TREETYPE.AVL);
    	d0 = s1.new Customer(10000); // min id
    	d1 = s1.new Customer(53002,51.5078,-0.0878);//London Bridge (North & West)
    	d2 = s1.new Customer(20201, 39.2554, -76.7107); //Catonsville campus (North & West)
    	d3 = s1.new Customer(60496, 48.8584, 2.2945); //Eiffel Tower (North & East)
    	d4 = s1.new Customer(19289,43.6150,-116.2023);//Boise, ID (North & West)
    	d5 = s1.new Customer(27904, 55.7558, 37.6173);//Catherine Palace Moscow Russia (North & East)
    	d6 = s1.new Customer(93209, -33.8568, 151.2153);//Sydney Opera House (South & East)
    	d7 = s1.new Customer(19224, 40.4319,116.5704);//Great Wall of China (North & East)
    	d8 = s1.new Customer(19372, 27.1751, 78.0421);//Taj Mahal (North & East)
    	d9 = s1.new Customer(26241, -13.1632,-72.5453);//Machu Picchu (South & West)
    }
    
    @AfterEach
    void tearDown() throws Exception {
    	s3 = s2 = s1 = null;
    }
    
    @Test
    void testWirelessPowerConstructor() {
    	assertNull(s1.getRoot());
    	assertTrue(s2.getRoot() == null);
    	assertFalse(s3.getRoot() != null);
    	assertEquals(TREETYPE.AVL,s1.getType());
    	assertEquals(TREETYPE.BST,s2.getType());
    	assertEquals(TREETYPE.SPLAY,s3.getType());
    }
    
    @Test
    void testInsertEasyAVL() {
    	s1.insert(d1);
    	//this Customer is the root of the tree
    	assertEquals(53002,s1.getRoot().getID());
    	assertEquals(51.5078, s1.getRoot().getLatitude());
    	assertEquals(-0.0878, s1.getRoot().getLongitude());
    
    	//insert to the left of the root
    	s1.insert(d2);
    	assertEquals(20201,s1.getRoot().getLeft().getID());
    	assertEquals(39.2554, s1.getRoot().getLeft().getLatitude());
    	assertEquals(-76.7107, s1.getRoot().getLeft().getLongitude());
    
    	//insert to the right of the root
    	s1.insert(d3);
    	assertEquals(60496,s1.getRoot().getRight().getID());
    	assertEquals(48.8584, s1.getRoot().getRight().getLatitude());
    	assertEquals(2.2945, s1.getRoot().getRight().getLongitude());
    	//check the heights
    	assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree());
    }
    
    @Test
    void testInsertAVLNoRebalance() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	s1.insert(d7);//left of left of left of root
    	s1.insert(d8); //right of left of left of root
    	s1.insert(d9); //left of right of left of root
    	assertEquals(53002,s1.getRoot().getID());
    	assertEquals(60496,s1.getRoot().getRight().getID());
    	assertEquals(20201,s1.getRoot().getLeft().getID());
    	assertEquals(19289,s1.getRoot().getLeft().getLeft().getID());
    	assertEquals(27904,s1.getRoot().getLeft().getRight().getID());
    	assertEquals(93209,s1.getRoot().getRight().getRight().getID());
    	assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID());
    	assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID());
    	assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID());
    	assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());		
    }
    
    @Test
    void testInsertRebalanceEasyAVL() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d4); //left of left of root
    	//requires a rebalance
    	assertEquals(20201,s1.getRoot().getID());
    	assertEquals(53002,s1.getRoot().getRight().getID());
    	assertEquals(19289,s1.getRoot().getLeft().getID());
    	//check the heights
    	assertEquals("((19289:0)20201:1(53002:0))",s1.dumpTree());
    
    }
    
    @Test
    void testInsertDeepCopyOfParameterAVL() {
    	s1.insert(d1);
    	s1.insert(d2);
    	assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878",s1.listCustomers());
    	d1.setID(93300);
    	s1.insert(d1);
    	assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n93300:51.5078:-0.0878",s1.listCustomers());
    	//check the heights
    	assertEquals("((20201:0)53002:1(93300:0))",s1.dumpTree());
    
    }
    
    @Test
    void testInsertRebalanceAVL() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root		
    	s1.insert(d7);//left of left of left of root
    	
    	assertEquals(53002,s1.getRoot().getID());
    	assertEquals(60496,s1.getRoot().getRight().getID());
    	assertEquals(19289,s1.getRoot().getLeft().getID());
    	assertEquals(19224,s1.getRoot().getLeft().getLeft().getID());
    	assertEquals(20201,s1.getRoot().getLeft().getRight().getID());
    	System.out.println(s1.dumpTree());
    }
    
    @Test
    void testInsertDuplicateAVL() {
    	s1.insert(d1);
    	s1.insert(d2);
    	s1.insert(d3);
    	assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945",s1.listCustomers());
    	s1.insert(s1.new Customer(60496));
    	//No duplicate IDs
    	assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945",s1.listCustomers());
    }
    
    @Test
    void testInsertErrorAVL() {
    	WirelessPower.Customer d10 = s1.new Customer(500,48.8584,2.2945);
    	s1.insert(d10);
    	//ID is less than minimum
    	assertNull(s1.getRoot());
    }
    
    @Test
    void testClearAVL() {
    	//create a tree
    	s1.insert(d1);
    	s1.insert(d2);
    	s1.insert(d3);
    	s1.clear();
    	assertNull(s1.getRoot());
    }
    
    
    @Test
    void testRemoveEasyAVL() {
    	//create a simple tree
    	s1.insert(d1);
    	s1.insert(d2);
    	s1.insert(d3);
    	//remove the node to the right of the root
    	s1.remove(60496); //this is d3
    	assertNull(s1.getRoot().getRight());
    	//check the heights
    	assertEquals("((20201:0)53002:1)",s1.dumpTree());
    
    }
    
    @Test
    void testRemoveNoRebalanceAVL() {
    	//create a simple tree
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	//insert d6 (goes to right of right of root)
    	s1.insert(d6);
    	
    	//delete 60496 which is right of root with a right child
    	s1.remove(60496);
    	//93209 (d6) should now be right of root
    	assertEquals(93209, s1.getRoot().getRight().getID());
    }
    
    @Test
    void testRemoveRebalanceEasyAVL() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	s1.insert(d7);//left of left of left of root
    	
    	//delete 27904 which is right of left of root and requires a rebalance
    	s1.remove(27904);
    	assertEquals(53002,s1.getRoot().getID());
    	assertEquals(60496,s1.getRoot().getRight().getID());
    	assertEquals(19289,s1.getRoot().getLeft().getID());
    	assertEquals(19224,s1.getRoot().getLeft().getLeft().getID());
    	assertEquals(20201,s1.getRoot().getLeft().getRight().getID());
    	//check the heights
    	assertEquals("(((19224:0)19289:1(20201:0))53002:2(60496:1(93209:0)))",s1.dumpTree());
    }
    
    @Test
    void testHeightChangesAVL() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	assertEquals(1,s1.getRoot().getHeight());
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	assertEquals(2,s1.getRoot().getHeight());
    	s1.insert(d7);//left of left of left of root
    	s1.insert(d8); //right of left of left of root
    	s1.insert(d9); //left of right of left of root
    	assertEquals(3,s1.getRoot().getHeight());
    	//check the heights
    	assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
    
    }
    
    @Test
    void testRemoveNoRebalAVL() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	s1.insert(d7);//left of left of left of root
    	s1.insert(d8); //right of left of left of root
    	s1.insert(d9); //left of right of left of root
    	String result = s1.listCustomers();
    	assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n19372:27.1751:78.0421\n20201:39.2554:-76.7107\n26241:-13.1632:-72.5453\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
    	s1.remove(19372);
    	result = s1.listCustomers();
    	assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n26241:-13.1632:-72.5453\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
    	//check the heights
    	assertEquals("((((19224:0)19289:1)20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
    
    }
    
    @Test
    void testRemoveReBalEasyAVL() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	s1.insert(d7);//left of left of left of root
    	
    	System.out.println(s1.dumpTree());
    	String result = s1.listCustomers();
    	assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
    	s1.remove(27904);
    	result = s1.listCustomers();
    	assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
    	assertEquals("(((19224:0)19289:1(20201:0))53002:2(60496:1(93209:0)))",s1.dumpTree());
    }
    	
    
    @Test
    void testCopyConstructorEasyAVL() {
    	s1.insert(d1);
    	s1.insert(d2);
    	s1.insert(d3);
    	assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree());
    	WirelessPower s4 = new WirelessPower(s1);
    
    	// this Customer is the root of the tree
    	assertEquals(53002, s4.getRoot().getID());
    	assertEquals(51.5078, s4.getRoot().getLatitude());
    	assertEquals(-0.0878, s4.getRoot().getLongitude());
    
    	// left of the root
    	assertEquals(20201, s4.getRoot().getLeft().getID());
    	assertEquals(39.2554, s4.getRoot().getLeft().getLatitude());
    	assertEquals(-76.7107, s4.getRoot().getLeft().getLongitude());
    
    	// right of the root
    	assertEquals(60496, s4.getRoot().getRight().getID());
    	assertEquals(48.8584, s4.getRoot().getRight().getLatitude());
    	assertEquals(2.2945, s4.getRoot().getRight().getLongitude());
    	assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree());
    	assertEquals("((20201:0)53002:1(60496:0))", s4.dumpTree());
    }
    
    @Test
    void testCopyConstructorAVL() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	s1.insert(d7);//left of left of left of root
    	s1.insert(d8); //right of left of left of root
    	s1.insert(d9); //left of right of left of root
    	WirelessPower s4 = new WirelessPower(s1);
    	assertEquals(53002,s4.getRoot().getID());
    	assertEquals(60496,s4.getRoot().getRight().getID());
    	assertEquals(20201,s4.getRoot().getLeft().getID());
    	assertEquals(19289,s4.getRoot().getLeft().getLeft().getID());
    	assertEquals(27904,s4.getRoot().getLeft().getRight().getID());
    	assertEquals(93209,s4.getRoot().getRight().getRight().getID());
    	assertEquals(19224,s4.getRoot().getLeft().getLeft().getLeft().getID());
    	assertEquals(19372,s4.getRoot().getLeft().getLeft().getRight().getID());
    	assertEquals(26241,s4.getRoot().getLeft().getRight().getLeft().getID());	
    }
    
    @Test
    void testSetTypeAVLtoBST() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	s1.insert(d7);//left of left of left of root
    	s1.insert(d8); //right of left of left of root
    	s1.insert(d9); //left of right of left of root
    	assertEquals(53002,s1.getRoot().getID());
    	assertEquals(60496,s1.getRoot().getRight().getID());
    	assertEquals(20201,s1.getRoot().getLeft().getID());
    	assertEquals(19289,s1.getRoot().getLeft().getLeft().getID());
    	assertEquals(27904,s1.getRoot().getLeft().getRight().getID());
    	assertEquals(93209,s1.getRoot().getRight().getRight().getID());
    	assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID());
    	assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID());
    	assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID());
    	assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
    	//convert AVL tree to BST tree
    	s1.setType(TREETYPE.BST);
    	//no change
    	assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
    	assertEquals(TREETYPE.BST,s1.getType());
    	
    }
    
    @Test
    void testSetTypeAVLtoSplay() {
    	s1.insert(d1); //root
    	s1.insert(d2); //left of root
    	s1.insert(d3); //right of root
    	s1.insert(d4); //left of left of root
    	s1.insert(d5); //right of left of root
    	s1.insert(d6); //right of right of root
    	s1.insert(d7);//left of left of left of root
    	s1.insert(d8); //right of left of left of root
    	s1.insert(d9); //left of right of left of root
    	assertEquals(53002,s1.getRoot().getID());
    	assertEquals(60496,s1.getRoot().getRight().getID());
    	assertEquals(20201,s1.getRoot().getLeft().getID());
    	assertEquals(19289,s1.getRoot().getLeft().getLeft().getID());
    	assertEquals(27904,s1.getRoot().getLeft().getRight().getID());
    	assertEquals(93209,s1.getRoot().getRight().getRight().getID());
    	assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID());
    	assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID());
    	assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID());
    	assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
    	//convert AVL tree to Splay tree
    	s1.setType(TREETYPE.SPLAY);
    	//no change
    	assertEquals(TREETYPE.SPLAY,s1.getType());
    	assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
    	
    }
    

    }

    I'm getting stack overflow on some of them for example void testInsertAVLNoRebalance() { is one of them how would i go about fixing this i still want to use arrayList for my implementation of everything since it seems to be the most efficent no? I also cannot modify anything in the test cases or inside of the custoemr class and I cant import any other java utils

  2. Assistant

    The stack overflow you're experiencing is likely due to the balance method being called twice during AVL insertions. Here's a detailed explanation and the steps to fix the issue:

    Root Cause: Double Balancing

    1. Current Implementation:

      • In the insert method, for the AVL case, you call both insertAVL and balance:
        case AVL:
            m_root = insertAVL(m_root, aCustomer, tempNodes);
            balance(tempNodes);
            break;
        
      • Inside the insertAVL method, you also call balance:
        private Customer insertAVL(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) {
            // ... insertion logic ...
            return balance(tempNodes);
        }
        
    2. Issue:

      • When insertAVL is called, it already performs balancing on the tree.
      • After insertAVL returns, the insert method calls balance again on the same nodes.
      • This redundant call can lead to an infinite loop of balancing, especially if the tree remains unbalanced after the first balancing attempt, causing a stack overflow.

    Solution: Remove Redundant Balancing

    To fix the stack overflow, you need to ensure that balance is called only once during AVL insertions. Here's how you can do it:

    1. Modify the insert Method:

      • Remove the balance(tempNodes); call from the AVL case since insertAVL already handles balancing.
      • Ensure that balancing is not called for the BST case, as standard BSTs do not require balancing.
      public void insert(Customer aCustomer) {
          // ArrayList to keep track of nodes along the insertion path
          ArrayList<Customer> tempNodes = new ArrayList<>();
      
          // Check for valid range of ID
          if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) {
              return;
          }
      
          // Check if tree is empty 
          if (isEmpty()) {
              // Create a new customer node and set it as the root since tree is empty
              m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
              return;
          }
      
          // Determine the type of tree and perform the appropriate insertion
          switch (getType()) {
              case BST:
                  m_root = insertBST(m_root, aCustomer, tempNodes);
                  break;
              case AVL:
                  m_root = insertAVL(m_root, aCustomer, tempNodes);
                  break;
              case SPLAY:
                  m_root = splay(m_root, aCustomer);
                  break;
          }
      }
      
    2. Ensure insertBST Does Not Balance:

      • The insertBST method should remain unchanged, as standard BSTs do not perform balancing.
      private Customer insertBST(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) {
          // Base case: If the current node is null, insert the new customer here
          if (node == null) {
              return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
          }
      
          // Check for duplicate ID
          if (node.getID() == aCustomer.getID()) {
              return node; // Do not insert duplicates
          }
      
          // Add the current node to the path list
          tempNodes.add(node);
      
          // Recur down the tree
          if (aCustomer.getID() < node.getID()) {
              node.setLeft(insertBST(node.getLeft(), aCustomer, tempNodes));
          } else {
              node.setRight(insertBST(node.getRight(), aCustomer, tempNodes));
          }
      
          // Update the height of the current node
          updateHeight(node);
      
          return node;
      }
      
    3. Verify insertAVL Handles Balancing Correctly:

      • Ensure that insertAVL correctly inserts the node and balances the tree using the passed tempNodes.
      private Customer insertAVL(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) {
          // If the tree is empty, create a new node and return it
          if (node == null) {
              return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
          }
      
          // If the key already exists, return the node (no duplicates)
          if (node.getID() == aCustomer.getID()) {
              return node; // Early return to prevent infinite recursion on duplicates
          }
      
          // Add the current node to the list
          tempNodes.add(node);
      
          // Traverse the tree and insert the new customer
          if (aCustomer.getID() < node.getID()) {
              node.setLeft(insertAVL(node.getLeft(), aCustomer, tempNodes));
          } else {
              node.setRight(insertAVL(node.getRight(), aCustomer, tempNodes));
          }
      
          // Update the height of the ancestor node
          updateHeight(node);
      
          // Balance the node and return the potentially new root of this subtree
          return balance(tempNodes);
      }
      

    Additional Recommendations:

    1. Ensure Proper Balancing Logic:

      • Double-check your balance method to ensure it correctly identifies imbalances and performs the necessary rotations without introducing cycles or infinite loops.
    2. Test Incrementally:

      • After making the changes, run your tests incrementally to ensure that each part works as expected before moving on to more complex insertions.
    3. Debugging:

      • If you continue to encounter issues, consider adding debug statements inside your insertAVL and balance methods to trace the execution flow and identify where the recursion may be going wrong.

    Conclusion

    By ensuring that the balance method is called only once during AVL insertions, you should prevent the stack overflow caused by infinite recursion. This change respects the distinction between BST and AVL insertion behaviors and aligns the implementation with your test cases.

    Updated insert Method:

    public void insert(Customer aCustomer) {
        // ArrayList to keep track of nodes along the insertion path
        ArrayList<Customer> tempNodes = new ArrayList<>();
    
        // Check for valid range of ID
        if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) {
            return;
        }
    
        // Check if tree is empty 
        if (isEmpty()) {
            // Create a new customer node and set it as the root since tree is empty
            m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
            return;
        }
    
        // Determine the type of tree and perform the appropriate insertion
        switch (getType()) {
            case BST:
                m_root = insertBST(m_root, aCustomer, tempNodes);
                break;
            case AVL:
                m_root = insertAVL(m_root, aCustomer, tempNodes);
                break;
            case SPLAY:
                m_root = splay(m_root, aCustomer);
                break;
        }
    }
    

    By removing the redundant balance(tempNodes); call in the AVL case, the tree should now handle insertions correctly without causing a stack overflow.