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

Question

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

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

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

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

Answer 1

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

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

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

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

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