binary-search-tree - “Programming Pearls” : Searching

Question

我们可以通过保存一个集合来避免对存储分配器的多次调用 他自己的结构中的可用节点。

这个思想可以应用于二叉搜索树数据结构。

作者说:“一次分配所有节点可以大大减少 tree 的空间需求，这将运行时间减少了大约三分之一。"

我很好奇这个技巧如何减少空间需求。我的意思是如果我们 想要构建一个有四个节点的二叉搜索树，我们需要分配 这四个节点的内存，不管我们是一个一个分配还是全部分配 一次。

Answer 1

众所周知，内存分配器不擅长分配非常小的对象。这种情况在过去十年中有所改善，但书中的技巧仍然适用。

大多数分配器在分配给您的 block 中保留附加信息，以便它们可以正确释放内存。例如，malloc/free 对 C 或 new[]/delete[] 对 C++ 需要将有关实际内存块长度的信息保存在某处；通常，此数据在返回给您的地址之前的四个字节中结束。

这意味着每次分配至少会浪费四个额外的字节。如果您的树节点占用 12 个字节(两个指针各占 4 个字节，数字占 4 个字节)，将为每个节点分配 16 个字节 - 增加 33.3%。

内存分配器还需要执行额外的簿记工作。每次从堆中取出一个 block 时，分配器都必须考虑到这一点。

最后，您的树使用的内存越多，在处理当前节点时从缓存中获取相邻节点的可能性就越小，因为内存中到下一个节点的距离较远。