C++二叉搜索树实现，动态数组还是structs/class？

Question

我的任务是实现一个二叉搜索树，并且正在走通常的结构路线：

struct Node { 
    int value;
    Node * left;
    Node * right;
    Node( int val ) {
     ...
    }
}

当我想到使用动态数组实现它并使用算术计算出左右节点时。我的问题是，数组实现是否会改变操作的时间和 space 复杂性（插入、删除、有序遍历等），是好是坏？

我可以看出删除操作可能是个问题，重新组织数组并保持树的结构，但树的大小很小，最多一百个节点。

Answer 1

Will the time and space complexity of the operations (insert, delete, inorder walk, et al.) change?

在基于数组的树中的非叶节点中插入和删除将需要移动数组中它之后的所有元素。这将复杂度从 O(log n) 更改为 O(n log n)。

will an array implementation be a better use of memory than using structs?

是的，毫无疑问。基于数组的树对缓存更友好，分配更少，而且不需要为每个节点存储指针。

C++ binary search tree implementation, dynamic array or structs/class?