C++二叉搜索树实现，动态数组或结构/类

Question

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

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

当我考虑使用动态数组并使用算术来计算左右节点时。我的问题是，数组实现会改变操作(插入、删除、无序遍历等(的时间和空间复杂性，是好是坏？

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

Answer 1

操作(插入、删除、按顺序行走等(的时间和空间复杂性是否会发生变化？

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

数组实现会比使用结构更好地利用内存吗？

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