binary search trees we now look at binary search treeswhich are particular type of binary tree that provide an efficient way of storing data that allows particular items to be found as quickly as possible then we consider further elaborations of these treesnamely avl trees and -treeswhich operate more efficiently at the expense of requiring more sophisticated algorithms searching with arrays or lists as we have already seen in many computer science applications involve searching for particular item in collection of data if the data is stored as an unsorted array or listthen to find the item in questionone obviously has to check each entry in turn until the correct one is foundor the collection is exhausted on averageif there are itemsthis will take / checksand in the worst caseall items will have to be checked if the collection is largesuch as all items accessible via the internetthat will take too much time we also saw that if the items are sorted before storing in an arrayone can perform binary search which only requires log checks in the average and worst cases howeverthat involves an overhead of sorting the array in the first placeor maintaining sorted array if items are inserted or deleted over time the idea here is thatwith the help of binary treeswe can speed up the storing and search process without needing to maintain sorted array search keys if the items to be searched are labelled by comparable keysone can order them and store them in such way that they are sorted already being 'sortedmay mean different things for different keysand which key to choose is an important design decision in our examplesthe search keys willfor simplicityusually be integer numbers (such as student id numbers)but other choices occur in practice for examplethe comparable keys could be words in that casecomparability usually refers to the alphabetical order if and are wordswe write to mean that precedes in the alphabetical order if bed and sky then the relation holdsbut this is not the case if bed and abacus classic example of collection to be searched is dictionary each entry of the dictionary is pair consisting of word and definition the definition is sequence of words and punctuation symbols the search keyin this exampleis the word (to which definition is attached in the dictionary entrythusabstractlya dictionary is sequence of