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

Question

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

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

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评论说:

我不明白这个函数背后的意图..如果要在BST中交换两个节点,交换数据而不是操纵指针是不够的？

我回答了:

好吧,也许我应该更多地补充所有这些"怪物"功能背后的原因.我可以BSTNode在BST中插入对象或任何类似的对象.当用户决定插入任何类似对象时,创建该对象的责任BSTNode是我的,因此用户无权访问初始BSTNode引用,除非他们搜索密钥.但BSTNode只有在插入密钥后才会返回,或者BSTNode树中已经有另一个具有相同密钥(或值)的对象,但后一种情况无关紧要.

用户还可以BSTNode在树中插入具有初始(并且应该保持不变)键(或值)的对象.然而,如果我只是交换节点的值或键,则用户将引用具有不同键的节点,然后是他插入的节点的键.当然,我想避免这种情况.

Answer 1

你的BST.py定义class BST。该类的成员有一个元素，self.root可以指向一个节点。如图所示，您的代码没有考虑到这一点。

我相信你需要处理这些情况：

1. 将根节点与其子节点之一交换。
2. 将根节点与非子节点交换。
3. 将非根节点与其子节点之一交换。
4. 将非根节点与非子非根节点交换。

编辑：重新检查 switch_1 后，我认为您确实处理了所有情况。

此外，调用者可能会请求您将不是树成员的节点交换为成员节点。或者交换两个都不是当前树成员的节点。检测这些情况需要花费一些代码，但您可能可以使用dict或set来跟踪树成员资格。我不知道您是否想将“交换”视为有效的操作。

==.在几个地方，您可以使用“这是一个可以被覆盖的操作”来比较节点。您应该使用isandis not进行身份比较和比较None.

最后，请考虑Python 化你的BST类。它是一个可变的可迭代容器，因此它应该尽可能支持标准操作。