python - 交换从树移动指针中随机选择的两个节点的角色的算法

Question

我创建了一个算法，其目的应该是，给定 BST 中的两个节点 A 和 B，它通过简单地移动指针来切换两者的角色(或树中的位置)。在我对 BST 的表示中，我使用了双链接连接(即 A.parent == B 和(B.left == A)或(B.right == A))。我不确定它是否完全正确。我把算法分为两种情况。

1. A 和 B 直接相连(A 是 B 的父级或 B 是 A 的父级)

2. 所有其他情况

对于前面的每个案例，我都创建了一个嵌套函数。我想首先了解您对算法正确性的看法，如果我能以某种方式改进它。这是代码:

def switch(self, x: BSTNode, y: BSTNode, search_first=False):
    if not x:
        raise ValueError("x cannot be None.")
    if not y:
        raise ValueError("y cannot be None.")
    if x == y:
        raise ValueError("x cannot be equal to y")

    if search_first:
        if not self.search(x.key) or not self.search(y.key):
            raise LookupError("x or y not found.")
    
    def switch_1(p, s):
        """Switches the roles of p and s,
        where p (parent) is the direct parent of s (son)."""
        assert s.parent == p
        
        if s.is_left_child():
            p.left = s.left
            if s.left:
                s.left.parent = p
        
            s.left = p
            
            s.right, p.right = p.right, s.right
            if s.right:
                s.right.parent = s
            if p.right:
                p.right.parent = p
        else:
            p.right = s.right
            if s.right:
                s.right.parent = p
                
            s.right = p

            s.left, p.left = p.left, s.left
            if s.left:
                s.left.parent = s
            if p.left:
                p.left.parent = p
        
        if p.parent:
            if p.is_left_child():
                p.parent.left = s 
            else:
                p.parent.right = s
        else:  # p is the root
            self.root = s
            
        s.parent = p.parent
        p.parent = s

    def switch_2(u, v):
        """u and v are nodes in the tree
        that are not related by a parent-son
        or a grandparent-son relantionships."""
        if not u.parent:
            self.root = v
            if v.is_left_child():
                v.parent.left = u
            else:
                v.parent.right = u
        elif not v.parent:
            self.root = u
            if u.is_left_child():
                u.parent.left = v
            else:
                u.parent.right = v
        else:  # neither u nor v is the root                
            if u.is_left_child():
                if v.is_left_child():                   
                    v.parent.left, u.parent.left = u, v
                else:
                    v.parent.right, u.parent.left = u, v
            else:
                if v.is_left_child():                   
                    v.parent.left, u.parent.right = u, v
                else:
                    v.parent.right, u.parent.right = u, v                    
                
        v.parent, u.parent = u.parent, v.parent
        u.left, v.left = v.left, u.left
        u.right, v.right = v.right, u.right

        if u.left:
            u.left.parent = u
        if u.right:
            u.right.parent = u
        if v.left:
            v.left.parent = v
        if v.right:
            v.right.parent = v
    
    if x.parent == y:
        switch_1(y, x)            
    elif y.parent == x:
        switch_1(x, y)
    else:
        switch_2(x, y)

我真的需要 switch 在所有情况下都能正常工作，无论我们选择哪个节点 x 或 y。我已经做了一些测试，它似乎有效，但我仍然不确定。

编辑

最后，如果它以某种方式有帮助，这里你有我的 BST 的完整实现(我正在做的测试):

https://github.com/dossan/ands/blob/master/ands/ds/BST.py

编辑 2(只是出于好奇)

@Rishav 评论道:

I do not understand the intention behind this function.. if it is to swap two nodes in the BST, is it not sufficient to swap their data instead of manipulating pointers?

我回答:

Ok, maybe I should have added a little bit more about the reason behind all this "monster" function. I can insert BSTNode objects or any comparable objects in my BST. When the user decides to insert any comparable object, the responsibility of creating the BSTNode is mine, therefore the user has no access to a initial BSTNode reference, unless they search for the key. But a BSTNode would only be returned after the insertion of the key, or there's already another BSTNode object in the tree with the same key (or value), but this latter case is irrelevant.

