Chapter 11
Search Trees
Contents
11.1.1 Searching Within a Binary Search Tree
11.1.2 Insertions and Deletions
11.1.4 Performance of a Binary Search Tree
11.2.1 Java Framework for Balancing Search Trees
11.4.4 Amortized Analysis of Splaying
11.1 Binary Search Trees
In Chapter 8 we introduced the tree data structure and demonstrated a variety of applications. One important use is as a search tree (as described on page 338). In this chapter, we use a search-tree structure to efficiently implement a sorted map. The three most fundamental methods of of a map (see Section 10.1.1) are:
get(k): | Returns the value v associated with key k, if such an entry exists; otherwise returns null. |
put(k, v): | Associates value v with key k, replacing and returning any existing value if the map already contains an entry with key equal to k. |
remove(k): | Removes the entry with key equal to k, if one exists, ... |
Get Data Structures and Algorithms in Java, 6th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.