from the point of view of the search algorithms we are going to consider in what followswe shall concentrate on the search keysbut should always bear in mind that there is usually more substantial data entry associated with it notice the use of the word "abstracthere what we mean is that we abstract or remove any details that are irrelevant from the point of view of the algorithms for examplea dictionary usually comes in the form of bookwhich is sequence of pages but for usthe distribution of dictionary entries into pages is an accidental feature of the dictionary all that matters for us is that the dictionary is sequence of entries so "abstractionmeans "getting rid of irrelevant detailsfor our purposesonly the search key is importantso we will ignore the fact that the entries of the collection will typically be more complex objects (as in the example of dictionary or phone booknote that we should always employ the data structure to hold the items which performs best for the typical application there is no easy answer as to what the best choice is the particular circumstances have to be inspectedand decision has to be made based on that howeverfor many applicationsthe kind of binary trees we studied in the last are particularly useful here binary search trees the solution to our search problem is to store the collection of data to be searched using binary tree in such way that searching for particular item takes minimal effort the underlying idea is simpleat each tree nodewe want the value of that node to either tell us that we have found the required itemor tell us which of its two subtrees we should search for it in for the momentwe shall assume that all the items in the data collection are distinctwith different search keysso each possible node value occurs at most oncebut we shall see later that it is easy to relax this assumption hence we definedefinition binary search tree is binary tree that is either empty or satisfies the following conditionsall values occurring in the left subtree are smaller than that of the root all values occurring in the right subtree are larger than that of the root the left and right subtrees are themselves binary search trees so this is just particular type of binary treewith node values that are the search keys this means we can inherit many of the operators and algorithms we defined for general binary trees in particularthe primitive operators maketree(vlr)root( )left( )right(tand isempty(tare the same we just have to maintain the additional node value ordering building binary search trees when building binary search treeone naturally starts with the root and then adds further new nodes as needed soto insert new value vthe following cases ariseif the given tree is emptythen simply assign the new value to the rootand leave the left and right subtrees empty