1. 概述
本章的内容是单词查找树,即字符串查找树,它和一般的查找树有相似之处,但是由于字符串的特征,可以有更大的改进,但由于字符集是固定的,所以字符重复可以被我们利用起来。
我们可以基于字符为结点(隐性),构造一棵R向(字符集大小)的查找树。
2. R向单词查找树
2.1. 特征描述
这样的查找树它的构成的基本单元是一个结点Node,结点的内容很简洁如下:
1 | class Node // 在类中定义 |
vector<string> next
是一个大小为256+1的vector,引索代指字符,所以我们对字符串和字符的访问是隐性的,多出来的大小是为了方便引索。
对于这颗树,我们仍然给出了插入,查找,删除的基本操作,以及新添加的操作:寻找前缀匹配的字符串,寻找模式符合的字符串,寻找最长给定的字符串的子字符串(在树中的)。
2.2. 查找
查找算法基本思路是根据查找深度d作为阶段判断,从不含内容的根节点开始,搜索结点的next数组(我们后续将vector可以称呼为数组)里第’c’个结点(’c’是我们的待查找字符串的第d个字符,因为有根节点存在,我们呢的d实际是超前一个的,也就是说,一个过程中的d是下一次过程的对象)。长度达到键的长度或者达到空结点就会结束。
1 | val* get(string s) |
2.3.插入
思路相似
1 | void put(string s, val value) |
2.4. 删除
删除只需要找到待删除键(字符串)的末尾,将其值的指针设为空指针。如果没找到,会返回空指针,如果删除后,当前结点的next数组全是空指针,就删除之,如此递归。
1 | void Delete(string key) |
2.5. 寻找前缀匹配的字符串
意思是寻找树中有子字符串prefix的键,我们首先可以先用私有的get方法,找到prefix末尾的结点,那么我们只需要把从这里开始的所有键存入即可。
1 | vector<string> KeysWithPrefix(string pre) |
2.6. 寻找模式符合的字符串
同样是一层层搜索,当长度达到模式长度就添加。我们对字符串中的”.”认为是任意字符的匹配。
1 | vector<string> KeysWithMatch(string pat) |
2.7. 寻找最长给定的字符串的子字符串(在树中的)
根据要寻找的子字符,搜索,当长度达到后,值非空就返回长度,当出现空结点也返回长度。然后根据长度选择子字符串。
1 | string LongestPrefixOf(string s) |
2.8. R向单词查找树的性质
1.这种单词查找树的链表结构和插入删除顺序无关。
2.在单词查找树中查找一个键或是插入一个键,访问数组最多次数为键的长度加一。
3.字母表大小为R,在一颗有N个随机键构造的R向单词查找树中,未命中查找平均所需检查的结点数量为~$\log_R{N}$。
4.一颗单词查找树的链接总数在$RN$到$RNw$之间,其中$w$为键的平均长度。
3. 三向单词查找树
三向单词查找树和二叉搜索树很相似,一个结点内有显式的字符储存,也有左中右(小于,等于,大于)三个子链接。其代码我们这里就只实现查找和插入了。
1 | template<class val> |
3.1. 三向单词查找树的性质
1.$N$个平均长度为$w$的字符串构造的三向单词查找树的总链接树为$3N$到$3Nw$之间。
2.在一棵有$N$个随机字符串构造的三项单词查找树中,查找未命中平均需要比较字符~$\ln{N}$次,一次插入或者命中的查找会比较一次查找的键中的每个字符。