Skip to main content
Software Engineering

Return to Answer

added 50 characters in body
Source Link
user541686
user541686
  • 8.2k
  • 10
  • 40
  • 50

I would consider an alternative if you are fine with randomized data structures: Skip Lists.

From a high-level point of view, it's a tree structure, except that it's not implemented as a tree but as a list with multiple layers of links.

You'll get O(log N) insertions / searches / deletes, and you won't have to deal with all those tricky rebalancing cases.

I've never considered implementing them in a Functional Language though, and the wikipedia page does not show any, so it may not be easy (wrt to immutability)

I would consider an alternative: Skip Lists.

From a high-level point of view, it's a tree structure, except that it's not implemented as a tree but as a list with multiple layers of links.

You'll get O(log N) insertions / searches / deletes, and you won't have to deal with all those tricky rebalancing cases.

I've never considered implementing them in a Functional Language though, and the wikipedia page does not show any, so it may not be easy (wrt to immutability)

I would consider an alternative if you are fine with randomized data structures: Skip Lists.

From a high-level point of view, it's a tree structure, except that it's not implemented as a tree but as a list with multiple layers of links.

You'll get O(log N) insertions / searches / deletes, and you won't have to deal with all those tricky rebalancing cases.

I've never considered implementing them in a Functional Language though, and the wikipedia page does not show any, so it may not be easy (wrt to immutability)

Source Link
Matthieu M.
Matthieu M.
  • 15.3k
  • 5
  • 48
  • 69

I would consider an alternative: Skip Lists.

From a high-level point of view, it's a tree structure, except that it's not implemented as a tree but as a list with multiple layers of links.

You'll get O(log N) insertions / searches / deletes, and you won't have to deal with all those tricky rebalancing cases.

I've never considered implementing them in a Functional Language though, and the wikipedia page does not show any, so it may not be easy (wrt to immutability)