Splayツリーの実装でのバグ

Question

私はSplayツリーを実装しようとしていましたが、今まで成功していませんでした。以前はバイナリ検索ツリーと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という（）メソッドがあると思いルートまでのノードを移動されています間違っているのは分かりません。

Answer 1

を助けなければならないこと。

最初に、ローテーションメソッドに微妙なバグがあり、子供のリンクの1つをNoneに設定していないことがありました。最初のifのrotRoot.rightChild = newRoot.leftChildの行は、rotateLeft（および同等の行はrotateRight）で無条件に実行する必要があります。 ifからそれを上に移動して修正してください。

2番目の問題は、moveUpをあまりにも頻繁に呼び出すことです。あなたは_putへのすべての再帰呼び出しから実行していますが、moveUpもそれ自体を再帰的に呼び出すので、あまりにも頻繁に実行されます。 _putに呼び出しをインデントして、新しいノードを作成するブロックelseの一部にします。そうすれば、最後の_putコールからのコールではなく、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 

Answer 2

は、2つの場所であなたの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 

あなたのコード内の二つの問題がありました