2023年11月25日

Java代写 | COMPUTER SCIENCE 21A PROGRAMMING ASSIGNMENT 2

本次北美CS代写主要是使用Java完成数据结构算法的AVL树

COMPUTER SCIENCE 21A (SPRING TERM, 2021) DATA STRUCTURES

PROGRAMMING ASSIGNMENT 2

Chess Leaderboards with AVL trees

Background:

You have been hired by an international chess society to update their scoreboard system. The chess society is a membership organization, the members play chess against one another and the society keeps track of the outcomes. Each member has an Elo rating (a score based on their prior performance in chess matches), and the members are ranked based on their Elo ratings. Whenever there is a chess match between two society members, the winner’s score increases and the loser’s score decreases, and the rankings may also change. The society members are very competitive, so they frequently check their own ranking and Elo rating and the rankings and ratings of their opponents.

Your predecessor, who dropped out of data structures class after the first assignment, wrote the old scoreboard code using a linked list with insertion sort. This wasn’t a problem when the society was small, but the society is growing, and members are complaining that it takes too long to look up the rankings and ratings of individual players. Of course, we know that this is because searching for a particular member in a linked list takes O(n) time. You have been instructed by the chess society that these lookups need to be worst case O(log(n)) time or you will be fired. To accomplish this task, you will need to build a self-balancing AVL tree, augmented to allow fast computation of player ranking.

Basic Idea:

Each player has a name, ID number, and Elo score. You need to allow players to look up their Elo score or their rank in the league using only their player ID number. To do this, you will need to make two trees to store players – one tree where the players are sorted based on ID, and another where they are sorted based on Elo. In order to find the ranking of the player with ID number 100, you would first search for player 100 in the ID tree. Inside the node for player 100 is the Elo score for player 100. Use this score to query the Elo tree to find the actual ranking of player 100 based on Elo score.

Computing the Rank:

The rank of a player is one more than the number of players with a higher score (the best player is ranked 1). To compute the rank, each node will have to store the number of nodes in the right (bigger) subtree. Using this property, the rank can be computed recursively. The rank of the root is one more than the number of nodes in the right subtree. If the Elo score is greater than the root, the rank is equal to the rank in the right subtree, computed recursively. If the Elo score is less than the root, the rank is the rank in the left subtree (computed recursively) plus the number of nodes in the right subtree, plus one for the root. You will need to add a line of code to the end of the left and right rotation procedures to maintain the count of nodes in the right subtree.

Writing Your AVL tree:

As mentioned before, in order to find the rank of a player using only their player ID, you will need two trees. You should not write two different tree node classes. Instead, in order to reuse code, you should write one tree node class that can do everything you need for both trees. Each node should store the value that it is sorted by in a separate field apart from where it stores its Player object. Your insert method should take as arguments a Player object to insert and a double value to sort the player by. Then, if you want to insert a new Player p with name “Bill” with id 0 and Elo 100.0, you can do eloTree.insert(p,p.getElo()) and idTree.insert(p,p.getID()).

Requirements:

Your job is to fill in the methods ofAVLPlayerNode.java, your AVL tree node class. Y ou have been provided with the code for the Player class, which is described below. You have also been provided with the interactive part of the code, including the main method, in ScoreKeeper.java. We have commented out the parts of that file which use the AVLPlayerNode methods you are responsible for writing. As you fill in the methods for AVLPlayerNode, you can uncomment the relevant sections of ScoreKeeper.java, but you should not add any new code to this file.

Your tree should do self-balancing AVL insertions. Your tree must also allow for deletions, but we have made self-balancing deletions extra credit. For full credit, you need only implement a delete method which returns the tree in a valid state. Be warned that these unbalanced deletions can break the AVL property of your tree, so once you delete from a tree there is no guarantee that insertions will work properly. If you are not doing the extra credit, you should not expect insertions to work properly after deletions when testing your code.

Y our tree will need a method getPlayer(double value) which returns the Player object stored in the node with this.value=value.

As mentioned before, your tree node class will also need a getRank(double value) method that returns the rank of the player at the node with this.value=value.

Your main method will need to be able to print the entire scoreboard in order from highest Elo to lowest, so your tree node class should have a method that returns the full board as a String.

Lastly, your tree node class should have a method that returns a String of the tree of names, using parentheses to separate subtrees. For example, for the tree below, the printout would be: (((alice)bill((dave)fred(jane(joe))))judy(mary(tom)))