In this homework assignment, you will implement an Account ADT using a binary search tree (BST) data structure. A BST permits a more efficient lookup mechanism (comparing to a linked list) so there is an efficiency test to ensure your code can handle a quarter of a million entries. 1 The Binary Search Tree Data Structure Please read section 9.5 in the textbook for a description of the binary search tree data structure. Alternatively, there are many webpages/lecture notes on BST, the wiki page maybe a good starting point (https://en.wikipedia.org/wiki/Binaryjsearch-tree). In the textbook (as well as some online sources), a separate BTNodce class is used; we will not do that. Use a nested node class as before. Linked lists and arrays support insertion, removal or finding an entry in time proportional to the number of entries in the container. Trees, on the other hand, offer a significant efficiency advantage in that they generally support these operations in time proportional to the log of the number of entries (assuming the tree is kept balanced). In order to achieve the potential time efficiency of binary search trees, one needs to keep the tree roughly balanced. In CompSci 535, you will learn some of the techniques used to do this (as it happens, the tree-based containers in .Java's libraries use "red-black" trees). But in this course, we will ignore the problems of unbalanced trees. Do not make any attempt to re-balance your tree. The efficiency tests we run will make sure to construct a balanced tree. 2 Concerning the Transaction ADT Account transactions arc implemented using a public class Transaction packaged with the Account class (described below). A "transaction" consists of a date/time, an non-negative amount, and a payee. We override the equals method to define that two transactions arc the same only if they have exactly the same date/time, amount, and payee. We override the hash code computation as well; hash codes will be discussed later in the course. 2.1 How is Date/Time stored? We will store the Date/Time of a transaction using the java.time.LocalDateTimo class. This class provides the ability to compare two Date/Times which will helpful when creating our tree. You can check if one LocalDateTime is before or after another using date1. isBefore(date2) and date1. isAfter(date2). We also provide a Util class which gives the functionality to convert a date/time to a string of our preferred format, and back again. This helper class also defines the minimum and maximum dates we will allow' in an account. In this homework assignment, you will implement an Account ADT using a binary search tree (BST) data structure. A BST permits a more efficient lookup mechanism (comparing to a linked list) so there is an efficiency test to ensure your code can handle a quarter of a million entries. 1 The Binary Search Tree Data Structure Please read section 9.5 in the textbook for a description of the binary search tree data structure. Alternatively, there are many webpages/lecture notes on BST, the wiki page maybe a good starting point (https://en.wikipedia.org/wiki/Binaryjsearch-tree). In the textbook (as well as some online sources), a separate BTNodce class is used; we will not do that. Use a nested node class as before. Linked lists and arrays support insertion, removal or finding an entry in time proportional to the number of entries in the container. Trees, on the other hand, offer a significant efficiency advantage in that they generally support these operations in time proportional to the log of the number of entries (assuming the tree is kept balanced). In order to achieve the potential time efficiency of binary search trees, one needs to keep the tree roughly balanced. In CompSci 535, you will learn some of the techniques used to do this (as it happens, the tree-based containers in .Java's libraries use "red-black" trees). But in this course, we will ignore the problems of unbalanced trees. Do not make any attempt to re-balance your tree. The efficiency tests we run will make sure to construct a balanced tree. 2 Concerning the Transaction ADT Account transactions arc implemented using a public class Transaction packaged with the Account class (described below). A "transaction" consists of a date/time, an non-negative amount, and a payee. We override the equals method to define that two transactions arc the same only if they have exactly the same date/time, amount, and payee. We override the hash code computation as well; hash codes will be discussed later in the course. 2.1 How is Date/Time stored? We will store the Date/Time of a transaction using the java.time.LocalDateTimo class. This class provides the ability to compare two Date/Times which will helpful when creating our tree. You can check if one LocalDateTime is before or after another using date1. isBefore(date2) and date1. isAfter(date2). We also provide a Util class which gives the functionality to convert a date/time to a string of our preferred format, and back again. This helper class also defines the minimum and maximum dates we will allow' in an account