time size,isempty ( findinsertremove (hfindall ( snote that the running time of search and update operations in binary search tree varies dramatically depending on the tree' height we can nevertheless take comfort thaton averagea binary search tree with keys generated from random series of insertions and removals of keys has expected height (lognsuch statement requires careful mathematical language to precisely define what we mean by random series of insertions and removalsand sophisticated probability theory to provehenceits justification is beyond the scope of this book neverthelesskeep in mind the poor worst-case performance and take care in using standard binary search trees in applications where updates are not random there areafter allapplications where it is essential to have dictionary with fast worst-case search and update times the data structures presented in the next sections address this need java implementation in code fragments through we describe binary search tree classbinarysearchtreewhich stores objects of class bstentry (implementing the entry interfaceat its nodes class binarysearchtree extends class linked binarytree from code fragments through thus taking advantage of code reuse this class makes use of several auxiliary methods to do much of the heavy lifting the auxiliary method treesearchbased on the treesearch algorithm (code fragment )is invoked by the findfindalland insert methods we use recursive addall method as the main engine for the findall(kmethodin that it performs an inorder traversal of all the entries with keys equal to (although not using the fast algorithmsince it performs failed search for every entry it findswe use two additional update methodsinsertatexternalwhich inserts new entry at an external nodeand removeexternalwhich removes an external node and its parent