why use binary treeswhy might you want to use treeusuallybecause it combines the advantages of two other structuresan ordered array and linked list you can search tree quicklyas you can an ordered arrayand you can also insert and delete items quicklyas you can with linked list let' explore these topics bit before delving into the details of trees slow insertion in an ordered array imagine an array in which all the elements are arranged in orderthat isan ordered arraysuch as we saw in "simple sorting as we learnedit' quick to search such an array for particular valueusing binary search you check in the center of the arrayif the object you're looking for is greater than what you find thereyou narrow your search to the top half of the arrayif it' lessyou narrow your search to the bottom half applying this process repeatedly finds the object in (logntime it' also quick to iterate through an ordered arrayvisiting each object in sorted order on the other handif you want to insert new object into an ordered arrayyou first need to find where the object will goand then move all the objects with greater keys up one space in the array to make room for it these multiple moves are time consumingrequiringon the averagemoving half the items ( / movesdeletion involves the same multimove operationand is thus equally slow if you're going to be doing lot of insertions and deletionsan ordered array is bad choice slow searching in linked list on the other handas we saw in "advanced sorting,insertions and deletions are quick to perform on linked list they are accomplished simply by changing few references these operations require ( time (the fastest big- timeunfortunatelyhoweverfinding specified element in linked list is not so easy you must start at the beginning of the list and visit each element until you find the one you're looking for thus you will need to visit an average of / objectscomparing each one' key with the desired value this is slowrequiring (ntime (notice that times considered fast for sort are slow for data structure operations you might think you could speed things up by using an ordered linked listin which the elements were arranged in orderbut this doesn' help you still must start at the beginning and visit the elements in orderbecause there' no way to access given element without following the chain of references to it (of coursein an ordered list it' much quicker to visit the nodes in order than it is in non-ordered listbut that doesn' help to find an arbitrary object trees to the rescue it would be nice if there were data structure with the quick insertion and deletion of linked listand also the quick searching of an ordered array trees provide both these characteristicsand are also one of the most interesting data structures what is treewe'll be mostly interested in particular kind of tree called binary treebut let' start by discussing trees in general before moving on to the specifics of binary trees