tree-map.asc

Tree Map

A Map is an abstract data structure to store pairs of data: key and value. It also has a fast key lookup of O(1) for [hashmap-chap] or O(log n) for Tree Map.

We can implement a Map using two different underlying data structures: Hash Map or Tree Map.

HashMap vs TreeMap

A map can be implemented using hash functions or a binary search tree:

• HashMap: it’s a map implementation using an array and a hash function. The hash function’s job is to convert the key into an index that maps to the value. HashMap has an average runtime of O(1).

• TreeMap: it’s a map implementation that uses a self-balanced Binary Search Tree (like [c-avl-tree] or Red-Black Tree). The BST nodes store the key, and the value and nodes are sorted by key guaranteeing an O(log n) lookup time.

When to use a TreeMap vs. HashMap?

• HashMap is more time-efficient. A TreeMap is more space-efficient.

• TreeMap search complexity is O(log n), while an optimized HashMap is O(1) on average.

• HashMap’s keys are in insertion order (or random depending on the implementation). TreeMap’s keys are always sorted.

• TreeMap offers some statistical data for free such as: get minimum, get maximum, median, find ranges of keys. HashMap doesn’t.

• TreeMap has a guarantee always an O(log n), while `HashMap`s has an amortized time of O(1) but in the rare case of a rehash, it would take an O(n).

TreeMap Time complexity vs HashMap

As we discussed so far, there is a trade-off between the implementations.

Table 1. Time complexity for different Maps implementations

Data Structure	Searching By		Insert	Delete	Space Complexity
	Index/Key	Value
Hash Map	O(1)	O(n)	O(1)*	O(1)	O(n)
Tree Map (Red-Black Tree)	O(log n)	O(n)	O(log n)	O(log n)	O(n)

* = Amortized run time. E.g. rehashing might affect run time to O(n).

We already covered Hash Map, so in this chapter, we will focus on TreeMap.

Tip	JavaScript only provides (Hash) Map. That’s enough for most needs. But we will implement a TreeMap so it’s more clear how it works and when it should be used.

Ok, now that you know the advantages, let’s implement it!

Let’s get started with the essential functions. They have the same interface as the HashMap (but the implementation is different).

TreeMap class overview

class TreeMap {
  constructor(){}
  set(key, value) {}
  get(key) {}
  has(key) {}
  delete(key) {}
}

Inserting values into a TreeMap

For inserting a value on a TreeMap, we first need to initialize the tree:

TreeMap constructor

link:../../../src/data-structures/maps/tree-maps/tree-map.js[role=include]

The tree can be an instance of any Binary Search Tree that we implemented so far. For better performance, it should be a self-balanced tree like a Red-Black Tree or AVL Tree.

Let’s implement the method to add values to the tree.

TreeMap add method and size attribute

link:../../../src/data-structures/maps/tree-maps/tree-map.js[role=include]

Adding values is very easy (once we have the underlying tree implementation).

Getting values out of a TreeMap

When we search by key in a treemap, it takes O(log n). The following is a possible implementation:

TreeMap get and has method

link:../../../src/data-structures/maps/tree-maps/tree-map.js[role=include]

One side effect of storing keys in a tree is that they don’t come up in insertion order. Instead, they ordered by value.

TreeMap iterators

link:../../../src/data-structures/maps/tree-maps/tree-map.js[role=include]

1. We implemented the default iterator using the in-order traversal. That’s useful for getting the keys sorted.

JavaScript Iterators and Generators

Generators are useful for producing values that can you can iterate in a for…​of loop. Generators use the function* syntax, which expects to have a yield with a value.

Deleting values from a TreeMap

Removing elements from TreeMap is simple.

TreeMap delete method

link:../../../src/data-structures/maps/tree-maps/tree-map.js[role=include]

The BST implementation does all the heavy lifting.

That’s it! To see the full file in context, click here: here