How about adding AVL or Red Black tree data structure?

[khasanovasad]

How about adding AVL or Red Black tree data structure?

[khasanovasad]

Good. I will work on that!

[srdja]

Hi @khasanovasad, thanks for the suggestion! We already have an RB tree implemented as the treetable, however, having an additional AVL version would be nice.

[khasanovasad]

Hello, @srdja, I was just wondering if the AVL version of the tree data structure should also be implemented with key-value pair as its data. Or would it be adequate for a node to hold single value only?

[srdja]

Hi @khasanovasad, it depends on what kind of high level container you want to implement. If you want to make another alternative implementation of the table container (which is easily convertible to a set by ignoring the value), then it makes sense to store a key-value pair. On the other hand, if you only want the tree to be used as a set, then you only need one value, and so on depending on the container. Think of it this way: what do you want to do at the level of API? AVL / RB / hash are all implementation details with specific space-time tradeoffs.

I hope that makes sense!