I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node to all the others. I want to recursively unite all of the Tries if I know each Trie's parent.. how can I do that?

This is my data structure and this is how I am using it.

typedef struct trie
    int id;
    int parent;
    struct trie *child;
    struct trie *sibling;
} *Trie;
Trie *forest;

EDIT with photos:

We have 2 tries here: first second

If node 4 which is the "root" of the right Trie had the parent 9 for example, I would like to "unite" 9 to 4 and get the bigger Trie.

I would like to implement a function

Trie uniteForest(Trie root, Trie *forest, int id)
    // do stuff

That returns me the final "Trie".

  • 1
    $\begingroup$ I'm not sure what you're asking. What do you mean by "unite"? Do you just make one node a child of the other? Also what is a Trie's parent? Is this different than the root? Also, if these are specifically Trie's then uniting them is non trivial if you want to maintain properties of a Trie. For instance when merging a trie of {his, her, him} and a trie of {hero, heavy, hippy}. Could you provide a small picture/diagram of an example of what you're looking for? $\endgroup$ – ryan Apr 9 '19 at 16:21
  • $\begingroup$ @ryan yeah i will provide pictures in 10 mins $\endgroup$ – C. Cristi Apr 9 '19 at 16:25
  • $\begingroup$ @ryan Check the edit! I hope my question is more clear now $\endgroup$ – C. Cristi Apr 9 '19 at 16:56
  • 1
    $\begingroup$ Also, can you specifically define what it means to "unite" a node A and a node B? This might help clear up some confusion as I don't quite get it from this example. $\endgroup$ – ryan Apr 9 '19 at 17:39
  • 1
    $\begingroup$ I mean to define "unite" in general, not for this example. The definition should be something like this definition of union: "Union(x,y) uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other." $\endgroup$ – ryan Apr 9 '19 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.