[Design] Treap and SearchTree modules

[rapiz1]

Treap is a kind of Search Trees. In the original proposal, Treap is listed separately from Search Tree. However, Treap is equivalent to any other Search Tree in terms of operations supported. I think we can keep only one Search Tree. We can use Treap as the underlying structure for Search Tree. Alternatively, we can also use an AVL Tree or Red-black Tree. But I don't see the point to keep both Treap and SearchTree module. In brief, I think only one module should be provided: A Search Tree module containing Treap, or any other balanced tree. @krishnadey30 @e-kayrakli @cassella What do you think?

---

SearchTree.Treap / TreapMap

A randomlized serach tree. Fast in practice.

I'm also proposing a kind of Map built on Treap.

In other langauges

LANG	LIB
C++	Boost.Intrusive.treap

vs other balanced tree

https://github.com/chapel-lang/chapel/issues/15658#issuecomment-629009285

Interface

Same as SkipList TreapMap, same as Map but with Treap as the underlying structure

[bradcray]

Putting myself in a user's shoes, I often want there to be one data type with a consistent interface, but to have a compile-time / param-based way to select between multiple implementations under the covers (e.g., linked list vs. vector-based list vs. multi-vector-based list). I'm not sure whether that would apply here or not (I don't know much about treaps), but wanted to throw it out as food for thought.

[cassella]

I think the primary question is: "Of Treap, AVL Tree, and Red-Black Tree: which combination should be implemented?". (With subquestions as to priority and organization once the primary question is decided.) There are a few ways that could be answered.

I find it's helpful to make a list of the possibilities, with a little more detail to flesh them out, and describing the advantages and disadvantages of each approach. Pick one as a baseline to write all the others' advantages and disadvantages in comparison to. Since you're proposing one, it makes sense to use that one as the baseline.

Other people can then suggest other approaches, or other advantages/disadvantages.

[rapiz1]

So we agree on implementing Treap, AVL, or RBT as part of SearchTree module instead of separating Treap and SearchTree modules as the original project idealist implied.

Comparison

reference

Treap Pros:

• Easy to implement
• Fast in practice. Sometimes it could be even faster than Red-Black Tree depending on the implementation and the input.

Cons:

• It bases on randomization. Time complexity is expected, not stable ( though fast enough in practice)

Red-Black Tree C++ STL std::map implies RBT.

Pros:

• Strictly balanced. Best in theory
• Very Fast.

Cons:

• Difficult to implement. (It will take me far more time than other structures)

AVL Tree A medium between Treap and Red-Black Tree. Difficult than Treap and easy than Red-Black Tree. Pros:

• Performance is very similar to Red-Black Tree

---

So I'm thinking I can implement Treap as a submodule as SearchTree ( just like current Sort module and various sorting algorithms) as an initial effort. Then if I have time I can get back to implement RBT to avoid postponing the whole plan.

[rapiz1]

Closed by https://github.com/chapel-lang/chapel/issues/15921