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

Question

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

Answer 1

要从数组中创建关联数组，通常从某种结构的数组开始：

struct item {
    key_type key;
    value_type value;
};

然后你会使用keys 来查找values。为了提高效率，您通常希望根据keys 对数组进行排序，因此您可以使用二进制搜索（或插值搜索，如果您的密钥分布有任何程度的可预测性）。

对于一棵树，你会做几乎相同的事情，除了对于一棵树，二叉搜索是默认的。你最终得到一个与数组非常相似的节点，加上几个指针：

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

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