trees for large amounts of inputthe linear access time of linked lists is prohibitive in this we look at simple data structure for which the average running time of most operations is (log nwe also sketch conceptually simple modification to this data structure that guarantees the above time bound in the worst case and discuss second modification that essentially gives an (log nrunning time per operation for long sequence of instructions the data structure that we are referring to is known as binary search tree the binary search tree is the basis for the implementation of two library collections classesset and mapwhich are used in many applications trees in general are very useful abstractions in computer scienceso we will discuss their use in othermore general applications in this we will see how trees are used to implement the file system of several popular operating systems see how trees can be used to evaluate arithmetic expressions show how to use trees to support searching operations in (log naverage time and how to refine these ideas to obtain (log nworst-case bounds we will also see how to implement these operations when the data are stored on disk discuss and use the set and map classes preliminaries tree can be defined in several ways one natural way to define tree is recursively tree is collection of nodes the collection can be emptyotherwisea tree consists of distinguished nodercalled the rootand zero or more nonempty (sub)trees tk each of whose roots are connected by directed edge from the root of each subtree is said to be child of rand is the parent of each subtree root figure shows typical tree using the recursive definition from the recursive definitionwe find that tree is collection of nodesone of which is the rootand edges that there are edges follows from the fact that each edge connects some node to its parentand every node except the root has one parent (see fig