DS Search Tree Operations

Section 8.3 Search Tree Operations

In Section 6.2, we looked at the definition of the ADT for maps and for sets. As a reminder, here again is the interface we created to represent a map.

🔗

Listing 8.3.1. Interface representing Map ADT

🔗

interface MapADT<K, V> {
    // Adds the key/value pair to the map.
    // If the key is already in the map, it replaces the old value with the new one.
    fun put(key: K, value: V)

    // Returns the value matching the provided key, or null otherwise.
    fun get(key: K): V?

    // Removes the key from the map.
    // Returns the matching value stored in the map, or null otherwise.
    fun remove(key: K): V?

    // Returns true if the key is in the map, false otherwise.
    fun containsKey(key: K): Boolean

    // Returns the number of key/value pairs stored in the map
    fun size(): Int
}

There’s an important detail about MapADT that we didn’t focus on earlier. The type of the key, which we refer to as K in the interface, is not a subclass of Comparable. In other words, in any of the code that we write in a class implementing MapADT (such as HashTableMap), we would be forbidden from doing less-than or greater-than comparisons between keys. This was reasonable to do in the chapter on hashing, because hashing doesn’t require such comparisons. However, in this chapter, we want to be able to consider maps and sets where we can do such comparisons. Here are two main reasons:

There are applications for maps and sets where we might want to do such comparisons. The most common use case is where we want to efficiently obtain all keys in a particular range.

🔗
In this chapter, we will be looking at binary search trees as an approach for implementing sets and maps. That approach is fundamentally based on organizing the data based on ordering between keys.

🔗

🔗

Therefore, in this chapter we will define a slight modification to the map ADT, which requires the type of the key to be Comparable. While we’re at it, we’ll add one method to enable range queries, to help emphasize that this is an additional advantage that we get with this approach. Instead of redefining the whole map from scratch, we’ll use inheritance to create a new subinterface that includes everything from the MapADT interface, but includes one more method that takes advantage of comparison operations. We also make sure to indicate that we can do comparison operations on the type K.

🔗

Listing 8.3.2. Interface representing Comparable Map ADT

🔗

// Subinterface of MapADT that adds Comparable capability.
interface ComparableMapADT<K: Comparable<K>, V>: MapADT<K, V> {

    // Return a list of all keys from fromKey to toKey, inclusive.
    fun keyList(fromKey: K, toKey: K): List<K>
}

We will likewise similar add a similar update to our set ADT.

🔗

Listing 8.3.3. Interface representing Comparable Set ADT

🔗

// Subinterface of SetADT that adds Comparable capability.
interface ComparableSetADT<E: Comparable<E>>: SetADT<E> {

    // Return a list of all keys from fromKey to toKey, inclusive.
    fun keyList(fromElement: E, toElement: E): List<E>
}

You have attempted of activities on this page.

🔗

Prev Top Next