Skip to content

Latest commit

 

History

History
141 lines (102 loc) · 4.59 KB

tree-set.asc

File metadata and controls

141 lines (102 loc) · 4.59 KB

Tree Set

A tree set is a data structure that stores unique values and keeps them sorted. You can get check if a value exists in O(log n) time.

Another way to implement a Set is by using a hash function, as we covered on Hash Set. There are some critical differences between the two implementations.

HashSet vs TreeSet

We can implement a map using a balanced binary search tree or a hash function. If we use them to implement a Set, we would have a HashSet and TreeSet. As with all data structures, there are trade-offs. Here are some key differences:

  • TreeSet, would return the values sorted in ascending order.

  • HashSet, would return the values in insertion order.

  • Operations on a HashSet would take on average O(1), and in the worst case (rehash is due), it would take O(n).

  • Operation on a TreeSet is always O(log n).

Time Complexity Hash Set vs Tree Set

Table 1. Time complexity HashSet vs TreeSet

Data Structure

Searching By

Insert

Delete

Space Complexity

Index/Key

Value

Hash Set

O(1)

-

O(1)*

O(1)

O(n)

Tree Set

O(log n)

-

O(log n)

O(log n)

O(n)

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

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

Implementing a Tree Set

TreeSet’s constructor method and size attribute
link:../../../src/data-structures/sets/tree-set.js[role=include]
}

  1. Converts an array or any iterable data structure to a set.

An everyday use case for Sets is to remove duplicated values from an array. We can do that by bypassing them in the constructor as follows:

Removing duplicates from an Array using a Set
set = new TreeSet([1, 2, 3, 2, 1]);
expect(set.size).toBe(3);
expect(Array.from(set.keys())).toEqual([1, 2, 3]);

Ok, now let’s implement the add method.

Adding elements to a TreeSet

For adding values to the set, we Tree.add method.

TreeSet’s constructor method and size attribute
link:../../../src/data-structures/sets/tree-set.js[role=include]

Our BST implementation can hold duplicated values. It has a multiplicity tally to keep track of duplicates. However, we don’t dupe in a set. For that, we check if the value is already in the tree. Don’t worry about adding extra lookups. The Tree.has is also very performant O(log n).

Searching for values in a TreeSet

Again, we rely on the Tree implementation to do the heavy lifting:

TreeSet’s has method
link:../../../src/data-structures/sets/tree-set.js[role=include]
Deleting elements from a TreeSet

We delete the elements from the TreeSet using the remove method of the BST.

TreeSet’s delete method
link:../../../src/data-structures/sets/tree-set.js[role=include]

Voilà! That’s it!

Converting TreeSet to Array

Another use case for a Set is to convert it to an array or use an iterator (for loops, forEach, …). Let’s provide the method for that:

TreeSet’s iterator
link:../../../src/data-structures/sets/tree-set.js[role=include]

We are using the inOrderTraversal method of the BST to go each key in an ascending order.

JavaScript Built-in Symbol iterator

The Symbol.iterator built-in symbol specifies the default iterator for an object. Used by for…​of, Array.from, and others.

Now we can convert from set to array and vice versa easily. For instance:

TreeSet’s iterator
const array = [1, 1, 2, 3, 5];

// array to set
const set = new TreeSet(array);

// set to array
Array.from(set); //↪️ (4) [1, 2, 3, 5]

No more duplicates in our array!