三叉搜索树

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

三叉搜索树
类型	tree
用大O符号表示的时间复杂度 算法 平均 最差 搜索 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 插入 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 删除 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 用大O符号表示的空间复杂度

描述

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