Splay 树插入实现中的错误

Question

我一直在尝试实现 splay 树，但没有成功，所以 far.Previously 我成功地实现了二叉搜索树和 avl 树，因为 splay 树是二叉搜索树的变体，所以插入代码和旋转代码是 fine.The 我面临的唯一问题是每次节点是 inserted.This 时将节点向上移动到根是我的代码

class SplayTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def moveUp(self, currentNode):
        if currentNode.parent:
            if currentNode.parent.parent is not None:
                #zig zag
                if currentNode.isRightChild() and currentNode.parent.isLeftChild():
                    self.rotateLeft(currentNode.parent)
                    self.rotateRight(currentNode.parent)

                elif currentNode.isLeftChild() and currentNode.parent.isRightChild():
                    self.rotateRight(currentNode.parent)
                    self.rotateLeft(currentNode.parent)

                #zig zig
                if currentNode.isLeftChild() and currentNode.parent.isLeftChild():
                    self.rotateRight(currentNode.parent.parent)
                    self.rotateRight(currentNode.parent)

                elif currentNode.isRightChild() and currentNode.parent.isRightChild():
                    self.rotateLeft(currentNode.parent.parent)
                    self.rotateLeft(currentNode.parent)
                self.moveUp(currentNode)

            #zig
            if currentNode.isLeftChild():
                self.rotateRight(currentNode.parent)
            elif currentNode.isRightChild():
                self.rotateLeft(currentNode.parent)
            self.moveUp(currentNode)

        else:
            return

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size += 1

    def _put(self,key,val,currentNode):               
         if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode)
            self.moveUp(currentNode.leftChild)

         else:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode)
            self.moveUp(currentNode.rightChild)

    def __setitem__(self, key, value):
        self.put(key,value)

    def rotateLeft(self, rotRoot):
        newRoot = rotRoot.rightChild
        if newRoot.leftChild is not None:
            rotRoot.rightChild = newRoot.leftChild
            newRoot.leftChild.parent = rotRoot
        # if subtree is at top or somewhere in between
        # make connection between node and parent
        newRoot.parent = rotRoot.parent
        if rotRoot.parent is None:
            self.root = newRoot
        # make connection between parent and node
        else:
            if rotRoot.isLeftChild():
                rotRoot.parent.leftChild = newRoot
            else:
                rotRoot.parent.rightChild = newRoot
        newRoot.leftChild = rotRoot
        rotRoot.parent = newRoot

    def rotateRight(self, rotRoot):
        newRoot = rotRoot.leftChild
        if newRoot.rightChild is not None:
            rotRoot.leftChild = newRoot.rightChild
            newRoot.rightChild.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.parent is None:
            self.root = newRoot
        else:
            if rotRoot.isLeftChild():
                rotRoot.parent.leftChild = newRoot
            else:
                rotRoot.parent.rightChild = newRoot
        newRoot.rightChild = rotRoot
        rotRoot.parent = newRoot

    def inorder(self):
        print("INORDER")
        if self.root:
            self._inorder(self.root)
            print()
        else:
            return None

    def _inorder(self,currentNode):
        if currentNode:
            self._inorder(currentNode.leftChild)
            print(currentNode.key,end=" ")
            self._inorder(currentNode.rightChild)

class TreeNode:

    def __init__(self,key,val,left = None,right = None,parent = None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isLeaf(self):
        return not (self.leftChild or self.rightChild)

    def hasAnyChildren(self):
        return self.leftChild or self.rightChild

    def hasBothChildren(self):
        return self.leftChild and self.rightChild

st = SplayTree()
st[32] = "Cat"
st[55] = "Dog"
st[10] = "Lion"
st[41] = "Zebra"
st[19] = "Fox"
st[1] = "Wolf"
st[16] = "Tiger"
st[12] = "Pig"
st.inorder()

我认为我的 moveUp() 方法是正确的 wrong.But 我似乎无法弄清楚到底出了什么问题？

Answer 1

尝试在两个地方改变你的 moveUp：

if currentNode.isRightChild() and currentNode.parent.isLeftChild():
    self.rotateLeft(currentNode.parent)
    self.rotateRight(currentNode.parent.parent) // Here
elif currentNode.isLeftChild() and currentNode.parent.isRightChild():
    self.rotateRight(currentNode.parent)
    self.rotateLeft(currentNode.parent.parent) // Here

这应该有帮助

Answer 2

您的代码中存在两个问题。

首先是您的旋转方法中有一个细微的错误，您有时无法将其中一个子链接设置为 None。 rotateLeft 中第一个 if 中的行 rotRoot.rightChild = newRoot.leftChild（以及 rotateRight 中的等效行）应该无条件地运行。只需将其移出 if 即可修复。

第二个问题是您打电话 moveUp 太频繁了。您从对 _put 的每次递归调用中运行宁它，但由于它 moveUp 也递归地调用自身，这意味着它运行太频繁了。缩进 _put 中的调用，使它们成为您创建新节点的 else 块的一部分。这样，您只会从最后一个 _put 调用中调用 moveUp，而不是从所有调用中调用 moveUp。

def _put(self,key,val,currentNode):               
     if key < currentNode.key:
        if currentNode.hasLeftChild():
            self._put(key,val,currentNode.leftChild)
        else:
            currentNode.leftChild = TreeNode(key,val,parent=currentNode)
            self.moveUp(currentNode.leftChild)                     # increase indent here!

     else:
        if currentNode.hasRightChild():
            self._put(key,val,currentNode.rightChild)
        else:
            currentNode.rightChild = TreeNode(key,val,parent=currentNode)
            self.moveUp(currentNode.rightChild)                    # here too

def rotateLeft(self, rotRoot):
    newRoot = rotRoot.rightChild
    rotRoot.rightChild = newRoot.leftChild       # move this line up, out of the if
    if newRoot.leftChild is not None:
        newRoot.leftChild.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.parent is None:
        self.root = newRoot
    # make connection between parent and node
    else:
        if rotRoot.isLeftChild():
            rotRoot.parent.leftChild = newRoot
        else:
            rotRoot.parent.rightChild = newRoot
    newRoot.leftChild = rotRoot
    rotRoot.parent = newRoot

def rotateRight(self, rotRoot):
    newRoot = rotRoot.leftChild
    rotRoot.leftChild = newRoot.rightChild       # this one as well
    if newRoot.rightChild is not None:
        newRoot.rightChild.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.parent is None:
        self.root = newRoot
    else:
        if rotRoot.isLeftChild():
            rotRoot.parent.leftChild = newRoot
        else:
            rotRoot.parent.rightChild = newRoot
    newRoot.rightChild = rotRoot
    rotRoot.parent = newRoot

Splay 树插入实现中的错误

Bug in Splay tree insertion implementation

python-3.x

data-structures

tree

splay-tree