Trie

trie.cpp

struct TrieNode {
	int minVal;
	TrieNode *child[2];
	TrieNode() {
		minVal = inf;
		child[0] = child[1] = NULL;
	}
};

struct Trie {
	TrieNode *root;

	void insert(int val) {
		int bits[maxd], v = val;
		for (int i = 0; i < maxd; i++) {
			bits[maxd - 1 - i] = (v & 1);
			v >>= 1;
		}
		if (root == NULL) root = new TrieNode();
		TrieNode *fa = root, *cur = NULL;
		for (int i = 0; i < maxd; i++) {
			if (fa->child[bits[i]] == NULL) {
				fa->child[bits[i]] = new TrieNode();
			}
			cur = fa->child[bits[i]];
			cur->minVal = std::min(cur->minVal, val);
			fa = cur;
		}
	}

	void deleteTrie(TrieNode *cur) {
		if (cur == NULL) return;
		deleteTrie(cur->child[0]);
		deleteTrie(cur->child[1]);
		delete cur;
	}

} trie;