The user can also insert a BSTNode object in the tree which has an initial (and should remain constant) key (or value). Nevertheless, if I just exchanged the values or keys of the nodes, the user would have a reference to a node with a different key then the key of the node he inserted. Of course, I want to avoid this.

Answer 1

您需要适当的单元测试。我推荐python-nose - 非常易于使用。

至于测试向量，我建议使用两个节点 a 和 b 的所有可能组合:

对于 BST 树，您有 3 种类型的节点:

1. 叶节点，
2. 1-子节点，
3. 2-子节点。

结合以下其他情况:

1. a 是root，或者
2. a 是b 的父级，
3. a 不是 b 的父级。

以及它们的组合(也在对称情况下)。

然后在交换之后你需要检查所有涉及的节点，即:a,b，a 和 b 的 child ，a 和 b 的 parent ，如果一切按计划进行的话。

我会使用包含所有类型节点的小树来做到这一点。然后遍历节点的所有可能组合并交换节点并检查预期结果，然后再次交换以使树恢复到其原始状态。

[编辑]

如果您的问题是如何避免所有繁琐的工作。您可以考虑寻找一些完善的 BST 实现并将结果与​​您的函数进行比较。可以通过使用准备好的树并生成该树的所有可能节点对来自动创建向量。

[/编辑]

至于函数的不需要的输入。你需要发挥你的想象力，尽管在我看来你已经涵盖了大多数情况。除了 Austin Hastings 提到的至少一个输入节点不属于树的那个。

我找到了为我的一个私有(private)项目编写的相同函数的旧版本，也许你会发现它有用:

def swap( a, b ):
    if a == b: return
    if a is None or b is None: return
    #if a not in self or b not in self: return

    if b.parent == a:
        a, b = b, a

    #swap connections naively
    a.parent, b.parent = b.parent, a.parent
    a.left, b.left = b.left, a.left
    a.right, b.right = b.right, a.right

    if b.parent == b: #b was the p of a
        b.parent = a

    if a.parent is not None:
        if a.parent.left == b: a.parent.left = a
        else: a.parent.right = a
    else:
        self.root = a

    if b.parent is not None:
        if b.parent.left == a: b.parent.left = b
        else: b.parent.right = b
    else:
        self.root = b

    if a.right is not None: a.right.parent = a
    if a.left is not None: a.left.parent = a
    if b.right is not None: b.right.parent = b
    if b.left is not None: b.left.parent = b

和性能优化版本:

def swap_opt( a, b ):
    if a == b: return
    if a is None or b is None: return
    #if a not in self or b not in self: return

    if b.p == a:
        a, b = b, a

    #swap connections naively
    a.p, b.p = b.p, a.p
    a.l, b.l = b.l, a.l
    a.r, b.r = b.r, a.r

    if b.p == b: #b was the p of a
        b.p = a
        if a.l == a:
            a.l = b
            if a.r is not None: a.r.p = a
        else:
            a.r = b
            if a.l is not None: a.l.p = a

        if b.r is not None: b.r.p = b
        if b.l is not None: b.l.p = b
        if a.p is not None:
            if a.p.l == b: a.p.l = a
            else: a.p.r = a
        else:
            #set new root to a
            pass

    else:
        if a.r is not None: a.r.p = a
        if a.l is not None: a.l.p = a
        if b.r is not None: b.r.p = b
        if b.l is not None: b.l.p = b

        if a.p is not None:
            if a.p.l == b: a.p.l = a
            else: a.p.r = a
        else:
            #set new root to a
            pass
        if b.p is not None:
            if b.p.l == a: b.p.l = b
            else: b.p.r = b
        else:
            #set new root to b
            pass

我没有对这段代码进行适当的单元测试——它按我预期的那样工作。我对实现之间的性能差异更感兴趣。swap_opt 处理相邻节点的速度稍快一些，与 swap 的紧凑实现相比，速度提高了大约 5%。 [EDIT2] 但这取决于用于测试和硬件的树 [/EDIT2]