这个绳子的实现是如何正确的？

Question

我试图解决一个编程问题，这个问题涉及到很多插入到列表中的内容。然而，问题的具体情况与这个问题无关。

为了解决这个问题，我最终写了一种绳子数据结构，试图从我在互联网上找到的稀缺资源中拼凑一个实现。

最后我写了这个：

from dataclasses import dataclass
import typing as t

from hypothesis import given, strategies as st

T = t.TypeVar("T")


@dataclass
class Branch(t.Generic[T]):
    weight: int
    left: t.Union[t.List[T], "Branch[T]"]
    right: t.Union[t.List[T], "Branch[T]"]


Rope = t.Union[t.List[T], Branch[T]]


def insert(rope: Rope, index: int, item: T) -> Rope:
    if isinstance(rope, list):  # leaf
        if index == len(rope):  # at the end, just append
            rope.append(item)
            return rope

        # split
        left, right = rope[:index], [item, *rope[index:]]
        return Branch(len(left), left, right)
    else:  # branch
        if rope.right and rope.weight <= index:
            rope.right = insert(rope.right, index - rope.weight, item)
        else:
            rope.weight += 1
            rope.left = insert(rope.left, index, item)

        return rope


def straighten(rope: Rope) -> t.Iterator[T]:
    if isinstance(rope, list):
        yield from rope
    else:
        yield from straighten(rope.left)
        yield from straighten(rope.right)


@st.composite
def instructions(draw, elements=st.integers(0, 255)):
    items = draw(st.lists(elements, min_size=1))
    result = []
    for i, item in enumerate(items):
        insertion_point = draw(st.integers(min_value=0, max_value=i))
        result.append((insertion_point, item))
    return result


@given(instructions())
def test_correctness(seq: t.List[t.Tuple[int, int]]) -> None:
    manual: t.List[int] = []
    for (i, item) in seq:
        manual.insert(i, item)

    rope: Rope = []
    for (i, item) in seq:
        rope = insert(rope, i, item)

    assert manual == list(
        straighten(rope)
    ), f"{manual!r} != {rope!r} => {list(straighten(rope))!r}"


if __name__ == "__main__":
    test_correctness()
    print("All good")

如您所见，代码通过了假设，因此，它解决了这个问题。

然而，我无法理解为什么我编写的这段代码是正确的，因为试图仅仅使用分支和叶子来重写它(也就是说，不使用列表)会产生不正确的实现：

from dataclasses import dataclass
import typing as t

from hypothesis import given, strategies as st

T = t.TypeVar("T")


@dataclass
class Branch(t.Generic[T]):
    weight: int
    left: t.Union[T, "Branch[T]"]
    right: t.Union[T, "Branch[T]"]


Rope = t.Union[T, Branch[T]]


def insert(rope: Rope, index: int, item: T) -> Rope:
    if isinstance(rope, Branch):  # leaf
        if rope.right and rope.weight <= index:
            rope.right = insert(rope.right, index - rope.weight, item)
        else:
            rope.weight += 1
            rope.left = insert(rope.left, index, item)

        return rope

    if index == 0:
        left, right = item, rope
    else:
        left, right = rope, item

    return Branch(1, left, right)


def straighten(rope: Rope) -> t.Iterator[T]:
    if isinstance(rope, Branch):
        yield from straighten(rope.left)
        yield from straighten(rope.right)
    else:
        yield rope


@st.composite
def instructions(draw, elements=st.integers(0, 255)):
    items = draw(st.lists(elements, min_size=1))
    result = []
    for i, item in enumerate(items):
        insertion_point = draw(st.integers(min_value=0, max_value=i))
        result.append((insertion_point, item))
    return result


@given(instructions())
def test_correctness(seq: t.List[t.Tuple[int, int]]) -> None:
    it = iter(seq)
    _, head = next(it)

    rope: Rope = head
    manual = [head]
    for (i, item) in it:
        manual.insert(i, item)
        rope = insert(rope, i, item)

        straight_rope: t.List[int] = list(straighten(rope))
        assert manual == straight_rope, f"{manual!r} != {straight_rope!r} ({rope!r})"


if __name__ == "__main__":
    test_correctness()
    print("All good")

因此，我希望任何对这一数据结构有更深入了解的人能告诉我这两种实现之间的区别，以及为什么其中一种实现工作，而另一种则不工作。

Answer 1

您的代码失败，因为在if rope.right and rope.weight <= index:中，条件在rope.right == 0时计算为False。在第二段代码中，当正确的节点是值为0的叶子，并将导致将值插入错误的子树时，就会发生这种情况。

根本没有理由检查rope.right，所以这个检查应该是if rope.weight <= index:。

在两个rope实现中还有另一个潜在的问题:您正在变异节点，而rope实现通常将节点视为不可变的，并创建新的节点来进行任何更改。这不会影响您的测试，因为您一次只有一个绳子实例。例如，它会引起问题：

r = create_some_rope()
r2 = r
r = insert(r, idx, val)
# now r2 may or may not have changed, depending on its structure.

如果您曾经添加过绳子连接，也会引起问题。在这种情况下，如果将一条绳子连接到自己(或其本身的一个子树)，那么任何进一步的操作都可能无意中影响到绳子的多个部分。