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
    
     , 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
     
       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的实现一般都是用红黑树。