为什么存储分配器使用循环链表来存储已分配/空闲地址而不是平衡树?遍历链表需要O(n)阶的复杂度而遍历平衡树只需要O(logn)阶，对吧?它背后的优势/理由是什么?
前提("存储分配器使用循环链表来存储已分配/空闲地址")不一定是正确的。对于某些分配器可能是正确的，但一般情况下不是这样。
如果分配器使用类似链表的结构来跟踪内存块，那么它通常作为元数据嵌入到内存块本身中。而不是作为一个单独的数据结构。
例如，每个内存块可以从状态(空闲/已分配)和块大小开始。这种方法基本上实现了一个链表(使用大小，你可以很容易地确定下一个块的开始地址)，但是它有一个链表没有的其他属性:你仍然可以通过知道它的内存地址来找到一个特定的内存块(节点)。
因此，您将有一个O(1)访问时间(因为您或编译器知道内存块的内存地址)。合并邻近的空闲块也很简单。如果需要运行某种碎片整理或压缩算法，可以使用类似链表的结构。查找足够大小的空闲块也可以使用类似链表的结构来完成(尽管有时会为空闲块专门使用第二个嵌入的链表，以最小化分配函数的开销)。
当然，这只是解决问题的一种可能方法。但它表明，使用链表并不一定是比其他数据结构更糟糕的选择。
好吧，分配器通常是专门构建的，非常仔细，并且特别针对期望它们服务的特定需求进行精心设计。
因此，在许多工业强度分配器中可能存在更复杂和更不规则的结构。
尽管如此，假设你的问题的前提是准确的:
最坏情况下的复杂度与非常大的遍历最相关。大多数分配器的设计都是为了使必要的遍历量通常非常小，小到维护平衡树所需的额外开销使得平均情况下的遍历变慢。此外，工程师更喜欢最简单的解决方案，除非更复杂的解决方案明显更好:循环链表是最简单的。
遍历一个链表需要O(n)阶的复杂度
是的，但是存储分配器的目的是提供一些已分配的空间，这并不一定需要"遍历"存储先前分配的结构。例如，如果我们每次都以特定大小的块分配内存(因此我们在结构中保留该大小的块)，那么我们只需要返回第一个。一般来说，我们只需要找到一个足够大的节点，所以我们一直寻找，直到找到一个足够大的节点(这通常会很快发生)。
而平衡树可以在O(logn)内遍历，对吧?
我们可以在O(logn)中找到一个特定的元素，但我们不能在那个时间内"遍历"树，因为根据定义，对数据结构的"遍历"意味着访问每个节点，并且有O(n)个节点。如果树有合适的搜索树属性，我们只能在O(logn)内找到一个特定的元素。我们需要哪个节点呢?这将使我们有效地找到，例如，足够大的最小分配;但无论如何，这并不一定是我们想要回报的(因为这种策略导致生成许多小块，这些小块可能适合也可能不适合未来的任何分配，并且会使结构膨胀)。也看到。