c - 索引树的最佳方法

Question

我有一棵节点数从 100 到超过 500,000 不等的树。树中的每个节点都有一个唯一的 ID。由于树中有大量节点，解析树以在其中搜索节点的计算量很大。所以我想实现一个索引数据结构，它有 id 和另一个指向节点的指针，什么是实现这个索引数据结构的最佳方法，我想用数组来做，但它赢了'帮助，因为在执行之前不知道节点的数量。

树中的节点数可能超过 500K 并且动态增加，树中的节点根据唯一 id 不相关，此 id 用于与其他节点区分，主要用于搜索节点在树上。

下面的例子可能会给出关于树的粗略概念(但这不是实际场景，只是用来解释树)。

Assume the tree is describing vehicles, each node under the root node classifies the type of vehicle, lets say two wheelers, trains, four wheelers, trucks etc. under this nodes there might be further classifications based on other criteria like make, model, engine etc.. and each node will have few attributes(like in xml). So at the end we will be using the id to search if the node exists if so read those attributes, there are multiple other functions done on the tree, searching is one among them, and it consuming huge amount of time.

Answer 1

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

比如定义平衡搜索树的节点结构是这样的:

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

然后根据id构建平衡搜索树。

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