在动态存储分配和释放过程中使用循环链表作为"free list" v/s 平衡二叉搜索树

Question

链表的缺点是，要想malloc（）一个区块，内存分配器必须搜索链表，如果找到了地址，就返回它。那么，为什么不使用二进制树来减少搜索时间呢？

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

找到了一篇相关的文章，在这里进行了讨论

Answer 1

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

内存分配的时间复杂性

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