1

我正在为展开树编写代码，但我对展开树的删除方面有疑问。在互联网上研究它之后，这是我发现的：

首先搜索要删除的元素并将其展开到顶部。然后执行以下操作

  1. 如果根（将元素展开到顶部之后）同时具有左右子节点，则删除根，这样您现在就有两个子树。在左子树中，找到最大的元素并将其展开到顶部，然后将其连接到右子树的根。
  2. 如果根没有左孩子但有右孩子，则删除该根并将右子树的根作为新根。

但是如果根没有正确的孩子怎么办？所以我删除根，让左子树的根成为新的根？

还有其他需要我注意的条件吗？

如果有帮助，我在下面编写了删除代码。

def delete(self,key):
    res = self.get(key) #The get() function also does the splaying operation as well
    if res:
        ls = self.root.leftChild
        rs = self.root.rightChild
        if ls is not None and rs is not None: #has both the child
            ls.parent = None
            rs.parent = None
            current = ls
            while ls.hasRightChild():
                current = current.rightChild #find the largest element
            self.get(current.key)
            rs.parent = current
            current.rightChild = rs
            self.root = current
        elif ls is None and rs is not None: #has no left child
            rs.parent = None
            self.root = rs
        elif ls is None and rs is None: #has no left or right child ie the tree contains only one node
            self.root = None
    else:
        return
4

0 回答 0