CODEWITHSUNDEEP
c++cstringtreetrie
sad
sad

Reputation: 820

Why are there separate "trie_node" and "trie" structures?

I have read the following implementation for implementing trie.

typedef struct trie_node trie_node_t;
struct trie_node 
{
int value;
trie_node_t *children[ALPHABET_SIZE];
};

// trie ADT
typedef struct trie trie_t;
struct trie 
{
trie_node_t *root;
int count; 
};

I dont understand why there are two structures when we can have just one with an array of pointers and a value type. Please help.!

Upvotes: 1

Views: 298

Answers (1)

Mohit Jain
Mohit Jain

Reputation: 30489

Short answer

trie_node_t is type of each node inside (linked into a) trie.

trie_t is type of each trie.

Usage

Possible usage may be

trie_t tr1, tr2;  /* Create 2 tries */

addstring(&tr1, "baseball");   /* This adds multiple nodes to existing trie */
addstring(&tr1, "basketball");

addstring(&tr2, "rock");
addstring(&tr2, "rocket");
addstring(&tr2, "rob");

Author used 2 structure possibly because it makes the things more modular and manageable and ease the dynamic allocation.

Visualization

 +--------+
 |  tr2   |    trie_t
 +---+----+
     |
   +-+-+
   | r |       trie_node_t
   +-+-+
     |
   +-+-+
   | o |       trie_node_t
   +-+-+
    / \
   /   \
+-+-+ +-+-+
| b*| | c |    both trie_node_t
+---+ +-+-+
        |
      +-+-+
      | k*|    trie_node_t
      +-+-+
        |
      +-+-+
      | e |    trie_node_t
      +-+-+
        |
      +-+-+
      | t*|    trie_node_t
      +---+
(* means count is not zero)

Finally

Trie (or other data structure for example linked list) is just an idea, and implementation may vary.

For example a linked list may be implemented as an array (keeping index of next item as link and keeping a special number for last) or as node type and list type where list type contains pointer to head. Former implementation may be easy to understand, implement and debug, while later implementation exploits dynamic allocation better. An implementation may be good for one purpose while may not be as suitable for other purpose.

Upvotes: 4

Related Questions