What's the use of avl_height/2? And why is assoc_height/2 absent?

Question

The SICStus Prolog libraries assoc and avl both provide tree implementations of association lists.

While the binary trees used by library(assoc) are unbalanced (and thus can degrade to linear lists in the worst case), the binary trees used in library(avl) are kept balanced (using balancing operations upon insertion which utilize additional bookkeeping data).

So with library(avl) tree heights are guaranteed to be in O(log N)—even in the worst-case. With library(assoc), heights can range from log₂(N) (best case) to O(log N) (average case) to N (worst case)—depending on the order of insertions.

So why then does library(avl) offer avl_height/2 while library(assoc) does not offer assoc_height/2? (I don't see a use case of avl_height/2, but I see a clear one of assoc_height/2.)

Answer 1

The reason these predicates exists respectively do not exist in the SICStus Prolog library is because this is how it was in Quintus Prolog, from which these libraries originated. I do not know why Quintus made this decision.

I agree that avl_height/2 seems useless whereas assoc_height/2 might be (marginally) useful.

On "why avl, when there are red black trees?": I do not know, but RB-trees are much trickier to implement, especially at the time when Quintus made the decision to offer AVL but not RB trees.

There are other alternatives than AVL and RB trees these days. I am not aware of any systematic investigation into which dictionary implementation would be "best" for Prolog (or SICStus Prolog).