二叉搜索树
二叉搜索树二叉搜索树是一种应用非常广泛的二叉树，英文名称为BinarySearchTree，简称BST。二叉搜索树的性质：1、若左子树不空，则左子树上所有结点的值均小于它的根结点的值。2、若右子树不空，则右子树上所有结点的值均大于它的根结点的值。3、左、右子树也是一棵二叉搜索树。
二叉搜索树的遍历
二叉搜索树的查找
二叉搜索树的最大最小元素下面的过程返回了一个指向在以给定阶段x为根的子树中的最小元素的指针，这里假设不为NIL。给出最大元素的过程是对称的，如下：
二叉搜索树的插入
二叉搜索树的删除
删除叶子节点(没有孩子)这种情况可以直接删除节点，假设要删除的节点为node，则1、当node.parent==null时，root=null2、当node==node.parent.left时，node.parent.left=null3、当node==node.parent.right时，node.parent.right=null
删除度为1的节点(孩子数为1）用子节点代替原节点的位置，假设node是原节点，son是子节点1、如果node是根节点root=sonson.parent=null2、如果node是左子节点son.parent=node.parentnode.parent.left=son3、如果node是右子节点son.parent=node.parentnode.parent.right=son
前驱和后继
删除度为2的节点(孩子数为2)假如要删除节点121、先用前驱或者后继节点的值覆盖原节点的值2、然后删除相应的前驱或者后继节点如果一个节点的度为2，那么，它的前驱、后继节点的度只可能为1或者0，当前驱、后继节点的度为1时，前驱节点只有左孩子，后继节点只有右孩子。
二叉搜索树不平衡假如构建二叉搜索树的过程中，数据是高度有序的（包括顺序和逆序），此时构建出的二叉搜索树会高度不平衡，甚至退化成链表，增删改查的效率大大降低。
随机构建二叉搜索树
谢谢！