How to use or create AVL tree sets analog to assoc maps?

Help! Data Structure
1

I am really happy about the lib(assoc), because partly that is exactly what I need for my project. However, I also need AVL tree sets. Is there a lib that provides these, or can they be derived from the assoc lib somehow? In theory it should be simple to have any value other than a key/value pair in the tree, shouldn’t it?

2

From: library(assoc): Association lists

This library uses AVL trees to implement association lists. This means that

  • inserting a key
  • changing an association
  • fetching a single element

are all O( log(N) ) worst-case (and expected) time operations, where N denotes the number of elements in the association list.

Also see: Create a binary search tree from a list of integers

For even more examples see this search of StackOverflow; note the results may not be exactly what you seek so you will have to research the results.

HTH

3

It is a tree of key/value pairs. What if I want to have any other (i.e. not key/value pair) values in that tree, such that it is then simply a set, not a map? I could, of course, put a dummy element as value if I never need it, and the set element as key, but that seems like a waste to me.

The implementation of an AVL tree map can easily be a specialisation of the more general AVL tree set. This is why I am asking. Why provide the special functionality and not the more general one?

4

Perhaps you seek library(ordsets): Ordered set manipulation

5

Thanks for the suggestion. What I am really looking for is a (so to say) set implementation that goes well with the assoc implementation, in that it uses exactly the same tree representation, and that I can neatly interchange them (and, for example, ask whether an AVL tree happens to be an AVL map, and act accordingly, if I need to, which I do, because I want to compose a more complex data structure of both).

I am left with two alternatives now: I could i) simply misuse pairs with dummy value elements or ii) take the source of the assoc lib and generalize it to an AVL tree lib.

I would vote for the latter to be done “officially”, if that is an option at all.

On the other hand I might as well specialize the RB tree into an RB map. I would prefer AVL, but perhaps this doesn’t really matter, anyway.

1 Like
6

At this point I will stop looking but just because I did not find it does not mean it does not already exist. I typically search the built-in predicates, libraries, packages, packs, SWI-Prolog source code and read the books. Sometimes I also ask.

Searching the source code is hardest because sometimes there are data structures hidden in the code that are not exposed. If you know Object Oriented code think of it like an inner class. You also have to search all of the repositories.

1 Like
7

Thanks, @EricGT, I do cherish your answers. I am already doing what you suggest. It is not so much a question of possibility now, more one of decision of how to continue. It is not overly difficult to implement an AVL tree, but of course the libs or other sources show how to do it efficiently, in other words, with higher quality.

Plus, I have learned just some minutes ago, that assoc is a library traditionally shipped with many PROLOG versions. Again, I ask myself why then an AVL set, so closely related and already implemented in principle, is traditionally not included. But it is obviously not, and so I will make my own one. Thanks so far!

1 Like
8

Well, yes. A node in the AVL tree is a term t/5. If you turn the map into just a set of keys that could be t/4. That reduces the size of a node from 48 to 40 bytes at the cost of most duplicating the code in library(assoc). I doubt that is worth the trouble. Of course I might have misunderstood …

There are a lot of ways to represent a set in Prolog (and any other language). Better advice might be possible if you share what you want to do with the set. What kind of elements are in there? Must be it a backtracking data structure? How large (approx)? What is the expected read/write ratio?

2 Likes
9

Thanks, @jan, for the question.Out of experience these are the moment where I learn something, or at least might discover a misconception. Your statement about the t term shows a direction, because I (perhaps naively) come from an idea that every key/value pair would itself be an element contained by that tree. But that is not so, rather are both key and value contained in the t term.

If they were within another term, then they could be derived from an AVL set, but that would indeed be a waste, forcing another term added on every node. That was my misunderstanding.

Basically I want to combine maps to trees (an conjoining them, i.e. they would be directed graphs rather than trees), and close them with simple value sets. Given your hint, the waste of space is probably negligible.

update: Forgot to add that I usually build them as a whole, and then regularly filter them, i.e. extract sub sets (or sub maps). But the vast majority of nodes will not have dummy values, so I think this is a strong hint towards not worrying about the few that have.

1 Like
10

For a long time, Python didn’t have sets; people just used dicts with a dummy value (typically None, which is a bit weird because that doesn’t play nicely with default boolean coercion for detecting whether a key is present or not).

Depending on your performance requirements, you might also be interested in red-black trees library(rbtrees). Annoyingly, some of the predicates have a different parameter order than library(assoc); so you might want to use wrapper predicates to allow you to switch implementations if you’re not sure which is best.

1 Like