c - 使用符号表的二叉搜索树索引实现

Question

我正在阅读作者 Robert Sedwick 在《C++ 算法》一书中使用符号表实现索引。

下面是书中的片段

We can adapt binary search trees to build indices in precisely the same manner as we provided indirection for sorting and for heaps. Arrange for keys to be extracted from items via the key member function, as usual. Moreover, we can use parallel arrays for the links, as we did for linked lists. We use three arrays, one each for the items, left links, and right links. The links are array indices (integers), and we replace link references such as

x = x->l

in all our code with array references such as

x = l[x].

This approach avoids the cost of dynamic memory allocation for each node—the items occupy an array without regard to the search function, and we preallocate two integers per item to hold the tree links, recognizing that we will need at least this amount of space when all the items are in the search structure. The space for the links is not always in use, but it is there for use by the search routine without any time overhead for allocation. Another important feature of this approach is that it allows extra arrays (extra information associated with each node) to be added without the tree-manipulation code being changed at all. When the search routine returns the index for an item, it gives a way to access immediately all the information associated with that item, by using the index to access an appropriate array.

This way of implementing BSTs to aid in searching large arrays of items is sometimes useful, because it avoids the extra expense of copying items into the internal representation of the ADT, and the overhead of allocation and construction by new. The use of arrays is not appropriate when space is at a premium and the symbol table grows and shrinks markedly, particularly if it is difficult to estimate the maximum size of the symbol table in advance. If no accurate size prediction is possible, unused links might waste space in the item array.

我对以上文字的问题是

1. 作者所说的“我们可以像对链表一样对链接使用并行数组”是什么意思？这条语句是什么意思，什么是并行数组。

2. 作者的意思是链接是数组索引，我们用 x=l[x] 替换链接引用，例如 x=x->l？

3. 作者所说的“这种方法的另一个重要特征是它允许添加额外的数组(与每个节点关联的额外信息)而无需更改树操作代码”是什么意思。 ?

Answer 1

您似乎已经编辑了文本以删除有用的引用资料。或者你有文本的早期版本。

我的第三版指出，索引构建在第 9.6 节中介绍，其中涵盖了过程，并行数组在第 3 章中进行了解释。并行数组只是存储有效负载(键和可能保存的数据)在树中)和三个或更多独立数组中的左/右指针，使用索引将它们连接在一起(x = left[x])。在这种情况下，您可能会得到类似这样的结果:

int leftptr[100];
int rightptr[100];
char *payload[100];

等等。在该示例中，节点 # 74 将其数据存储在 payload[74] 中，左右“指针”(实际上是索引)存储在 left[74] 中和 right[74] 分别。

这与具有将有效负载和指针保存在一起的结构的单个结构数组形成对比 (x = x->left;):

struct sNode {
    struct sNode *left, right;
    char payload[];
};

因此，对于您的具体问题:

1. 并行数组只是将树结构信息与负载信息分开，并使用索引将来自这些数组的信息联系在一起。

2. 由于您使用数组作为链接(这些数组现在包含数组索引而不是指针)，您不再使用 x = x->left 向左移动 child 。相反，您可以使用 x = left[x]。

3. 树操作只对链接感兴趣。通过将链接与有效负载(以及其他可能有用的信息)分开，操作树结构的代码可以更简单。