c - 连续可变有序列表

Question

这可能存在也可能不存在，但我正在寻找一种存储排序整数列表的方法，该列表在内存中是连续的，相当紧凑，并允许 O(log n) 摊销插入和删除。各种自平衡二叉搜索树似乎都有我想要的插入和删除属性，但是到处都是用指针实现的，不太适合我的用例。有任何想法吗？

（如果重要的话，实现语言几乎肯定是 C 语言。如果您提出的任何建议都有现有的实现，那就更好了，但我可以自己编写。）

Answer 1

根据“读取发生多于写入”的事实，您可以尝试在其之上使用动态调整大小的数组+二进制搜索。因此，您将有O(log n)时间访问元素（读取），但您必须O(n)为插入/删除付费（O(log n)- 搜索数组中的正确位置 + O(n)- 向右或向左移动元素）。这有点慢，但这是解决问题的方法。试着想一想。

Answer 2

二叉搜索树可以使用数组来实现。