Data Structures

insertSymbioteHost(SymbioteHost symbiote)

As Venom, we need an easy way to store and traverse the list of potential target hosts. Utilize the Binary Search Tree (BST) data structure discussed during the BST lectures to do so.

• The BST is a Symbol Table that stores SymbioteHost nodes.
  • This is a bit different from the code from lecture that had distinctive <key,value> pairs.
• The key is a SymbioteHost’s name. Use the name as the key to compare and traverse through the BST.
• The value is also stored in SymbioteHosts in the form of remaining host’s characteristics.

This method takes a SymbioteHost node a parameter, and adds the node to the BST rooted at root. Remember that the root is a reference to the root node of the BST.

• Follow the BST insertion algorithm as discussed in class to insert a SymbioteHost into the BST.

• The BST has unique SymbioteHosts’ key, meaning no two SymbioteHosts can have the same name. If you encounter the same key again, UPDATE the existing node with its new stability, compatibility and antibodies values.

• SymbioteHosts with names greater than a node’s name are stored to the right of the node, otherwise they are stored to the left. Compare based on names Use the compareTo() method to determine where to place SymbioteHosts lexicographically (ie. comparing strings).

Note that although only names are used as keys, each node represents an entire SymbioteHost.

How to test: 

• You can complete the Driver class to finish the driver. We provide simple driver code in the main() method, you must fill in each case in the switch statement. The class is not fully implemented — use the comments in the code to make the code work.
• You can also use JUnit test cases. We provide a sample test method for insertSymbioteHost. A smaller test input file (testInput.in) is provided for you to work with fewer nodes than the input file.

This method builds the BST from the input filename parameter.

1. Call createSymbioteHosts using the filename given as parameter. createSymbioteHosts will return an array of SymbioteHost that were read from the file.
2. Then, call insertSymbioteHost for every element in the array returned by createSymbioteHosts to insert each into the BST.

IMPLEMENT the insertSymbioteHost method and update the method’s code to make this method work. Once the insertSymbioteHost and buildTree methods are implemented, submit Venom.java with these two methods implemented under Early Submission for extra credit.

How to test:

• You have two options for writing tests. Filling in the Driver class, or writing JUnit tests. The Driver class may be easier, but less helpful.
  • NOTE: In the driver, call StdIn.resetFile(); AFTER calling printTree() when testing this method.
• Use BST ordering to conclude whether or not your code works as intended.

Here is the expected tree structure when using hosts0.in. Note that names are emphasized with bolds.

If you use the printTree() method, the structure will look like this:

• NOTE: In the driver, call StdIn.resetFile(); AFTER calling printTree() when testing this method.

+--- Host{name='Eddie Brock', symbioteCompatibility=22, mentalStability=24, hasAntibodies=false, suitability=96}
        |-L- Host{name='Anne Weying', symbioteCompatibility=66, mentalStability=1, hasAntibodies=true, suitability=117}
                |-L- null
                |-R- Host{name='Dylan Brock', symbioteCompatibility=78, mentalStability=9, hasAntibodies=false, suitability=137}
                        |-L- Host{name='Captain America', symbioteCompatibility=31, mentalStability=5, hasAntibodies=false, suitability=86}
                                |-L- Host{name='Bruce Banner', symbioteCompatibility=12, mentalStability=44, hasAntibodies=false, suitability=106}
                                |-R- Host{name='Clint Barton', symbioteCompatibility=78, mentalStability=9, hasAntibodies=false, suitability=137}
                        |-R- null
        |-R- Host{name='Peter Parker', symbioteCompatibility=36, mentalStability=9, hasAntibodies=false, suitability=95}
                |-L- Host{name='Flash Thompson', symbioteCompatibility=78, mentalStability=9, hasAntibodies=true, suitability=137}
                        |-L- null
                        |-R- Host{name='Mac Gargan', symbioteCompatibility=47, mentalStability=21, hasAntibodies=false, suitability=118}
                                |-L- null
                                |-R- Host{name='Natasha Romanoff', symbioteCompatibility=78, mentalStability=9, hasAntibodies=false, suitability=137}
                |-R- Host{name='Wade Winston', symbioteCompatibility=15, mentalStability=5, hasAntibodies=true, suitability=70}
                        |-L- Host{name='Tony Stark', symbioteCompatibility=29, mentalStability=11, hasAntibodies=false, suitability=90}
                                |-L- Host{name='Stephen Strange', symbioteCompatibility=66, mentalStability=10, hasAntibodies=false, suitability=126}
                                        |-L- null
                                        |-R- Host{name='Thor Odinson', symbioteCompatibility=48, mentalStability=9, hasAntibodies=true, suitability=107}
                                |-R- null
                        |-R- null