索引树的最佳方法

Question

我有一棵树，节点数量从100到500,000多个不等。树中的每个节点都被赋予一个唯一的id。由于树中有大量的节点，解析到树中搜索节点的计算量很大。所以我想实现一个索引数据结构，它有一个id和另一个指向节点的指针，--这是实现这个索引数据结构的最好方法，我想用一个数组来实现它，但是它不会有帮助，因为在执行之前不知道节点的数量。

树中的节点数可能超过500 K，并且动态增加，树中的节点不依赖于唯一的id，该id用于与其他节点的区分，并主要用于搜索树中的节点。

下面的示例可能给出了关于树的粗略想法(但这不是实际的场景，只是使用它来解释树)。

假设树描述的是车辆，根节点下的每个节点对车辆的类型进行分类，假设在这个节点下有两轮车、列车、四轮车、卡车等，在此节点下可能会有基于其他标准的进一步分类，如make、model、engine等。而且每个节点都有很少的属性(如xml中的属性)。因此，在最后，我们将使用id来搜索节点是否存在，如果这样读取这些属性，那么树上还有多个其他函数，搜索就是其中之一，它花费了大量的时间。

Answer 1

由于无法估计树节点的数目，所以可以使用另一个平衡搜索树，例如R树，将地址存储到您的树节点。

例如，定义平衡搜索树的节点结构如下：

struct rb_node
{
    int id;
    node *n; //pointer to your tree node
};

然后根据id建立一个均衡的搜索树。

每次向树插入节点时，也要向平衡树插入一个节点。然后，您可以使用id快速找到节点。

Answer 2

对于我来说，有一个id字段，然后一个node指针字段，这听起来有点像hashmap (或者hashtable，或者什么东西)。

如果你不知道这是什么，你基本上有一个数组，它只能变大(以2的幂)，填充节点。当您想要添加数据时，对键执行散列计算，在本例中是id字段。这给了你一些数字。然后你说number % size_of_array。这需要模块余数才能得到实际上在数组大小范围内的数组元素。假设数组大小为2的幂，则可以确保所有节点都已填满。

您还需要一些其他功能，您可以在某个地方了解它们。

现在，(或者假设您已经知道了hashmap)，您使用id字段作为每个节点的键，而每个节点的值指针将是指向树节点的指针。这通常是相当快的，除非您有很多冲突，或者具有相同哈希的节点，尽管通常您不应该超过两三次重新哈希。

struct hashnode {
  void *key;  //This is the id field.
  void *value;  //This points to the tree node.
}

struct hashmap {
  uint32_t size;
  uint32_t used;

  hashnode *nodes;
};