【数据结构】前缀树（字典树)汇总

基础

{“a”,“abc”,“bac”,“bbc”,“ca” }的字典树如下图：

最主用的应用：一，字符串编码。二，位运算。

字符串编码

相比利用哈希映射编码，优点如下：
依次查询长度为n的字符串s的前缀时间复杂度是O(n)。查询完s[0…i]，再查询s[0…i+1]的时间复杂度是O(1)。而哈希映射的时间复杂度是：O(nn)。
利用哈希映射编码的代码如下：
注意m_iLeafIndex 为-1，表示此节点不是任何字符串的结束字符。

class CStrToIndex
{
public:
	CStrToIndex() {

	}
	CStrToIndex(const vector<string>& wordList) {
		for (const auto& str : wordList)
		{
			Add(str);
		}
	}
	int Add(const string& str)
	{
		if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
		m_mIndexs[str] = m_strs.size();
		m_strs.push_back(str);
		return  m_strs.size()-1;
	}
	vector<string> m_strs;
	int GetIndex(const string& str)
	{
		if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
		return -1;
	}
protected:
	unordered_map<string, int> m_mIndexs;
};

利用字典树编码的代码如下：

template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:
	~CTrieNode()
	{
		for (auto& [tmp, ptr] : m_dataToChilds) {
			delete ptr;
		}
	}
	CTrieNode* AddChar(TData ele, int& iMaxID)
	{
#ifdef _DEBUG
		if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
		{
			return nullptr;
		}
#endif
		const int index = ele - cBegin;
		auto ptr = m_dataToChilds[ele - cBegin];
		if (!ptr)
		{
			m_dataToChilds[index] = new CTrieNode();
#ifdef _DEBUG
			m_dataToChilds[index]->m_iID = ++iMaxID;
			m_childForDebug[ele] = m_dataToChilds[index];
#endif
		}
		return m_dataToChilds[index];
	}
	CTrieNode* GetChild(TData ele)
	{
#ifdef _DEBUG
		if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
		{
			return nullptr;
		}
#endif
		return m_dataToChilds[ele - cBegin];
	}
protected:
#ifdef _DEBUG
	int m_iID = -1;
	std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:
	int m_iLeafIndex = -1;
protected:
	//CTrieNode* m_dataToChilds[iTypeNum] = { nullptr };//空间换时间 大约216字节
	//unordered_map<int, CTrieNode*>    m_dataToChilds;//时间换空间 大约56字节
	map<int, CTrieNode*>    m_dataToChilds;//时间换空间,空间略优于哈希映射，数量小于256时，时间也优。大约48字节
};
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:
	int GetLeadCount()
	{
		return m_iLeafCount;
	}
	CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par,TData curValue)
	{
		auto curNode =par->AddChar(curValue, m_iMaxID);
		FreshLeafIndex(curNode);
		return curNode;
	}
	template<class IT>
	int Add(IT begin, IT end)
	{
		auto pNode = &m_root;
		for (; begin != end; ++begin)
		{
			pNode = pNode->AddChar(*begin, m_iMaxID);
		}
		FreshLeafIndex(pNode);
		return pNode->m_iLeafIndex;
	}	
	template<class IT>
	CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end)
	{
		auto ptr = &m_root;
		for (; begin != end; ++begin)
		{
			ptr = ptr->GetChild(*begin);
			if (nullptr == ptr)
			{
				return nullptr;
			}
		}
		return ptr;
	}
	CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:
	void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode)
	{
		if (-1 == pNode->m_iLeafIndex)
		{
			pNode->m_iLeafIndex = m_iLeafCount++;
		}
	}
	int m_iMaxID = 0;
	int m_iLeafCount = 0;
};

二进制位运算（01前缀树)

比如求nums和x的xor最大值。
将nums放到01放到前缀树中。通过拆位法依次从高到低处理各位，如果x 此为1，则优先选择前缀树的0分支；如果x为0，则优先选择前缀树的1分支。

class C2BNumTrieNode
{
public:
	C2BNumTrieNode()
	{
		m_childs[0] = m_childs[1] = nullptr;
	}
	bool GetNot0Child(bool bFirstRight)
	{
		auto ptr = m_childs[bFirstRight];
		if (ptr && (ptr->m_iNum > 0))
		{
			return bFirstRight;
		}
		return !bFirstRight;
	}
	int m_iNum = 0;
	C2BNumTrieNode* m_childs[2];
};

template<class T = int, int iLeveCount = 31>
class C2BNumTrie
{
public:
	C2BNumTrie()
	{
		m_pRoot = new C2BNumTrieNode();
	}
	void  Add(T iNum)
	{
		m_setHas.emplace(iNum);
		C2BNumTrieNode* p = m_pRoot;
		for (int i = iLeveCount - 1; i >= 0; i--)
		{
			p->m_iNum++;
			bool bRight = iNum & ((T)1 << i);
			if (nullptr == p->m_childs[bRight])
			{
				p->m_childs[bRight] = new C2BNumTrieNode();
			}
			p = p->m_childs[bRight];
		}
		p->m_iNum++;
	}
	void Del(T iNum)
	{
		auto it = m_setHas.find(iNum);
		if (m_setHas.end() == it)
		{
			return;
		}
		m_setHas.erase(it);
		C2BNumTrieNode* p = m_pRoot;
		for (int i = iLeveCount - 1; i >= 0; i--)
		{
			p->m_iNum--;
			bool bRight = iNum & ((T)1 << i);
			p = p->m_childs[bRight];
		}
		p->m_iNum--;
	}	
	void Swap(C2BNumTrie<T, iLeveCount>& o) {
		swap(m_pRoot, o.m_pRoot);
		swap(m_setHas, o.m_setHas);
	}
	C2BNumTrieNode* m_pRoot;
	std::unordered_multiset<T> m_setHas;
};

template<class T = int, int iLeveCount = 31>
class CMaxXor2BTrie : public C2BNumTrie<T, iLeveCount>
{
public:
	T MaxXor(T iNum)
	{
		C2BNumTrieNode* p = C2BNumTrie<T, iLeveCount>::m_pRoot;
		T iRet = 0;
		for (int i = iLeveCount - 1; i >= 0; i--)
		{
			bool bRight = !(iNum & ((T)1 << i));
			bool bSel = p->GetNot0Child(bRight);
			p = p->m_childs[bSel];
			if (bSel == bRight)
			{
				iRet |= ((T)1 << i);
			}
		}
		return iRet;
	}
};

题解

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。