binary trees 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 operation and 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 "linked lists,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 thusyou will need to visit an average of / objectscomparing each one' key with the desired value this process 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 tree consists of nodes connected by edges figure shows tree in such picture of tree (or in our workshop appletthe nodes are represented as circlesand the edges as lines connecting the circles trees have been studied extensively as abstract mathematical entitiesso there' large amount of theoretical knowledge about them tree is actually an instance of more general category called graphbut we don' need to worry about that here we'll discuss graphs in "graphs,and "weighted graphs