c++ - 关联数组、数组和树

Question

我有两个问题: 如何修改数组抽象数据类型以实现关联数组？ 如何修改树抽象数据类型来实现关联数组？

Answer 1

要从数组创建关联数组，您通常会从某种结构的数组开始:

struct item {
    key_type key;
    value_type value;
};

然后您将使用key 来查找value。为了提高效率，您通常希望根据 key 对数组进行排序，因此您可以使用二进制搜索(或插值搜索，如果您的键有任何程度的可预测性)分配)。

对于一棵树，你会做几乎相同的事情，除了对于一棵树，二分查找是默认的。您最终得到一个与数组非常相似的节点，外加几个指针:

struct node { 
    key_type key;
    value_type value;
    struct node *left;
    struct node *right;
};

根据涉及的树类型，您可能还需要另一个指针来创建线程树和/或一些平衡信息(例如，对于 AVL 或 R-B 树)。相反，对于 B 树，您最终会得到类似于关联数组的节点数组，并将它们链接在一起形成平衡树。