Posts

Showing posts from August, 2014

diffrence between char s[]="hello"; or char *s ="hello"

Trie |(Insert and Search )

Trie | (Insert and Search) Trie is an efficient information retrieval data structure. Using trie, search complexities can be brought to optimal limit (key length). If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. However the penalty is on trie storage requirements.
Every node of trie consists of multiple branches. Each branch represents a possible character of keys. We need to mark the last node of every key as leaf node. A trie node field value will be used to distinguish the node as leaf node (there are other uses of the value field). A simple structure to represent nodes of English alphabet can be as following,
structtrie_node { intvalue; /* Used to mark leaf nodes */ trie_node_t *children[ALPHABET_SIZE]; }; Inserting a key into trie is simple approach. Every character of input key is inserted as an individual trie n…