为什么 Patricia 会尝试在某些节点中建立反向链接，其背后的逻辑是什么？

Question

我正在尝试实现我自己的 Patricia Trie 库以用于学习目的，所以我在添加一些节点时卡住了，因为我得到的每个示例都有这些奇怪的向后链接，这对我来说毫无意义。这些链接有什么意义？这背后的逻辑是什么？

我看过很多视频、论文（包括 Edward Fredkin 的原始论文）、书籍（Drozdek、Chapman、Cormen 等人）和演示文稿，但我还是一无所知。

这是我做的插入例程，忽略最后的评论，我试图自学，但惨遭失败。

    public void insert(int value) {
        int numOfBits = (int) (Math.log(value) / Math.log(2)) + 1;
        if (numOfBits > MaxBits) {
            System.out.println("Error : Number too large");
            return;
        }

        root = insert(this.root, value);
    }



    private PatriciaNode insert(PatriciaNode node, int value) {

        int differingBitNumber;
        String binaryValue, binaryLastNodeValue;
        PatriciaNode newNodeGrandma, newNodeParent, lastNode, newNode;

        // Tree is empty create the first item
        if (node == null) {
            node = new PatriciaNode();

            node.bitNumber = 0;
            node.data = value;
            node.leftChild = node;
            node.rightChild = null;

            return node;
        }

        // Checks if there is already a node with this value
        lastNode = search(node, value);
        if (value == lastNode.data) {
            System.out.println("Error : key is already present\n");
            return node;
        }

        // There is no value like this stored!!!
        // translate values in to the binary
        // representations for comparisons
        binaryValue = toBinary(value);
        binaryLastNodeValue = toBinary(lastNode.data);

        // find the first differing bit beetween the binary representations
        differingBitNumber = 1;
        while (isBit1At(binaryValue, differingBitNumber) == isBit1At(binaryLastNodeValue, differingBitNumber)) {
            differingBitNumber++;
        }

        // going down in the tree in order to find a spot to insert the new node
        newNodeParent = node;
        newNodeGrandma = node.leftChild; // I known it makes no sense, but after the loop will
        while (newNodeGrandma.bitNumber > newNodeParent.bitNumber && newNodeGrandma.bitNumber < differingBitNumber) {
            newNodeParent = newNodeGrandma;

            // deciding if we should go to the left or to ther right
            // bit 1 to right, bit 0 to left
            newNodeGrandma = isBit1At(binaryValue, newNodeGrandma.bitNumber) ? newNodeGrandma.rightChild : newNodeGrandma.leftChild;
        }

        // spot has been found!!
        // creating the node
        newNode = new PatriciaNode();
        newNode.bitNumber = differingBitNumber;
        newNode.data = value;

        // Doing some circular references, it will be used when we search at tree
        // when bitNumberCurrent < bitnumberParent we known we reach the bottom of
        // the tree

        // my grandma is less than me? Put it on the left otherwise put it on the right
        newNode.leftChild = isBit1At(binaryValue, differingBitNumber) ? newNodeGrandma : newNode;

        // my grandma is bigger than me? Put it on right otherwise put it on the left
        newNode.rightChild = isBit1At(binaryValue, differingBitNumber) ? newNode : newNodeGrandma;

        // when using patricia trees the children points
        // backwards to grandmas informing if its grandmas
        // has bigger or lowers values, when a node has
        // a child it must "forget" about your own grandmas
        // and points to your new children
        if (newNodeGrandma == newNodeParent.leftChild) {
            newNodeParent.leftChild = newNode;
        } else {
            newNodeParent.rightChild = newNode;
        }

        return node;
    }

所以代码似乎可以工作，但我不明白为什么以及如何工作。

Answer 1

Patricia 尝试将内部（分支）和终端（叶）节点合并为一种节点类型。终端节点由不晚于其父节点的要比较的位指示，即它们是向上链接或自链接。阅读这些尝试的图形的明智方法是跟踪链接（仅使用位和子字段），直到您遇到一个比较不是后继位的节点。这是您比较完整密钥的终端节点。形象地说，上行链接指向终端节点，下行链接指向内部节点，任何一个特定的节点都扮演这两个角色。

空树没有节点。一棵只有一个项目的树有一个根，但没有位可以比较，因为没有其他值。因此，如果您在大端树中有字节值在位 {7..0} 上进行比较，那么根节点将被初始化以比较位 8，由于它是最大位 7 左侧的 1，因此是所有值都相同，即没有什么可比较的。因此，让我们采用一棵具有单个根节点 0x00 的树，假设第 8 位等于前导零。然后 left(0) child 指向 root 并且 right 可以保持未定义或 null 因为它永远不会被使用，因为第 8 位只是一个前导零，表示没有要比较的位并且永远不会是 1，因为一个字节没有第 8 位.

现在窃取 root 的 left(0) 字段并将其指向值为 0x40 (64) 的子项。该字节与第 6 位上的 0x00（根）不同。因此它标记第 6 位并且右（1）子节点指向自身，而左（0）子节点指向根 0x00。

“帕特里夏有点狡猾，需要仔细检查才能发现她所有的美。” -唐纳德·高德纳

Sedgwick 的“Algorithms in C”第一版中对此结构的最好描述。他为一个大的结束 int 树实现了插入。你会注意到他使用的值都以零开头，即前导 0（实际上意味着没有位可以比较）是明确的。只要记住这两条规则：根确实包含一个值（它不是空根）。只有一条远离根的路径被使用，这直接表示在树中至少有两个节点之前没有什么可比较的。

为什么 Patricia 会尝试在某些节点中建立反向链接，其背后的逻辑是什么？

Why Patricia tries has that backwards links in some nodes and what's the logic behing it?

patricia-trie