3

我将二叉树定义为搜索表。树是一个链表二叉树，节点就像

typedef struct node{
    int key;
    char *buf;
    ...
}node_t;

typedef table_t node_t *; 所以我有类似的功能

  insert(table_t table, node_t node)
  search(table_t table, node_t node)

现在我有多个键，比如

typedef struct node{
    int key1;
    int key2;
    char *buf;
    ...
}node_t;

我想有这样的功能：

  search_by_key1(table_t table, node_t node, int key1)
  search_by_key2(table_t table, node_t node, int key2)

实际上，它就像一个数据库，我可以搜索任何键来查找项目。

有源代码示例吗？我正在使用 linux C 谢谢！

4

4 回答 4

1

二叉树只能由一个键索引。

如果要使用多个键进行索引，可以为每个键构建一个元树，元树具有元节点，其中：

typedef struct meta_node
{
    int index;
    node * data;

    ...
}
meta_node_t;
于 2013-06-10T10:38:50.547 回答
0

好吧，在二叉树中，键仅在相互关联时才有意义。这意味着仅当 key1_b 在右分支中较大/较小时（取决于您如何构建它）， key1_a 在左分支中才有意义。如果您有一棵由两组键组成的树，假设它们具有相同的比例，它们可能位于相同的树数据结构中。如，如果 key2 中的每个键正好比 key1 高 50。但这根本没有用。

我唯一的想法就是让它有一些空值键。因此，如果您正在遍历您的树并且您位于 key1 的叶子而不是 key2 的叶子上，您只需继续前进，树的其余部分将在键中具有空值（可能是 -1？），或将有一个布尔触发器，因此 key1 不再存在于树的这个分支中。这有点难以描述，但你明白我的意思吗？就像基本上把它当作两棵交织在一起的树，然后一起走，直到你不得不发散（并且在保持实际树结构相同的同时做到这一点，但其中一个键具有空值）

不过听起来太复杂了，所以我不知道是否值得。

于 2013-06-09T18:26:07.327 回答
0

您可以有两棵树，但仍使用相同的节点：

struct basic_node {
    int key;
    struct basic_node *left, *right;
    struct node *node;
};
struct node {
    struct basic_node tree1;
    struct basic_node tree2;
    char *data;
};

struct node *tree1_root, *tree2_root;

创建节点时，您将分配一个struct node，然后basic_node根据其键将每个分别插入到相应的树中。在 eachbasic_node中，将node指针设置为包含它的节点。

查找时，只需从任一树根开始，然后进行简单查找，这将引导您找到所需的basic_node，然后找到节点本身。

如果要删除，则必须先从两棵树中取消链接节点，然后才能释放它。

于 2013-06-10T10:46:19.207 回答
0

我知道这个问题很久以前就被问过了，但是我在搜索用户正在寻找的确切数据结构时遇到了它......

长话短说，可以有一个具有多个键的二叉搜索树，称为 KD 树。

基本上，您所做的是构建一个正常的二叉搜索树，但您要跟踪节点在树中的“深度”。对于像这个问题使用的两个键，所有深度为偶数的节点都根据 key_a 的值对其子级进行排序，所有深度为奇数的节点都根据 key_b 的值对其子级进行排序。

同样，当您搜索树时，您会遍历分支。当你在一个均匀深度的节点上时，你根据存储在该节点的 key_a 中的值是小于还是大于 key_a 的期望值来决定走哪个分支。当您在奇数深度的节点上时，您将根据节点的值和所需的 key_b 值来决定。

如果我没记错的话，谷歌使用一种非常相似的数据结构来根据地理位置的范围快速找到位置，使用纬度作为一个键，经度作为另一个键。

于 2020-07-30T05:51:11.273 回答