这个Patricia树实现是错误的吗？

Question

我正在阅读《算法》一书的章节基数搜索（Robert Sedgwick）。

我做了一个简单的实现，但有些东西没有按预期运行。

在程序

15.5

中，您可以看到我们从一棵空树开始，其中头是空节点。在图

15.12

中，您可以看到空节点始终是最左边的节点。这在文中也有描述：

我们使用的约定是最左边的链接（对应于全 0 位的键的链接）不指向任何内部节点

程序

15.7

是Patricia-trie插入的实现。

如果您查看代码，就会发现头引用永远不可能更改为

A

，如图

15.12

所示。

这是一个错误吗？

Answer 1

你读的是哪个版本，我有这本书（c语言的算法，也是由sedgewick写的）。我发现了与你所说的相同的错误代码。 首先：如果trie为空，我们首先插入一个项目（当然创建一个新节点，我们将其命名为x），我们应该使该节点成为trie的头。但是boke中的代码没有反映这一点。 第二：如果trie不为空，当我们插入一个节点（名为x）时，首先我们会找到一个与x最理智的位的节点，确定i（while（bit（v，i）== bit（w， i)) i++;) .如果 x 的头不同位为 0，则情况 1:head.l = insertR(head.l, x, i, head)，否则情况 2:head.r = insertR(head.r, x，i，头）；