三元搜索树是否适用于所有单词？子节点被占用时如何插入？

一、子节点被不同字符占用时的处理逻辑 #

三元搜索树的左、中、右子节点分工明确，不存在“插入字符找不到位置”的冲突情况：

• 左子节点：仅存放字典序小于当前节点字符的节点
• 中子节点：仅存放与当前节点字符匹配后，字符串下一个位置的字符节点
• 右子节点：仅存放字典序大于当前节点字符的节点

当三个子节点都被占用时，说明当前节点的左、右分支已经覆盖了比它小和大的字符范围，中分支则对应了以当前字符开头的后续字符串。此时插入新字符，依然严格按字典序递归处理：

• 新字符 < 当前节点字符：递归进入左子树，重复比较逻辑
• 新字符 > 当前节点字符：递归进入右子树，重复比较逻辑
• 新字符 == 当前节点字符：递归进入中子树，处理字符串的下一个字符

每个分支的字符范围互斥，只要遵循字典序规则，总能找到对应的插入位置。

二、根节点为'b'时插入'cecil'和'dock'的具体步骤 #

插入'cecil'（字符序列：c → e → c → i → l） #

• 根节点是'b'，第一个字符'c'比'b'大，根的右子节点为空，新建存'c'的节点作为根的右子节点，进入该'c'节点处理下一个字符'e'
• 当前节点是'c'，字符'e'比'c'大，'c'的右子节点为空，新建存'e'的节点作为'c'的右子节点，进入该'e'节点处理下一个字符'c'
• 当前节点是'e'，字符'c'比'e'小，'e'的左子节点为空，新建存'c'的节点作为'e'的左子节点，进入该'c'节点处理下一个字符'i'
• 当前节点是'c'，字符'i'比'c'大，'c'的右子节点为空，新建存'i'的节点作为'c'的右子节点，进入该'i'节点处理下一个字符'l'
• 当前节点是'i'，字符'l'比'i'大，'i'的右子节点为空，新建存'l'的节点作为'i'的右子节点，最后在'l'节点标记为字符串结束（表示这是一个完整单词的结尾）

插入'dock'（字符序列：d → o → c → k） #

• 根节点是'b'，第一个字符'd'比'b'大，进入根的右子节点'c'；'d'比'c'大，进入'c'的右子节点'e'；'d'比'e'小，'e'的左子节点为空，新建存'd'的节点作为'e'的左子节点，进入该'd'节点处理下一个字符'o'
• 当前节点是'd'，字符'o'比'd'大，'d'的右子节点为空，新建存'o'的节点作为'd'的右子节点，进入该'o'节点处理下一个字符'c'
• 当前节点是'o'，字符'c'比'o'小，'o'的左子节点为空，新建存'c'的节点作为'o'的左子节点，进入该'c'节点处理下一个字符'k'
• 当前节点是'c'，字符'k'比'c'大，'c'的右子节点为空，新建存'k'的节点作为'c'的右子节点，最后在'k'节点标记为字符串结束

内容的提问来源于stack exchange，提问作者FariyaAchhab