Tham khảo tài liệu 'thuật toán algorithms (phần 20)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | ELEMENTARY SEARCHING METHODS 183 The call treeprint head will print out the keys of the tree in order. This defines a sorting method which is remarkably similar to Quicksort with the node at the root of the tree playing a role similar to that of the partitioning element in Quicksort. A major difference is that the tree-sorting method must use extra memory for the links while Quicksort sorts with only a little extra memory. The running times of algorithms on binary search trees are quite dependent on the shapes of the trees. In the best case the tree could be shaped like that given above for describing the comparison structure for binary search with about lg N nodes between the root and each external node. We might roughly expect logarithmic search times on the average because the first element inserted becomes the root of the tree if N keys are to be inserted at random then this element would divide the keys in half on the average leading to logarithmic search times using the same argument on the subtrees . Indeed were it not for the equal keys it could happen that the tree given above for describing the comparison structure for binary search would be built. This would be the best case of the algorithm with guaranteed logarithmic running time for all searches. Actually the root is equally likely to be any key in a truly random situation so such a perfectly balanced tree would be extremely rare. But if random keys are inserted it turns out that the trees are nicely balanced. The average number of steps for a treesearch in a tree built by successive insertion of N random keys is proportional to 2 In N. On the other hand binary tree searching is susceptible to the same case problems as Quicksort. For example when the keys are inserted in order or in reverse order the binary tree search method is no better than the sequential search method that we saw at the beginning of this chapter. In the next chapter we ll examine a technique for eliminating this worst case and
