arrays - 使用数组的二叉树表示

Question

使用基于数组的二叉树实现而不是旧的基于节点的实现是否有任何速度/空间/一般性能提升？我理解基于数组的树的旋转或任何其他复杂修改将是可怕的，但在简单的二叉树实现的情况下，你会说通过数组来做会更好吗？

Answer 1

我猜您正在寻找Binary Heap。

Answer 2

基于数组的版本不使用堆分配，因此它很可能都适合缓存，并且需要更简单的指针数学来加快遍历所需的读取量。如果您现在在编译时大小受到限制，那么它是更快的解决方案。

Answer 3

delete如果您的主要工作流程包括构建一棵树，然后通过一系列delete-range操作将其拆除，那么嵌入在数组中的二叉树可能比基于指针的树快得多。请参阅拆解树。另请参阅此答案。