Trie樹

• • • 作用
    • 存儲圖解
    • 查找圖解
    • 代碼實現(xiàn)
    • 習(xí)題

創(chuàng)新互聯(lián)是一家專業(yè)提供衡陽縣企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、HTML5、小程序制作等業(yè)務(wù)。10年已為衡陽縣眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進行中。作用

用來高效快速存儲和查找字符串集合的一種數(shù)據(jù)結(jié)構(gòu)

存儲圖解

假設(shè)有若干個字符串

先創(chuàng)建了一個根結(jié)點root，代指字符串集合的開頭，對第一個字符串a(chǎn)bcdef存儲就如上圖所示

當(dāng)存儲abdef時，一直走到b都和abcdef相同，于是在b點另開一個分支存儲之后的def

當(dāng)存儲aced時，一直走到a都和abcdef相同，于是在a點另開一個分支存儲之后的ced

以此類推

…

我們就得到能夠以樹的形式存儲一個字符串集合

并且在每個字符串的結(jié)尾的字母都標(biāo)記一下，表示以該字母結(jié)尾的節(jié)點是存在一個字符串的

如果有類似abc這樣的字符串，也要在c點標(biāo)記一下

查找圖解

如果要查找一個不存在的字符串，比如abcf

沿著樹枝一直走，走到c之后發(fā)現(xiàn)沒有f對應(yīng)的路徑，那么就說明該字符串不存在

或者查找一個字符串，該字符串在存儲里的字符串不存在，但屬于某個存儲的字符串的前綴

比如abcdef中的abc作為要查找的字符串

沿著樹枝走，發(fā)現(xiàn)c點沒有標(biāo)記，即使有對應(yīng)對應(yīng)路徑也不能說明該字符串存在

代碼實現(xiàn)

#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;

const int N = 100010;

int son[N][26];//代表每個節(jié)點可以有26個子節(jié)點
int cnt[N];//以當(dāng)前這個點結(jié)尾的字符串有多少個
int idx;//操作次數(shù)，當(dāng)前用到了哪個下標(biāo)
//下標(biāo)是0的點，既是根節(jié)點，也是空節(jié)點
char str[N];

void insert(char str[])//插入新字符串
{int p = 0;//根節(jié)點
	for (int i = 0;str[i];i++)
	{int u = str[i] - 'a';//存儲編號，字母a-'a'就變成了0，b就變成了1
		//如果說該節(jié)點之后沒有這個字母，即son[p][u] == 0
		if (!son[p][u]) son[p][u] = ++idx;//把這個節(jié)點加進去
		p = son[p][u];
	}

	cnt[p]++;//表示以該點結(jié)尾的數(shù)量又多了一個	
}

int query(char str[])//查詢字符串
{int p = 0;
	for (int i = 0;str[i];i++)
	{int u = str[i] - 'a';
		if (!son[p][u]) return 0;//如果不存在直接返回0
		p = son[p][u] ;
	}

	return cnt[p];//返回以該節(jié)點結(jié)尾的單詞數(shù)量
}
int main()
{int n;
	scanf("%d", &n);
	while (n--)
	{char op[2];//操作類型+空格
		scanf("%s%s", op,str);

		if (op[0] == 'I') insert(str);//插入操作
		else printf("%d\n", query(str));//查詢操作
	}

	return 0;
}

習(xí)題

暴力做法

利用兩重for循環(huán)來尋找大異或

//暴力法
	for (int i = 0;i< n;++i)
	{for (int j = 0; j< i;++j)
			res = max(res, (arr[i] ^ arr[j]));
	}

能被看作是trie樹的原因

因為運算方式是異或，而異或看的是二進制，如果兩個數(shù)的二進制某一位相同則為0，不同則為1

因此可以用31個長度的數(shù)組存儲兩個數(shù)的每一位

且對二進制從左往右看時，假設(shè)一個數(shù)為0，可以用trie樹查詢最高位為1的數(shù)，再找下一位為1的數(shù)，以此類推，便可以快速找出異或后的大數(shù)

因此，對某個數(shù)查詢能夠在存儲里的數(shù)尋找大異或時，可以從最高位依次查找每一位相異的數(shù)

實現(xiàn)代碼

#define _CRT_SECURE_NO_WARNINGS 1
#include#include 

using namespace std;

const int N = 100010;
const int M = N * 31;

int arr[N];
int son[M][2];
int idx;

void insert(int x)
{int p = 0;//尾節(jié)點
	for (int i = 30;i >= 0;--i)
	{int u = x >>i & 1;//得到該位
		if (!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
	}
}

int query(int x)
{int p = 0;
	int res = 0;
	for (int i = 30;i >= 0;i--)
	{int u = x >>i & 1;
		//如果該位相異的數(shù)存在
		if (son[p][!u])
		{	p = son[p][!u];
			res = res * 2 + !u;//相當(dāng)于把所有的位數(shù)進一再加上u
		}
		else
		{	p = son[p][u];
			res = res * 2 + u;
		}
	}

	return res;
}
int main()
{int n;
	scanf("%d", &n);

	for (int i = 0;i< n;++i) scanf("%d", &arr[i]);

	int res = 0; 

	for (int i = 0;i< n;++i)
	{insert(arr[i]);
		//先插入在查詢，防止第一次查詢不到的情況
		int t = query(arr[i]);

		res = max(res, (arr[i] ^ t));
	}
	printf("%d", res);
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：數(shù)據(jù)結(jié)構(gòu)：字典樹Trie-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://weahome.cn/article/doisce.html