Skip to content

Latest commit

 

History

History
97 lines (73 loc) · 3.39 KB

treemap.asc

File metadata and controls

97 lines (73 loc) · 3.39 KB

TreeMap

A TreeMap is a Map implementation using Binary Search Trees.

Implementing a Map with a tree, TreeMap, has a couple of advantages over a HashMap:

  • Keys are always sorted.

  • Statistical data can be easily obtained like the median, highest, lowest key.

  • Collisions are not a concern so in the worst case is still O(log n).

  • Trees are more space efficient and don’t need to allocate memory beforehand (e.g. HashMap’s initial capacity) nor you have to rehash when is getting full.

Ok, now that you know the advantages, let’s implement it! For a full comparison read the [HashMap vs TreeMap] section.

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 inialize 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. However, 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 tree map, it takes O(log n). This is the 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