如何使用Objective-C构建Trie数据结构？

Question

尽管Objective-C是C语言的超集，但我希望获得关于如何使用Objective-C创建Trie数据结构的反馈。我已经开始编写接口，但需要一些帮助来理解如何添加Trie节点（例如集合项）以存储单词。

@interface Trie : NSMutableArray {
   Trie *child;
   BOOL final;
}

@property(nonatomic, retain)Trie *child;
@property(nonatomic, assign)BOOL final;

-(void)addWord:(NSString *)_word;

@end

- Wayne Bishop

Answer 1

我为您编写了一个快速的实现，它应该是更加有效的，至少可以作为起点。请注意，我取消了数组子类。通常不建议子类化NSArrays，在这里您可以避免子类化。 请参阅继承与组合。

@interface Trie : NSObject

@property (nonatomic, strong) NSMutableArray *children;
@property (nonatomic, strong) NSString *key;
@property (nonatomic, readonly) BOOL isFinal;

- (void) addWord:(NSString *)word;
- (id) initWithKey:(NSString *)key;

@end

@implementation Trie

// designated initializer, initializes our array of children and sets the key
- (id) initWithKey:(NSString *)key
{
    if(self = [super init])
    {
        _key = key;
        _children = [NSMutableArray new];
    }
    return self;
}

- (void) addWord:(NSString *)word
{
    // no more characters left, this is our base case
    if(! word.length)
    {
       return;
    }

    Trie *childToUse;
    NSString *firstCharacter = [word substringToIndex:1];

    // look for an existing node to dive into
    for(Trie *child in _children)
    {
        if([child.key isEqualToString:firstCharacter])
        {
            childToUse = child;
            break;
        }
    }

    // create a new node if there isn't one
    if(! childToUse)
    {
        childToUse = [[Trie alloc] initWithKey:firstCharacter];
        [_children addObject:childToUse];
    }

    // we now have a node, add the rest of the word into our trie recursively
    [childToUse addWord:[word substringFromIndex:1]];
}

// no actual ivar is stored for this property, its value is returned dynamically by looking at the array count, which can change when more elements are added
- (BOOL) isFinal
{
    if(! _children.count)
    {
        return YES;
    }
    else
    {
        return NO;
    }
}

@end

只需通过类似 [[Trie alloc] initWithKey:@""] 的方式初始化根节点即可。

- Dima

---

非常感谢@Dima，看起来很棒！我会在Xcode中尝试一下，并且如果有任何问题，我会告诉你的。 - Wayne Bishop

当然！我还添加了一个基本情况，这是我之前忘记做的。如果没有这个，当你添加完整个单词后，你会遇到一个 NSRangeException 异常。 - Dima

嗨@Dima，在你的例子中，“key”是如何使用的？这是将与每个节点关联的实际字符吗？为什么我们不将键信息存储在NSMutableArray中？ - Wayne Bishop

每个节点存储自己的键，每个键实际上只是一个单字符。数组是子节点列表，每个子节点都有自己的键。如果您希望存储每个节点表示的完整字符串或任何其他数据，可以进行修改，这基本上是任意的。这样清楚吗？ - Dima

嗨@Dima，非常感谢，这对我来说是一个很好的起点。只有一个问题-为什么需要使用一个键来初始化Trie，并在此行中再次设置键：childToUse.key = firstCharacter;？再次感谢。 - goldengil

@goldengil 感谢你的指正！第二个 setter 调用完全不必要。我想在提交之前已经重构了这个解决方案，但忘记清除那一部分了。我现在会去做这件事。 - Dima

Answer 2

根据 @Dima 的解决方案，这里是一个现代化的版本，它使用了数组类型描述符，基于块的枚举，使得 children 从 Trie 类外部不可变，对于叶节点惰性地初始化 children 以节省空间，并移除了一个不必要的成员变量。

Trie.h:

@interface Trie : NSObject

@property (nonatomic, strong, readonly) NSMutableArray <Trie *>*children;
@property (nonatomic, strong) NSString *key;

- (id)initWithKey:(NSString *)key;
- (void)addWord:(NSString *)word;
- (BOOL)isLeaf;

@end

Trie.m:

@interface Trie ()

@property (nonatomic, strong, readwrite) NSMutableArray <Trie *>*children;

@end

@implementation Trie

- (id)initWithKey:(NSString *)key
{
    if (self = [super init]) {
        _key = key;
    }

    return self;
}

- (void)addWord:(NSString *)word
{
    if (word.length == 0) {
        return;
    }

    if (!self.children) {
        self.children = [NSMutableArray new];
    }

    NSString *firstCharacter = [word substringToIndex:1];
    __block Trie *childToUse = nil;
    [self.children enumerateObjectsUsingBlock:^(Trie *child, NSUInteger idx, BOOL *stop) {
        if ([child.key isEqualToString:firstCharacter]) {
            childToUse = child;
            *stop = YES;
        }
    }];

    if (!childToUse) {
        childToUse = [[Trie alloc] initWithKey:firstCharacter];
        [self.children addObject:childToUse];
    }

    [childToUse addWord:[word substringFromIndex:1]];
}

- (BOOL)isLeaf
{
    return self.children.count == 0;
}

@end

- awolf