This chapter provides knowledge of binary search trees. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Binary Search Trees 3/20/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Binary Search Trees 4 = 8 Binary Search Trees 1 Ordered Maps ! Keys are assumed to come from a total order. ! Items are stored in order by their keys ! This allows us to support nearest neighbor queries: ! ! Item with largest key less than or equal to k Item with smallest key greater than or equal to k © 2014 Goodrich, Tamassia, Goldwasser Binary Search Trees 2 1 Binary Search Trees 3/20/14 Binary Search ! Binary search can perform nearest neighbor queries on an ordered map that is implemented with an array, sorted by key similar to the high-low children’s game at each step, the number of candidate items is halved terminates after O(log n) steps n n n ! Example: find(7) 0 1 3 4 5 7 8 9 11 14 16 18 19 8 9 11 14 16 18 19 8 9 11 14 16 18 19 8 9 11 14 16 18 19 m l 0 1 3 4 5 7 4 5 7 l m h 4 5 m l 0 1 0 1 3 3 h h 7 l=m =h © 2014 Goodrich, Tamassia, Goldwasser Binary Search Trees 3 Search Tables ! A search table is an ordered map implemented by means of a sorted sequence n n We store the items in an array-based sequence, sorted by key We use an external comparator for the keys ! Performance: n n n Searches take O(log n) time, using binary search Inserting a new item takes O(n) time, since in the worst case we have to shift n/2 items to make room for the new item Removing an item takes O(n) time, since in the worst case we have to shift n/2 items to compact the items after the removal ! The lookup table is effective only for ordered maps of small size or for maps on which searches are the most common operations, while insertions and removals are rarely performed (., credit card authorizations) © 2014 Goodrich, Tamassia, Goldwasser Binary Search Trees 4 2 Binary Search .
