1. 定义

二叉搜索树(BST)又叫二叉查找树，二叉排序树。二叉搜索树就是一棵二叉树，但是它又具有搜索树的特征：

• 每个结点都比它的左结点大，比右结点小。
• 每个结点的左右子树都是一课二叉搜索树。
• 对一棵二叉搜索树进行中序遍历结果是从小到大排序的结果。

2. 时间复杂度

二叉搜索树结合了链表插入删除的灵活性和数组的查找的高效性。

• 最好情况：
  最好情况下的二叉搜索树是一棵满二叉树，这时从根结点到所有叶子结点的长度都为lgN，对应树的高度也为lgN。此时无论查找，插入，删除都可以在O(lgN)时间内完成。
• 最坏情况：
  最坏情况下的二叉搜索树的每个结点只有一个孩子，几乎是链表的形状了，对应树的高度为N。此时查找，插入，删除的时间复杂度为O(N)。
• 平均情况：
  二叉搜索树的平均情况应该是介于最好和最好情况之间。

3. 实现

接下来我用二叉搜索树来实现一个符号表，符号表就是一个存储键值对的数据结构，其中键不可以重复，值可以重复。定义了如下操作：

• put(Key key, Value value) 将键key和值value插入符号表
• delete(Key key) 删除指定的键值对
• get(Key key) 获取键对应的值，如果不存在该键则返回null
• deleteMax() 删除最大的键对应的键值对
• deleteMin() 删除最小的键对应的键值对
• min() 获取最小的键
• max() 获取最大的键
• size() 获取符号表的大小
• isEmpty() 判断符号表否为空

代码用java描述，使用了泛型。因为需要进行比较操作，所以键都必须实现Comparable接口。在BST这个类中，使用了一个内部类Node来表示二叉搜索树的结点，同时也是一个键值对。所有操作都是采用迭代的方式。

代码实现

public class BST<Key extends Comparable<Key>, Value> {

    private class Node {
        Key key;
        Value value;
        Node left;
        Node right;

        public Node(Key key, Value value, Node left, Node right){
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    private Node root;
    private int size;

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return root == null;
    }

    public Value get(Key key){
        Node node = root;
        int cmp;
        while(node != null){
            cmp = key.compareTo(node.key);
            if (cmp < 0)
                node = node.left;
            else if (cmp > 0)
                node = node.right;
            else
                return node.value;
        }
        return null;
    }

    public void put(Key key, Value value){
        if (root == null) {
            root = new Node(key, value, null, null);
            size = 1;
            return;
        }

        Node node = root;
        Node parent = null;
        int cmp;

        while (node != null){
            parent = node;
            cmp = key.compareTo(node.key);
            if (cmp < 0)
                node = node.left;
            else if (cmp > 0)
                node = node.right;
            else {
                node.value = value;
                return;
            }
        }

        if (key.compareTo(parent.key) < 0)
            parent.left = new Node(key, value, null, null);
        else
            parent.right = new Node(key, value, null, null);
        ++size;
    }

    private Node max(Node node){
        if (node == null)
            return null;
        while (node.right != null)
            node = node.right;
        return node;
    }

    private Node min(Node node){
        if (node == null)
            return null;
        while (node.left != null)
            node = node.left;
        return node;
    }

    public Key max(){
        Node node = max(root);
        return node == null ? null : node.key;
    }

    public Key min(){
        Node node = min(root);
        return node == null ? null : node.key;
    }


    private Node deleteMax(Node node) {
        Node x = node;
        if (node == null)
            return null;

        Node parent = null;
        while (node.right != null){
            parent = node;
            node = node.right;
        }

        --size;
        if (parent == null)
            return node.left;
        else
            parent.right = node.left;

        return x;

    }

    private Node deleteMin(Node node) {
        Node x = node;

        if (node == null)
            return null;

        Node parent = null;
        while (node.left != null){
            parent = node;
            node = node.left;
        }

        --size;
        if (parent == null)
            return node.right;
        else
            parent.left = node.right;

        return x;
    }

    public void deleteMax(){
        root = deleteMax(root);
    }

    public void deleteMin(){
        root = deleteMin(root);
    }

    public void traverse(){
        traverse(root);
    }

    //中序遍历
    private void traverse(Node node){
        if (node == null)
            return;

        traverse(node.left);
        System.out.println(node.key);
        traverse(node.right);
    }

    public void delete(Key key) {
        if (root == null)
            return;
        Node node = root;
        Node parent = root;
        int cmp;

        while (node != null){
            cmp = key.compareTo(node.key);

            if (cmp == 0) {
                --size;
                cmp = key.compareTo(parent.key);

                if (node.left == null){
                    if (cmp < 0)
                        parent.left = node.right;
                    else if (cmp > 0)
                        parent.right = node.right;
                    else
                        root = node.right;
                    return;
                }

                if (node.right == null){
                    if (cmp < 0)
                        parent.left = node.left;
                    else if (cmp > 0)
                        parent.right = node.left;
                    else
                        root = node.left;
                    return;
                }

                Node x = min(node.right);
                node.key = x.key;
                node.value = x.value;
                node.right = deleteMax(node.right);
            }
            else {
               parent = node;
               if (cmp < 0)
                   node = node.left;
               else
                   node = node.right;
            }
        }
    }


    public static void main(String[] args){

        BST<Integer, String> bst = new BST<>();
        bst.put(2, "qw");
        bst.put(3, "fy");
        bst.put(5, "naoko");
        bst.put(1, "qw");
        bst.put(4, "naoko");
        bst.put(-3, "naoko");
        bst.deleteMax();
        bst.deleteMin();
        bst.delete(10);
        bst.traverse();
    }
}

4. 最后

二叉搜索树虽然简单但在最坏情况下表现得并不好。不过它是其他树类型的数据结构的基础，二叉搜索树还有其他变种如AVL树，红黑树，Treap树等。在C++，Java的集合API中，符号表或是Set的实现一般都是用红黑树。