成员均为final的不可变Trie insertSorted方法仅能插入两元素求助

现有实现的核心问题 #

• 待插入字符小于当前节点字符的分支，返回的新节点没有将原当前节点挂到自身sibling上，直接截断了原有兄弟链表
• 待插入字符大于当前节点字符的分支，没有递归遍历原有sibling链路，遇到非空sibling时直接断链，同时未判断链路中是否已存在同字符节点
• 字符相等的分支逻辑写了自递归调用，没有按照要求判断重复就返回原链表

正确实现的核心逻辑 #

因为类中所有成员都是final修饰的不可变引用，本质需要按照持久化有序链表的规则实现插入：所有涉及引用变更的操作都不能修改原节点，而是通过逐层重建节点的方式，将原有属性值拷贝到新生成的节点上，最终靠递归返回值拼接出完整的有序链表，严格匹配方法定义的规则：

• 链表是按字符升序排列的
• 仅在不存在同字符边时插入新节点，存在同字符边时链表保持完全不变
• 最终返回整个兄弟链表的最左侧节点作为新的链表头

逻辑分支拆解 #

• 待插入字符 < 当前节点字符：新节点应放在当前节点之前，新节点的sibling直接挂载当前节点，返回新节点作为新的链表头
• 待插入字符 == 当前节点字符：已存在同标签的边，不做任何修改，直接返回当前节点本身
• 待插入字符 > 当前节点字符：
  • 若当前节点的sibling为null，说明已遍历到链表尾部，重建当前节点，将新节点作为自身的sibling
  • 若当前节点的sibling非空，递归调用sibling节点的insertSorted方法拿到插入完成后的子链表，重建当前节点，将自身的sibling替换为递归返回的新子链表

参考实现代码 #

public class TrieChildren extends AbstractTrieChildren {
    public TrieChildren(char character, AbstractTrie child, AbstractTrieChildren sibling) {
        super(character, child, sibling);
    }

    @Override
    public AbstractTrieChildren insertSorted(char character, AbstractTrie child) {
        // 待插入字符更小，前置插入
        if (character < this.character) {
            return new TrieChildren(character, child, this);
        }
        // 已存在同字符节点，直接返回原节点
        if (character == this.character) {
            return this;
        }
        // 链表尾部场景，直接挂新节点
        if (this.sibling == null) {
            return new TrieChildren(this.character, this.child, new TrieChildren(character, child, null));
        }
        // 递归处理子兄弟链路，重建当前节点
        AbstractTrieChildren updatedSibling = this.sibling.insertSorted(character, child);
        return new TrieChildren(this.character, this.child, updatedSibling);
    }
}

注意事项 #

• 全程不修改原对象的final成员引用，所有变更场景都通过新建对象完成属性拷贝
• 递归过程不需要额外的遍历游标，靠方法返回值即可自然拼接完整链路
• 重复插入同字符时，相等分支直接返回原对象引用，不会生成冗余节点

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