构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找的效率。
那么什么是二叉排序树呢？二叉排序树具有以下几个特点。
1：若根节点有左子树，则左子树的所有节点都比根节点小。
2：若根节点有右子树，则右子树的所有节点都比根节点大。
3：根节点的左，右子树也分别为二叉排序树。
二叉搜索树涉及三个操作：插入，查找，删除
插入和查找原理是一样的。
从根节点开始，比较当前节点与查找值的大小决定向左走还是向右走，直到走到叶子节点。
删除操作需要考虑三种不同的情况
- Deleting a node with no children: simply remove the node from the tree.
- Deleting a node with one child: remove the node and replace it with its child.
- Deleting a node with two children: call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases.
If you choose in-order successor of a node, as right sub tree is not NIL (Our present case is node has 2 children), then its in-order successor is node with least value in its right sub tree, which will have at a maximum of 1 sub tree, so deleting it would fall in one of first 2 cases.
Broadly speaking, nodes with children are harder to delete. As with all binary trees,** a node's in-order successor is its right subtree's left-most child, and a node's in-order predecessor is the left subtree's right-most child**. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.
def binary_tree_delete(self, key):
if key < self.key:
self.left_child.binary_tree_delete(key)
elif key > self.key:
self.right_child.binary_tree_delete(key)
else: # delete the key here
if self.left_child and self.right_child: # if both children are present
successor = self.right_child.find_min()
self.key = successor.key
successor.binary_tree_delete(successor.key)
elif self.left_child: # if the node has only a *left* child
self.replace_node_in_parent(self.left_child)
elif self.right_child: # if the node has only a *right* child
self.replace_node_in_parent(self.right_child)
else: # this node has no children
self.replace_node_in_parent(None)
