键树查找法

---

定义：

一棵度大于等于2的树，树中的每个结点中只含有组成关键字的符号。

• 例如，若关键字是数值，则结点中只包含一个数位；若关键字是单词，则结点中只包含一个字母字符。

---

特点：

为了查找和插入方便，我们约定键树是有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定$小于任何字符。

键树中每个结点的最大度d和关键字的“基”有关，若关键字是单词，则d=27，若关键字是数值，则d=11。

键树的深度h：取决于关键字中字符或数位的个数。

image.png