balanced binary search trees binary search trees binary search tree comes in handy when large number of insertdeleteand lookup operations are required by an application while at times it is necessary to traverse the items in ascending or descending order consider website like wikipedia that provides access to large set of online materials imagine the designers of the website want to keep log of all the users that have accessed the website within the last hour the website might operate as follows each visitor accesses the website with unique cookie when visitor accesses the site their cookie along with date and time is recorded in log on the site' server if they have accessed the site within the last two hours their cookie and access time may already be recorded in that casetheir last access date and time is updated every hour snapshot is generated as to who is currently accessing the site the snapshot is to be generated in ascending order of the unique cookie numbers after patron has been inactive for at least an houraccording to the snapshottheir information is deleted from the record of website activity log since the site is quite large with thousandsif not tens of thousands or morepeople accessing it every hourthe data structure to hold this information must be fast it must be fast to insertlookupand delete entries it must also be quick to take snapshot since the website will hold up all requests while the snapshot is taken if the number of users that come and go during an hour on site like wikipedia is typically higher than the number that stay around for long periods of timeif may be most efficient to rebuild the tree from the activity log rather than delete each entry after it has been inactive for at least an hour this would be true if the number of people still active on the site is much smaller than the number of inactive entries in the snapshot of the log in this caserebuilding the log after deleting inactive patrons must be fast as well binary search tree is logical choice for the organization of this log if we could guarantee (log nlookupinsertand delete along with (ntime to take snapshot howevera binary search tree has one big problem recall that as the snapshot is taken the log may be rebuilt with only the recently active users and furthermore the cookies will be accessed in ascending order while rebuilding the log consider the insert operation on binary search trees shown in sect when the binary search tree is rebuilt the items to insert into the new tree will be added in ascending order the result is an unbalanced tree binary search tree insert def __insert(root,val)if root =nonereturn binarysearchtree __node(valthis copy belongs to 'acha