三向单词查找树 -- C++实现


使用R向单词查找树会消耗大量的内存空间,而三向单词查找树则没有这个问题(但查找效率没有R向查找树快)

简单做了个测试,定义了2000个随机字符串(字符串最大长度不超过20)

分别使用R向单词查找和三向单词查找树加载这些字符串,三向单词查找树只用了820kb,而R向单词查找树则用了84M

测试代码

//main.cpp
#include "Component.h"
using namespace jay;

int main(int argc, char* argv[])
{
	TST t1;
	t1.put("mzk");
	t1.put("mka");
	t1.put("mds");
	t1.put("qlk");
	t1.put("11313");
	t1.put("4abc");
	t1.put("5abc");
	t1.put("6abc");
	t1.put("7abc");
	t1.put("8abc");
	t1.put("9qabc");
	t1.put("1abc");
	t1.put("2abc");
	t1.put("3abc");
	t1.put("hello");
	t1.put("he");
	t1.put("CPY");
	t1.put("CAT");
	t1.put("CMP");
	t1.put("he11111111");
	t1.put("hexxx");
	t1.put("1he");
	t1.put("hahhe");
	t1.put("y");
	t1.put("he");
	t1.put("hexxx1");
	t1.put("Hexxx1");
	t1.put("hExxx1");
	t1.put("hexxx2");
	t1.put("hexxxdxfg");

	cout << "mka is Contain? " << t1.isContain("mka") <<endl;
	cout << "1abc is Contain? " << t1.isContain("1abc") <<endl;
	cout << "hexxx1 is Contain? " << t1.isContain("hexxx1") <<endl;
	cout << "hexx is Contain? " << t1.isContain("hexx") <<endl;
	cout << "y is Contain? " << t1.isContain("y") <<endl;
	cout << "he111x11111 is Contain? " << t1.isContain("he111x11111") <<endl;


	vector<string> vectorC;
	string str("he");
	t1.keysWithPrefix(str,vectorC);

	for (int i=0;i<vectorC.size();i++)
	{
		cout << vectorC[i] << endl;
	}
}

测试结果

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。