This paper is about randomized binary search trees. A book warehouse company supplies books to bookstores in different towns and villages of the country. For better supplying and support of the stores the company has big warehouses with books that it has in some key locations in the country. The company periodically decides if it has to make new warehouses (on new towns or new warehouse in a town it already has another) and if it is good to shut down a warehouse. So it is necessary to have a data structure that can hold the info about books that are in each warehouse. The company has decided to create the data structure using randomized binary search trees.

Purpose of this paper is to create this data structure using the methods explained below. See image.

Each warehouse is one node of the tree, a treenode object. Each node as a unique id and a name of the city that it is. So the class has to at least contain the following fields. See image.

The booklist field is ordered linked list that has bookinfo objects. The Bookinfo class represents the book?s info. It has the ISBN and the number of the copies in the specific warehouse. The isbn in this case is from 0 to 9999. The booklist has one object for each book available in the warehouse (books with no copies are deleted from the list). In the list there must not be books with the same isbn. The list is ordered in ascending order by the isbn number.

  • void insertWarehouse(int nodeid, String name) - This method inserts a new warehouse (new treenode) with code nodeid and city name name. If there is a warehouse with the same id an error message sould be returned. The method should be working with possibility 1/N+1 insert at root with rotations or else insert as a normal leaf of the tree. Tha fields N and height should also be updated.
  • void insertBookAtWarehouse(int nodeid, int isbn, int copies) - This method removes the warehouse with code nodeid. N and heighted should be updated.
  • void removeBook(int nodeid, int isbn) - This method removes a book copy with this.isbn=isbn from warehouse with code=nodeid. If the warehouse doesn?t exist or has no copies of this book an error message should be displayed else you reduce the book number by 1 and if the book number is now 0 you remove the book from the list.
  • void searchByWarehouse(int nodeid) - With this method you search the warehouse by the nodeid and you print all the books available in the given warehouse.
  • void searchByCity(String cityname) - This method finds the warehouses available in the given city and prints the available books as long with the number of copies. If a book is in multiple warehouses you print once the isbn and the number of copies all added. For example Book 1332, copies:13. In this case you can't search by id so you have to run through the entire tree. You can use inorder, postorder or preorder.
  • void searchBookInWarehouse(int nodeid, int isbn) - With this method we search if the book with this isbn is in the warehouse with this id. If the book exists we print the number of the copies. If not we ask if you want to search the other warehouses. If the client accepts the method searches the entire tree for this book and prints the warehouse that is founded in and the number of the copies (this is done by searching again tree) tip you can find first the warehouses by running the entire tree and then search each one of them for the copies.
  • void printTree(PrintStream stream) - This method is usefull for debugging. It has to do run the entire tree firtst and then print each node and the contents of the booklist. You can add an additional methods you want.

You need to create a simple app of managing the warehouse. All the methods should appear. The program must interact with the user so he can add delete remove warehouses books etc.

Sample outputs

We have 3 warehouses. One in Athens with code 3 one in Thessaloniki with code 13 and one in Patra with code 33. In warehouse 3 we have books with isbn 134 and 256 with 2 copies each. In warehouse 13 we have 1 copy of the book with isbn 134 and 3 copies of the book 349. And in warehouse 33 we have 1 copy of the books with isbn 17,31,349.

No ready java methods should be used(vector,arraylist etc.) Don't forget to update the fields N and height. The height of a node wich has left and right child equal with null is 1. Any other node h has height 1+max {h.left.height,h.right.height}.

Academic Honesty!
It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.