什么是二叉搜索树
二叉搜索树是一种综合效率比较好的一种数据结构，搜索、插入、删除的复杂度等于树高， 平均空间复杂度为O（n），时间复杂度为O(log n)，最坏时间复杂度为O（n），（当插入的数列有序，导致二叉树退化为线性表），故一些其他的树，在二叉搜索树基础上进行改良的平衡树，如AVL树、红黑树等，可以使得树的高度总是得到平衡，从而使得最坏的情况下，时间复杂度也能达到O(log n)。
在没有二叉搜索树这种结构出现的时候，我们如果想对一个有序的序列，进行快速的检索，使用数组是可以做到的，但数组的弊端在于，如果我想向这个序列里面插入或者删除一个新的元素，使用数组就可能捉襟见肘了，而链表则对插入，删除非常友好，但检索性能比较低，故才出现了二叉搜索树这种结够，使得查询和更新能够达到不错的一个O（log n）性能权衡。
二叉搜索树的特点
（1）每个节点包含一个key，也称data的数据域
（2）左子树不为空的情况下，左子树的每个节点值都小于根节点的值，即：L < P
（3）右子树不为空的情况下，右子树的每个节点值都大于根节点的值，即：P < R
（4）节点的值不允许出现重复
（5）任意节点的左，右子树，均符合上面的规则
二叉搜索树的插入
二叉搜索树的插入与二叉树的搜索非常类似，当一个新的值要插入的时候，首先与根节点进行比较，如果大于根节点则进入右子树进行递归找位置，如果小于根节点则进入左子树进行递归找位置，按照二叉树的性质，新插入的节点最终会落在某在一个位置上，注意如果该值已经存在那么则不做任何处理，因为二叉树不允许重复的值插入。 下图在插入节点7之后的变化：
二叉搜索树的搜索
二叉搜索树的搜索与插入流程类型，都是从root节点开始，然后锁定要查询节点所在的子树，如果大于根节点则在右边搜索，否则则在左边，然后递归遍历，直到找到结果，如果没有找到，则返回false即可。
二叉搜索树的删除
删除相对于插入和搜索要复杂一点，删除一个节点要考虑如下几种情况：
（1）删除的节点不存在
（2）删除的节点是叶子节点
（3）删除的节点有一个孩子节点
（4）删除的节点包含两个孩子节点
第一种情况，不做处理，第二种和第三种情况，其实与链表处理的策略是一样的，如果是叶子节点直接将其赋值成null即可，如果包含一个孩子节点，则直接取孩子节点覆盖要删除的节点即可，如下：
第四种情况，如果该节点有两个孩子节点，这种情况就复杂了点，因为直接删除该节点会导致树结构遭到破坏，所以不能直接删除，要先找到该节点在左子树里面的最大节点或者右子树里面的最小节点，然后将最大节点的值替换到要删除的节点，之后在左子树里面再删除该节点的值即可，这样就完成了拥有两个节点删除的情况，如下图示：
下面我们看下代码实现：
首先定义一个二叉树结构：
public class BST< T extends Comparable<T>> {
public Node<T> root;
static class Node<T>{ public T data; public Node<T> left; public Node<T> right;
public Node(T data, Node<T> left, Node<T> right) { this.data = data; this.left = left; this.right = right; }
@Override public String toString() { return "Node{" + "data=" + data + '}'; } }
}然后分别定义插入方法：
public void insert(T data){ root=insert(root, data); //递归插入 }
public Node<T> insert(Node<T> p, T data){
if(p==null){ return new Node<>(data,null,null); }
if(compare(p.data,data)==0){ return p; }
if(compare(data,p.data)<0){ p.left=insert(p.left,data); }else { p.right=insert(p.right,data); } return p; }搜索方法：
public boolean search(T data){ return search(root,data); }
public boolean search(Node<T> node,T data){ if(node==null){ return false; } if(compare(node.data,data)==0){ return true; }else if(compare(data,node.data)<0) { return search(node.left,data); }else{ return search(node.right,data); }
}最后是删除的方法：
public void delete(T data){ root=delete(root,data); }
public Node<T> delete(Node<T> node,T data){
if(node==null){ throw new RuntimeException("删除的节点不存在"); }else if(compare(data,node.data)<0){ node.left=delete(node.left,data); }else if(compare(data,node.data)>0){ node.right=delete(node.right,data); }else{//叶子节点，或者只拥有一个孩子节点的处理逻辑是一样的 if(node.left==null){ return node.right; }else if(node.right==null){ return node.left; }else{ //到这一步说明删除的节点拥有2个孩子节点 //找到剩下左子树里面最大的节点，或者找到右子树里面最小的节点，这里使用的是前者 //使用最大值覆盖当前要被删除的节点的值 node.data=retrieveData(node.left); //最后删除，在剩下左子树里面刚才被替换到最大值的节点 node.left=delete(node.left,node.data); }
}
return node; }
private T retrieveData(Node<T> p) { while (p.right != null) p = p.right;
return p.data; }二叉搜索树的中序遍历，即可得到一个有序的数列，我们看下中序遍历的递归实现：
private void inOrder(Node<T> node){ if(node==null) return; inOrder(node.left); System.out.println(node); inOrder(node.right); }代码比较简单，然后我们再看下不用递归，使用迭代方式的中序遍历方式：
public void inOrderiterator(Node<Integer> root){
Stack<Node<Integer>> stack=new Stack<>(); List<Integer> list=new ArrayList<>(); while (root!=null||!stack.isEmpty()){ if(root!=null) { stack.push(root); root = root.left; }else{ root=stack.pop(); list.add(root.data); root=root.right; } }
System.out.println(list);
}这里借助了栈这个数据结构，非常简单的就实现了迭代版本的中序遍历，关于前序和后序版本这里就不再给出例子了，感兴趣的朋友可以自己研究下。
二叉搜索树是一个非常高效的数据结构，其综合效率约为O（logn），但插入数列为有序数列时，插入性能会退化为O（n），这是二叉搜索树的一个弊端，在改良后加入了具有平衡的功能时候，可以使得树的高度保持均衡，就演变成了AVL或者红黑树，这个时候即使是有序数列，插入性能也可保持在O（logn），这也是为什么红黑树高效的原因，因为其在插入时候能够自我调整树的高度，不会在极端情况下发生退化倾斜向一边的场景。