三元搜索树

维基百科,自由的百科全书
跳转至: 导航搜索

在计算机科学中,三元搜索树是trie树前缀树的一种实现,树的各个节点之间的结构类似二叉搜索树。和其他的前缀树一样,三元搜索树可以用于实现带前缀搜索功能的关联数组。三元搜索数比标准的前缀树更节省空间,但是牺牲了部分查找速度。三元搜索树常用于实现拼写检查自动完成功能。

描述[编辑]

三元搜索树的每个节点存储了一个字符、一个值对象或值指针以及三个指向字节点的指针。这三个字节点常被称为等位字节点、低位字节点和高位字节点。