简介
Trie是一种特殊的树，可用于
1 存储英语单词(如下图所示)
2 hash table的替代品，优点如下
1 Looking up values typically have a better worst-case time complexity.
2 Unlike a hash table, a Trie does not need to worry about key collisions.
3 Doesn’t require a hashing algorithm to guarantee a unique path to elements.
4 Trie structures can be alphabetically ordered.
当用于存储英语单词死，下图展示了Trie的结构
这个Trie包含“Cat”，“Cut”，“Cute”，“To”，“B”五个单词
示例
/**
TrieNode存储一个字符
*/
@interface TrieNode : NSObject
@property(nonatomic, copy) NSString *value;
//用来标识一个单词的结束(如果只添加了cute,则cut是不应该在单词库里面)
@property(nonatomic, assign) BOOL isTerminating;
@property(nonatomic, weak) TrieNode *parent;
@property(nonatomic, strong, readonly) NSMutableDictionary *children;
- (instancetype)initWithValue:(NSString *)value
parent:(TrieNode *)parent;
- (void)addChild:(NSString *)child;
@end
@interface TrieNode ()
@property(nonatomic, strong, readwrite) NSMutableDictionary *children;
@end
@implementation TrieNode
- (instancetype)initWithValue:(NSString *)value parent:(TrieNode *)parent
{
if (self = [super init]) {
_value = [value copy];
_parent = parent;
}
return self;
}
- (void)addChild:(NSString *)child
{
if (!self.children) {
self.children = [NSMutableDictionary new];
}
//一个节点下不能有2个一样的节点，避免重复
if ([[self.children allKeys] containsObject:child]) {
return;
}
TrieNode *node = [[TrieNode alloc] initWithValue:child parent:self];
[self.children setObject:node forKey:child];
}
@end
/**
管理所有单词
*/
@interface Trie : NSObject
//插入一个单词
- (void)insert:(NSString *)word;
//是否包含一个单词
- (BOOL)contains:(NSString *)word;
//删除一个单词
- (void)remove:(NSString *)word;
@end
@interface Trie ()
@property(nonatomic, strong) TrieNode *root;
@end
@implementation Trie
- (instancetype)init
{
if (self = [super init]) {
_root = [[TrieNode alloc] init];
}
return self;
}
- (void)insert:(NSString *)word
{
if (word.length == 0) {
return;
}
TrieNode *currentNode = _root;
NSMutableArray *words = [NSMutableArray new];
NSString *lowerWorld = [word lowercaseString];
for (NSInteger i = 0; i < lowerWorld.length; i++) {
[words addObject:[lowerWorld substringWithRange:NSMakeRange(i, 1)]];
}
NSInteger currentIndex = 0;
while (currentIndex < words.count) {
NSString *ch = words[currentIndex];
TrieNode *node = [currentNode.children objectForKey:ch];
if (node) {
currentNode = node;
} else {
[currentNode addChild:ch];
currentNode = [currentNode.children objectForKey:ch];
}
currentIndex += 1;
if (currentIndex == words.count) {
currentNode.isTerminating = YES;
}
}
}
- (BOOL)contains:(NSString *)word
{
if (word.length == 0) {
return NO;
}
TrieNode *currentNode = _root;
NSMutableArray *words = [NSMutableArray new];
NSString *lowerWorld = [word lowercaseString];
for (NSInteger i = 0; i < lowerWorld.length; i++) {
[words addObject:[lowerWorld substringWithRange:NSMakeRange(i, 1)]];
}
NSInteger currentIndex = 0;
while (currentIndex < words.count) {
TrieNode *node = [currentNode.children objectForKey:words[currentIndex]];
if (node) {
currentIndex += 1;
currentNode = node;
} else {
break;
}
}
if (currentIndex == words.count && currentNode.isTerminating) {
return YES;
}
return NO;
}
- (void)remove:(NSString *)word
{
if (![self contains:word]) {
return;
}
TrieNode *currentNode = _root;
NSMutableArray *words = [NSMutableArray new];
NSString *lowerWorld = [word lowercaseString];
for (NSInteger i = 0; i < lowerWorld.length; i++) {
[words addObject:[lowerWorld substringWithRange:NSMakeRange(i, 1)]];
}
NSInteger currentIndex = 0;
while (currentIndex < words.count) {
TrieNode *node = [currentNode.children objectForKey:words[currentIndex]];
if (node) {
currentIndex += 1;
currentNode = node;
} else {
break;
}
}
//此时的currentNode为单词最后一个字符所在的节点
//情形1和2可以参考下面的配图
/*
1 如果这个节点还有子节点，将这个节点的isTerminating属性设置为NO
例如"cute"和"cut"同时存在，删除"cut"，只要设置"t"对应节点的isTerminating=NO即可
*/
if (currentNode.children != nil) {
currentNode.isTerminating = NO;
} else {
/*
2 这个节点是叶子，那么删除这个节点，判断上一个节点
2.1 如果上一个节点的isTerminating=YES或者children的key数量>=2，不删除上一个节点，跳出循环
2.2 否则，删除上一个节点，并继续判断上一个节点的上一个节点
*/
while (currentNode) {
TrieNode *parentNode = currentNode.parent;
currentNode.parent = nil;
NSString *key = currentNode.value;
currentNode = parentNode;
if (parentNode) {
[parentNode.children removeObjectForKey:key];
if (parentNode.isTerminating || parentNode.children.allKeys.count > 0) {
break;
}
}
}
}
}
@end
删除方法对应的情形
