sicstus-prolog - avl_height/2有什么用？为什么 assoc_height/2 不存在？

Question

SICStus Prolog 库 assoc 和 avl 都提供关联列表的树实现。

虽然library(assoc)使用的二叉树是不平衡的(因此在最坏的情况下可以降级为线性列表)，中使用的二叉树>library(avl) 保持平衡(在插入时使用平衡操作，利用额外的簿记数据)。

因此，使用library(avl)，即使在最坏的情况下，保证树的高度为 O(log N)。对于library(assoc)，高度范围可以从log₂(N)(最好情况)到O(log N)(平均情况)到N(最坏情况)——取决于插入的顺序。

那么为什么会 library(avl) 提供 avl_height/2 而 library(assoc) 却< em>不提供assoc_height/2？ (我没有看到 avl_height/2 的用例，但我看到了 assoc_height/2 的明确用例。)

Answer 1

这些谓词在 SICStus Prolog 库中分别存在和不存在的原因是因为这就是这些库起源于 Quintus Prolog 中的情况。我不知道 Quintus 为何做出这个决定。

我同意 avl_height/2 似乎没用，而 assoc_height/2 可能(勉强)有用。

关于“既然有红黑树，为什么要使用 avl？”:我不知道，但是 RB 树的实现要困难得多，尤其是在 Quintus 决定提供 AVL 而不是 RB 树的时候。

现在除了 AVL 和 RB 树之外还有其他选择。我不知道有任何关于哪种字典实现最适合 Prolog(或 SICStus Prolog)的系统调查。