Trie is an efficient information retrieval data structure. Using trie, search complexities can be brought to optimal limit (key length). Using trie, we can search the key in O(M) time. However the penalty is on trie storage requirements.
struct trie_node{ int value; /* Used to mark leaf nodes */ trie_node_t *children[ALPHABET_SIZE];};void insert(trie_t *pTrie, char key[]){ int level; int length = strlen(key); int index; trie_node_t *pCrawl; pTrie->count++; pCrawl = pTrie->root; for( level = 0; level < length; level++ ) { index = CHAR_TO_INDEX(key[level]); if( !pCrawl->children[index] ) { pCrawl->children[index] = getNode(); } pCrawl = pCrawl->children[index]; } // mark last node as leaf pCrawl->value = pTrie->count;}// Returns non zero, if key presents in trieint search(trie_t *pTrie, char key[]){ int level; int length = strlen(key); int index; trie_node_t *pCrawl; pCrawl = pTrie->root; for( level = 0; level < length; level++ ) { index = CHAR_TO_INDEX(key[level]); if( !pCrawl->children[index] ) { return 0; } pCrawl = pCrawl->children[index]; } return (0 != pCrawl && pCrawl->value);}
During delete operation we delete the key in bottom up manner using recursion. The following are possible conditions when deleting key from trie,
- Key may not be there in trie. Delete operation should not modify trie.
- Key present as unique key (no part of key contains another key (prefix), nor the key itself is prefix of another key in trie). Delete all the nodes.
- Key is prefix key of another long key in trie. Unmark the leaf node.
- Key present in trie, having atleast one other key as prefix key. Delete nodes from end of key until first leaf node of longest prefix key.
bool deleteHelper(trie_node_t *pNode, char key[], int level, int len){ if( pNode ) { // Base case if( level == len ) { if( pNode->value ) { // Unmark leaf node pNode->value = 0; // If empty, node to be deleted if( isItFreeNode(pNode) ) { return true; } return false; } } else // Recursive case { int index = INDEX(key[level]); if( deleteHelper(pNode->children[index], key, level+1, len) ) { // last node marked, delete it FREE(pNode->children[index]); // recursively climb up, and delete eligible nodes return ( !leafNode(pNode) && isItFreeNode(pNode) ); } } } return false;}int isItFreeNode(trie_node_t *pNode){ int i; for(i = 0; i < ALPHABET_SIZE; i++) { if( pNode->children[i] ) return 0; } return 1;}
int leafNode(trie_node_t *pNode)
{
return (pNode->value != 0);
}
void deleteKey(trie_t *pTrie, char key[]){ int len = strlen(key); if( len > 0 ) { deleteHelper(pTrie->root, key, 0, len); }}
No comments:
Post a Comment