search

srdja / Collections-C

A library of generic data structures for the C language.
http://srdja.github.io/Collections-C
GNU Lesser General Public License v3.0
2.78k stars 328 forks source link

How about adding AVL or Red Black tree data structure? #144

Open khasanovasad opened 3 years ago

khasanovasad commented 3 years ago

I would love to see self balancing Binary Search Tree data structure with generics support. Ready to start working on it as long as it is OK. Here I have a draft version written for my own library. Should be changed to match the overall standards of Collections-C repository. My AVL tree implementation:

https://github.com/khasanovasad/TheAlgorithms/blob/main/data-structures/include/ue_avl.h https://github.com/khasanovasad/TheAlgorithms/blob/main/data-structures/src/ue_avl.c

srdja commented 3 years ago

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 commented 3 years ago

Good. I will work on that!

khasanovasad commented 3 years ago

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 commented 3 years ago

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!