Trie Trees practice
It's my first attempt writing a trie tree. I read the wikipedia page and tried to understand it, the image on stuck to my mind and I tried to code it from my understanding of it.
After much time spent, I figured I didn't know enough and I searched online for more information. It turns out this image is more like a radix tree, which is a specific type of trie tree, where intermediate substrings can be grouped. I decided to back up a little and went back to basics to focus on just getting the trie tree right first before moving on to a radix tree implementation (in future).
As a small challenge, I tried to code the bitwise implementation instead of character implemention. The code below is what I came up with. It turns out to be easier than expected to code, since basic trie trees create a node for every element (be it a char or a bit) in a string.
At first, I assumed encoding a bit string had to be done from the Most Significant Bit (MSB) to Least Significant Bit (LSB), meaning more significant bits would appear higher in the Trie Tree. However, after much thought, I coded the structure to go from LSB to MSB, and the resultant tree seems to be more elegantly formed than if it were to be MSB to LSB.
While researching trie trees, I also learnt a lot about:
Deterministic acyclic finite state automaton (DAFSA), where basically child nodes can combine thus saving space but not allowing auxillary information to be stored.
Radix trees, where the nodes in a trie trees and be condensed, saving space, but adding more complexity to the insertion and deletion algorithms.
_BitScanReverse and other compiler Intrinsic functions, it's the first time I encountered these, specifically, there are fast low level functions to do various operations like count the leading zeros in an unsigned long.
#include <intrin.h> #include using namespace std; #pragma intrinsic(_BitScanReverse) typedef char int8_t; class TrieNode { public: TrieNode* children[2]; bool value; void* leafObject; private: int getIndex(int8_t val, int startIndex=0) { unsigned long index = 0; unsigned char isNonZero; if(startIndex > 0) { int8_t mask = (0xFF >> startIndex); val = val & mask; } isNonZero = _BitScanForward(&index, val); return index; } public: explicit TrieNode(bool value_) : value(value_) , leafObject(nullptr) { children[0] = nullptr; children[1] = nullptr; } virtual ~TrieNode() { for(int i=0; i <2; i++) { if(children[i] != nullptr) { delete children[i]; children[i] = nullptr; } } } bool hasChildren() { return (children[0] || children[1]); } bool isLeaf() { return leafObject != nullptr; } }; class TrieTree { public: TrieNode* root; static const int maskOne = 0x1; TrieTree() : root(new TrieNode(false)) { } void* find(int8_t key) { TrieNode* currNode = root; TrieNode* nextNode = currNode->children[ (key & maskOne) ]; while(nextNode != nullptr) { currNode = nextNode; key = key >> 1; nextNode = currNode->children[ (key & maskOne) ]; } if(currNode->isLeaf() && key == 0) return currNode->leafObject; else return nullptr; // not found } void insert(int8_t key, void* value) { if(value == nullptr) return; insert(root, key, value); } void remove(int8_t key) { remove(root, key); } void print() { printf("\n\ntree"); print(root, 0); } private: TrieNode* insert(TrieNode* node, int8_t key, void* value) { unsigned long index = 0; unsigned char isNonZero = _BitScanReverse(&index, key); // if end of string if(isNonZero == 0) { // node will become a leaf node->leafObject = value; return node; } else { // we still have more significant bits int nodeIndex = (key & maskOne); TrieNode* childNode = node->children[ nodeIndex ]; if(childNode == nullptr) { childNode = new TrieNode(static_cast(nodeIndex)); node->children[ nodeIndex ] = childNode; } return insert(childNode, key>>1, value); } }//end insert // returns true if we want to delete the child node that we recursed to bool remove(TrieNode* node, int8_t key) { unsigned long index = 0; unsigned char isNonZero = _BitScanReverse(&index, key); // if end of string if(isNonZero == 0) { // double check if node is a leaf if(node->isLeaf()) { node->leafObject = nullptr; return true; } } else { // we still have more significant bits int nodeIndex = (key & maskOne); TrieNode* childNode = node->children[ nodeIndex ]; if(childNode == nullptr) { // nothing to delete return false; } else { if(remove(childNode, key>>1)) { delete childNode; node->children[nodeIndex] = nullptr; // check if we should remove self since child node doesn't exist anymore return (!node->hasChildren()); } // else do nothing } } }//end remove void print(TrieNode* node, int depth) { if(node == nullptr) return; printf("\n|"); for(int i=0; i<depth; i++) { printf("-"); } if(node->isLeaf()) printf("%d leaf:%s", node->value, node->leafObject ); else printf("%d", node->value); print(node->children[0], depth+1); print(node->children[1], depth+1); } };
