如果y是x右子树的一个节点，那么y.key >= x.key;
二叉搜索树的插入 class BST: def __init__(self): self.root=None #空不是根节点 而是None def insert(self,key): if not self.root: self.root = BiTreeNode(key) else: p=self.root while p: if key < p.data: #分为左子树是否为空的情况 if p.lchild: #左子树有节点就在左子树继续查找，否则就插入左节点的位置 p = p.lchild else: p.lchild = BiTreeNode(key) elif key > p.data: if p.rchild: p = p.rchild else: p.lchild = BiTreeNode(key) break else: break 二叉搜索树的查找 def query(self,key): p = self.root while p : if key < p.data: p = p.lchild elif key >p.data: p=p.rchild else: return True return False 二叉搜索树的删除删除有三种情况：
如果要删除的节点是叶子节点，那么找到后直接删除。
如果要删除的节点有一个子节点点，将 此节点的父节点和子节点相连接，然后删除此节点。
如果删除的节点有两个子节点，找到其左子树最大的节点或者右子树的最小节点，删除并替换当前节点，若最后一个一个节点还有一个右子节点，那么再按照第二种情况处理。
二叉搜索树的效率和AVL树平均情况下，二叉搜索时的时间复杂度为O(logn)，但是二叉搜索树可能会出现偏斜的情况，需要采用随机打乱的方法，所以这时候采用AVL树(自动平衡树)。
相关知识点：
AVL树：AVL树是一棵自平衡的二叉搜索树，它具有以下性质：
根的左右子树高度之差的绝对值不能超过1.
计算方法：
每个节点的左右子树的深度之差，也就是平衡因子。
根的左右子树都是平衡二叉树。
AVL树的插入操作插入一个节点可能会造成AVL树的不平衡，可以通过旋转操作来修正。
插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变，需要找到第一个平衡条件的节点，称之为K，K的两棵子树高度差肯定为2.
不平衡的出现有四种情况：
不平衡是由于对K的右子节点的右子树插入导致的：左旋。
不平衡是由于对K的左子节点的左子树插入导致的：右旋。
不平衡是由于右子节点的左子树插入导致的：右旋->左旋。
不平衡是由于左子节点的右子树插入导致的：左旋->右旋。
B树B-Tree是一种自平衡的多路搜索树，B-Tree存储在硬盘里，用于数据库的索引。