document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. from treenode import TreeNode
  2.  
  3. class BinarySearchTree:
  4.     def __init__(self):
  5.         self.root = None
  6.         self.size = 0
  7.    
  8.     def length(self):
  9.         return self.size
  10.    
  11.     def __len__(self):
  12.         return self.size
  13.    
  14.     def __iter__(self):
  15.         return self.root.__iter__()
  16.    
  17.     def get(self,key):
  18.         if self.root is not None:
  19.             res = self._get(key,self.root)
  20.             if res is not None:
  21.                 return res.payload
  22.             else:
  23.                 return None
  24.         else:
  25.             return None
  26.    
  27.     def _get(self,key,currentNode):
  28.         if not currentNode:
  29.             return None
  30.         elif currentNode.key == key:
  31.             return currentNode
  32.         elif key < currentNode.key:
  33.             return self._get(key,currentNode.leftChild)
  34.         else:
  35.             return self._get(key,currentNode.rightChild)
  36.    
  37.     def _put(self,key,val,currentNode):
  38.         """helper function for put(), finds the correct
  39.        placing for a new node"""
  40.         if key < currentNode.key:
  41.             if currentNode.hasLeftChild():
  42.                 self._put(key,val,currentNode.leftChild)
  43.             else:
  44.                 currentNode.leftChild = TreeNode(key,val,parent=currentNode)
  45.         else:
  46.             if currentNode.hasRightChild():
  47.                 self._put(key,val,currentNode.rightChild)
  48.             else:
  49.                 currentNode.rightChild = TreeNode(key,val,parent=currentNode)
  50.    
  51.     def put(self,key,val):
  52.         node = self._get(key,self.root)
  53.        
  54.         if node is None:
  55.             if self.root:
  56.                 self._put(key,val,self.root)
  57.             else:
  58.                 self.root = TreeNode(key,val)
  59.             self.size += 1
  60.         else:
  61.             #key is already in tree
  62.             #replace the value
  63.             node.payload = val
  64.    
  65.     def __getitem__(self, key):
  66.         return self.get(key)
  67.    
  68.     def remove(self, currentNode):
  69.         """remove a node from the tree"""
  70.         if currentNode.isLeaf():
  71.             if currentNode == currentNode.parent.leftChild:
  72.                 currentNode.parent.leftChild = None
  73.             else:
  74.                 currentNode.parent.rightChild = None
  75.         elif currentNode.hasBothChildren():
  76.             succ = currentNode.findSuccessor()
  77.             succ.spliceOut()
  78.             currentNode.key = succ.key
  79.             currentNode.payload = succ.payload
  80.        
  81.         else:
  82.             if currentNode.hasLeftChild():
  83.                 if currentNode.isLeftChild():
  84.                     currentNode.leftChild.parent = currentNode.parent
  85.                     currentNode.parent.leftChild = currentNode.leftChild
  86.                 elif currentNode.isRightChild():
  87.                     currentNode.leftChild.parent = currentNode.parent
  88.                     currentNode.parent.rightChild = currentNode.leftChild
  89.                 else:
  90.                     #currentNode is root
  91.                     currentNode.replaceNodeData(currentNode.leftChild.key,
  92.                                                 currentNode.leftChild.payload,
  93.                                                 currentNode.leftChild.leftChild,
  94.                                                 currentNode.leftChild.rightChild)
  95.             else: #has right child
  96.                 if currentNode.isLeftChild():
  97.                     currentNode.rightChild.parent = currentNode.parent
  98.                     currentNode.parent.leftChild = currentNode.rightChild
  99.                 elif currentNode.isRightChild():
  100.                     currentNode.rightChild.parent = currentNode.parent
  101.                     currentNode.parent.rightChild = currentNode.rightChild
  102.                 else:
  103.                     currentNode.replaceNodeData(currentNode.rightChild.key,
  104.                                                 currentNode.rightChild.payload,
  105.                                                 currentNode.rightChild.leftChild,
  106.                                                 currentNode.rightChild.rightChild)
  107.    
  108.     def delete(self, key):
  109.         if self.size > 1:
  110.             nodeToRemove = self._get(key, self.root)
  111.             if nodeToRemove is not None:
  112.                 self.remove(nodeToRemove)
  113.                 self.size -= 1
  114.             else:
  115.                 raise KeyError("Key is not in tree")
  116.         elif self.size == 1 and self.root.key == key:
  117.             self.root = None
  118.             self.size -= 1
  119.         else:
  120.             raise KeyError("Cannot delete key from an empty tree")
  121.    
  122.     def __delitem__(self, key):
  123.         self.delete(key)
  124.        
  125.     def getAsList(self):
  126.         """Non-recursive inorder traversal"""
  127.         result = []
  128.         currentNode = None
  129.        
  130.         if self.size == 1:
  131.             result.append(str(self.root.key) + ":" + str(self.root.payload))
  132.         elif self.size > 1:
  133.             currentNode = self.root.findMin()
  134.            
  135.             while currentNode is not None:
  136.                 result.append(str(currentNode.key) + ":" + str(currentNode.payload))
  137.                 currentNode = currentNode.findSuccessor()
  138.         return result
');