search trees we implemented hash table version of the map adt that improved the search times but its efficiency depends on the type of keys stored in the mapsince the choice of hash function can greatly impact the search operation throughout the we explore several different search treeseach of which we will use to implement new versions of the map adt to help avoid confusion between the various implementationswe use different class name for each implementation the binary search tree binary search tree (bstis binary tree in which each node contains search key within its payload and the tree is structured such that for each interior node all keys less than the key in node are stored in the left subtree of all keys greater than the key in node are stored in the right subtree of consider the binary search tree in figure which contains integer search keys the root node contains key value and all keys in the root' left subtree are less than and all of the keys in the right subtree are greater than if you examine every node in the keysyou will notice the same key relationship applies to every node in the tree given the relationship between the nodesan inorder traversal will visit the nodes in increasing search key order for the example binary search treethe order would be figure binary search tree storing integer search keys our definition of the binary search tree precludes the storage of duplicate keys in the treewhich makes the implementation of the various operations much easier it' also appropriate for some applicationsbut the restriction can be changed to allow duplicate keysif needed in additionfor illustration purposeswe only show the key within each node of our search trees you should assume the corresponding data value is also stored in the nodes partial implementation of the binary search tree version of the map adt is shown in listing the remaining code will be added as each operation is