对于二叉查找树的每个节点Node，它的左子树中所有的关键字都小于Node的关键字，而右子树中的所有关键字都大于Node的关键字。

二叉查找树的平均深度是O(log N)。

1.初始化

class BinarySearchTree(object):    def __init__(self,key):        self.key=key        self.left=None        self.right=None

2.Find

def find(self,x):        if x==self.key:            return self        elif x
     
      self.key and self.right:            return self.right.find(x)        else:            return None
     

3.FindMin和FindMax

分别返回树中的最小元素与最大元素的位置。FindMin，从根开始并且只要有左儿子就向左进行查找，终止点是最小元素。FindMax则向右进行。

def findMin(self):        if self.left:            return self.left.findMin()        else:            return self    def findMax(self):        tree=self        if tree:            while tree.right:                tree=tree.right        return tree

4.Insert

为了将x插入到树Tree中，先用find查找，如果找到x，则什么也不做。否则，将x插入到遍历路径的最后一点。

来自《Problem Solving with Algorithms and Data Structures》的图片：

def insert(self,x):        if x
     
      self.key:            if self.right:                self.right.insert(x)            else:                tree=BinarySearchTree(x)                self.right=tree
     

5.Delete

删除某节点有3种情况：

5.1 如果节点是一片树叶，那么可以立即被删除。

来自《Problem Solving with Algorithms and Data Structures》的图片：

5.2 如果节点只有一个儿子，则将此节点parent的指针指向此节点的儿子，然后删除。

来自《Problem Solving with Algorithms and Data Structures》的图片：

5.3 如果节点有两个儿子，则将其右子树的最小数据代替此节点的数据，并将其右子树的最小数据（不可能有左儿子，只有一个右儿子）删除。

来自《Problem Solving with Algorithms and Data Structures》的图片：

def delete(self,x):        if self.find(x):            if x
     
      self.key:                self.right=self.right.delete(x)                return self            elif self.left and self.right:                key=self.right.findMin().key                self.key=key                self.right=self.right.delete(key)                return self            else:                if self.left:                    return self.left                else:                    return self.right        else:            return self
     

全部代码

class BinarySearchTree(object):    def __init__(self,key):        self.key=key        self.left=None        self.right=None    def find(self,x):        if x==self.key:            return self        elif x
     
      self.key and self.right:            return self.right.find(x)        else:            return None       def findMin(self):        if self.left:            return self.left.findMin()        else:            return self    def findMax(self):        tree=self        if tree:            while tree.right:                tree=tree.right        return tree    def insert(self,x):        if x
      
       self.key:            if self.right:                self.right.insert(x)            else:                tree=BinarySearchTree(x)                self.right=tree    def delete(self,x):        if self.find(x):            if x
       
        self.key:                self.right=self.right.delete(x)                return self            elif self.left and self.right:                key=self.right.findMin().key                self.key=key                self.right=self.right.delete(key)                return self            else:                if self.left:                    return self.left                else:                    return self.right        else:            return self
       
      
     

上述写法的缺点是很难处理空树的情况。

另一种类似于链表的写法

class TreeNode(object):    def __init__(self,key,left=None,right=None,parent=None):        self.key=key        self.left=left        self.right=right        self.parent=parent    def hasLeftChild(self):        return self.left    def hasRightChild(self):        return self.right    def isLeftChild(self):        return self.parent and self.parent.left==self    def isRightChild(self):        return self.parent and self.parent.right==selfclass BSTree(object):    def __init__(self):        self.root=None        self.size=0    def length(self):        return self.size    def insert(self,x):        node=TreeNode(x)        if not self.root:            self.root=node            self.size+=1        else:            currentNode=self.root            while True:                if x
     
      currentNode.key:                    if currentNode.right:                        currentNode=currentNode.right                    else:                        currentNode.right=node                        node.parent=currentNode                        self.size+=1                        break                else:                    break                def find(self,key):        if self.root:            res=self._find(key,self.root)            if res:                return res            else:                return None        else:            return None    def _find(self,key,node):        if not node:            return None        elif node.key==key:            return node        elif key
      
       1:            nodeToRemove=self.find(key)            if nodeToRemove:                self.remove(nodeToRemove)                self.size-=1            else:                raise KeyError,'Error, key not in tree'        elif self.size==1 and self.root.key==key:            self.root=None            self.size-=1        else:            raise KeyError('Error, key not in tree')    def remove(self,node):        if not node.left and not node.right:   #node为树叶            if node==node.parent.left:                node.parent.left=None            else:                node.parent.right=None                   elif node.left and node.right:   #有两个儿子            minNode=self._findMin(node.right)            node.key=minNode.key            self.remove(minNode)                    else:    #有一个儿子            if node.hasLeftChild():                if node.isLeftChild():                    node.left.parent=node.parent                    node.parent.left=node.left                elif node.isRightChild():                    node.left.parent=node.parent                    node.parent.right=node.left                else:    #node为根                    self.root=node.left                    node.left.parent=None                    node.left=None            else:                if node.isLeftChild():                    node.right.parent=node.parent                    node.parent.left=node.right                elif node.isRightChild():                    node.right.parent=node.parent                    node.parent.right=node.right                else:   #node为根                    self.root=node.right                    node.right.parent=None                    node.right=None