I have been trying to implement splay tree but met with no success so far.Previously I successfully implemented binary search tree and avl tree and since splay tree is a variation of binary search tree so the insertion code and rotation code is fine.The only problem I am facing is moving the node up to the root each time a node is inserted.This is my code
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()
I think my moveUp() method is where things are going wrong.But I can't seem to figure out what exactly is going wrong?
There were two issues in your code.
The first was that you had a subtle bug in your rotation methods, where you were sometimes failing to set one of the child links to None when you should. The line rotRoot.rightChild = newRoot.leftChild in the first if in rotateLeft (and the equivalent line in rotateRight) should be run unconditionally. Just move it up out of the if to fix it.
The second issue is that you're calling moveUp too often. You're running it from every recursive call to _put, but since it moveUp calls itself recursively too, that means it runs too often. Indent the calls in _put so that they're part of the else blocks where you're creating the new nodes. That way, you will only call moveUp from the last _put call, rather than from all of them.
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