[硕.Love Python] BinarySearchTree(二叉搜索树)

class Node(object):
    __slots__ = ['left', 'right', 'data']

    def __init__(self, data, left=None, right=None):
 self.data = data
 self.left = left
 self.right = right

    def __str__(self):
 sl = '%s <-' % self.left if self.left else ''
 sr = '-> %s' % self.right if self.right else ''
 return '[%s Node(%s) %s]' % (sl, self.data, sr)

class BinarySearchTree(object):
    def __init__(self):
 self.root = None

    def insert(self, data):
 node, parent = self.search(data, True)
 if node:
     raise ValueError('"%s" has been in tree.' % data)

 node = Node(data)
 if parent is None:
     self.root = node
 elif data < parent.data:
     parent.left = node
 else:
     parent.right = node 

    def search(self, data, retParent=False):
 parent = None
 node = self.root

 while node and node.data != data:
     parent = node
     if data < node.data:
  node = node.left
     else:
  node = node.right

 return (node, parent) if retParent else node

    def delete(self, data):
 self._deleteNode(*self.search(data, True))

    def _findBiggest(self, node):
 parent = None
 while node.right:
     parent = node
     node = node.right
 return node, parent

    def _deleteNode(self, node, parent):
 if node is None:
     return 

 if node.left and node.right:
     tmp, tmpParent = self._findBiggest(node.left)
     if tmpParent is not None:
  tmpParent.right = tmp.left
  tmp.left = node.left 
     tmp.right = node.right
 else:
     tmp = node.left or node.right

 if parent is None:
     self.root = tmp
 elif parent.left is node:
     parent.left = tmp
 else:
     parent.right = tmp

if __name__ == '__main__':
    bst = BinarySearchTree()
    while True:
 cmd = (raw_input('$ ')).strip().split()
 if cmd[0] == 'i':
     bst.insert(int(cmd[1]))
     print bst.root
 elif cmd[0] == 'd':
     bst.delete(int(cmd[1]))
     print bst.root