在动态存储分配和释放期间使用循环链表作为“空闲列表”v/s平衡二叉搜索树

Question

链表的缺点是，要 malloc() 一个块，内存分配器必须搜索链表，然后如果找到该地址，则返回它。那么为什么不使用二叉树来减少搜索时间呢？

NVIDIA提出的问题之一 http://www.careercup.com/question?id=9765724

在这里找到了一篇讨论它的相关文章

Answer 1

如果我理解正确，请查看此链接：

内存分配的时间复杂度

堆分配可以通过将可用内存表示为链表来完成，但是任何相当复杂的内存管理器都会使用更快的东西，例如我发布的问题的答案中提到的 AVL 树。甚至还有一个 O(1) 解决方案，称为 TLSF（两级隔离拟合），答案中也提到了。