二叉查找树(二叉排序树)的详细实现

1、序

当所有的静态查找结构添加和删除一个数据的时候，整个结构都需要重建。这对于常常需要在查找过程中动态改变数据而言，是灾难性的。因此人们就必须去寻找高效的动态查找结构，我们在这讨论一个非常常用的动态查找树——二叉查找树。

本文详细实现了二叉查找树的各种操作：插入结点、构造二叉树、删除结点、查找、查找最大值、查找最小值、查找指定结点的前驱和后继

2、二叉查找树简介

如果所有的插入序列都是等可能的，那么，树的所有节点的平均深度为O(logN)

下面的图就是两棵二叉查找树，我们可以总结一下他的特点：

(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值

(2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
(3) 它的左、右子树也分别为二叉查找树

我们中序遍历这两棵树发现一个有序的数据序列：【1 2 3 4 5 6 7 8 】

二叉查找树的操作

插入操作：

现在我们要查找一个数9，如果不存在则，添加进a图。我们看看二叉查找树动态添加的过程：

1). 数9和根节点4比较(9>4)，则9放在节点4的右子树中。

2). 接着，9和节点5比较(9>5)，则9放在节点5的右子树中。

3). 依次类推：直到9和节点8比较(9>8)，则9放在节点8的右子树中，成为节点8的右孩子。

这个过程我们能够发现，动态添加任何一个数据，都会加在原树结构的叶子节点上，而不会重新建树。由此可见，动态查找结构确实在这方面有巨大的优势。

删除操作：

如果二叉查找树中需要删除的结点左、右子树都存在，则删除的时候需要改变一些子树结构，但所需要付出的代价很小。

二叉查找树的效率分析

那么我们再来看看二叉查找树的效率问题

很显然，在a,b两图的二叉查找树结构中查找一个数据，并不需要遍历全部的节点元素，查找效率确实提高了。但是有一个很严重的问题：我们在a图中查找8需要比较5次数据，而在B图中只需要比较3次。更为严重的是：如果按有序序列[1 2 3 4 5 6 7 8]建立一颗二叉查找树，整棵树就退化成了一个线性结构（如c输入图：单支树），此时查找8需要比较8次数据，和顺序查找没有什么不同。

总结一下：最坏情况下，构成的二叉排序树蜕变为单支树，树的深度为n，其查找时间复杂度与顺序查找一样O(N)。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2(N)成正比（O(log2(n))）。

这说明：同样一组数据集合，不同的添加顺序会导致查找树的结构完全不一样，直接影响了查找效率。

那么如何解决这个问题呢? 我们会在下面的专题中：《平衡二叉树》中来解决。

3、二叉查找树的详细实现（C++）

/**
 *BST 的实现
 * */

template <typename Comparable>
class BinarySearchTree
{
    public:
    BinarySearchTree();
    BinarySearchTree(const BinarySearchTree & ths);
    ~BinarySearchTree();

    const Comparable & findMin() const;
    const Comparable & findMax() const;
    bool contains(const Comparable & x) const;
    bool isEmpty() const;
    void printTree() const;

    void makeEmpty();
    void insert(const Comparable & x);
    void remove(const Comparable & x);

    const BinarySearchTree & operator=(const BinarySearchTree & rhs);

    private:
    struct BinaryNode{
        Comparable element;
        BinaryNode *left;
        BinaryNode *right;

        BinaryNode(const Comparable & theElement, BinaryNode* lt, BinaryNode* rt)
            :element(theElement), left(lt), right(rt){}
    };

    BinaryNode* root;

    void insert(const Comparable & x, BinaryNode* & t) const;
    void remove(const Comparable & x, BinaryNode* & t) const;
    BinaryNode * findMin(BinaryNode * t) const;
    BinaryNode * findMax(BinaryNode * t) const;

    bool contains(const Comparable & x, BinaryNode *t) const;
    void makeEmpty(BinaryNode* &t);
    void printTree(BinaryNode *t) const;
    BinaryNode * clone(BinaryNode *t) const;
};

bool BinarySearchTree::contains(const Comparable & x) const{
    return contains(x, root);
}

bool contains(const Comparable & x, BinaryNode * t) const{
    if(t == NULL)
        return false;
    else if(x < t->element)
        return contains(x, t->left);
    else if(x > t->element)
        return contains(x, t->right);
    else
        return true;
}

//findMin 只要有左儿子就向左进行
//二叉查找树中 最小值 总是在 最左叶子节点

BinaryNode* findMin(BinaryNode* t) const
{
    if( t == NULL)
        return NULL;
    if(t->left == NULL)
        return t;
    return findMin(t->left);
}

//findMax 只要有右儿子就向右进行
//二叉查找树中， 最大值 总是在 最右叶子结点

BinaryNode* findMax(BinaryNode * t)const{
    if(t == NULL)
        return NULL;
    while(t->right)
    {
        t = t->right;
    }
    return t;
}

//为了将X插入到树T中，可以像使用contains那样沿着树查找。如果找到X，则什么也不做。否则，将X插入到遍历的路径上的最后一点上
void insert(const Comparable &x, BinaryNode* & t)
{
    if( t == NULL)
        t = new BinaryNode(x, NULL, NULL);
    else if(x < t->element)
        insert(x, t->left);
    else if(x > t->element)
        insert(x, t->right);
    else //duplicate; do nothing
        ;
}

//remove:同许多数据结构一样，最困难的操作是删除。
//这里需要考虑三种情况：
//1、如果节点是叶子节点，那么可以被立即删除
//2、如果节点有一个儿子，则儿子节点替换该节点
//3、有两个儿子节点，这种情况比较复杂。一般的删除策略是其右子树的最小数据代替该节点的数据并递归删除那个节点
//这种删除策略效率并不高，因为它沿着该树进行两次搜索以查找和删除右子树中最小的节点

void remove(const Comparable &x, BinaryNode* & t)
{
    if(t == NULL)
        return ;//Item not found. do nothing
    if(x < t->element)
        remove(x, t->left);
    else if(x > t->element)
        remove(x, t->right);
    else if(t->left != NULL && t->right != NULL)    //two children
    {
        t->element = findMin(t->right)->element;
        remove(t->element, t->right);
    }
    else {  //one child or no child
        BinaryNode* oldNode = t;
        t = (t->left != NULL) ? t->left : t->right;
        delete oldNode;
    }
}

//析构函数和复制赋值操作符
~BinarySearchTree()
{
    makeEmpty();
}

void makeEmpty(BinaryNode * &t)
{
    if(t != NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }

    t = NULL;
}

const BinarySearchTree& operator= (const BinarySearchTree &rhs)
{
    if(this != &rhs)
    {
        makeEmpty();
        root = clone(rhs.root);
    }
    return *this;
}

//Deep Clone
BinaryNode* clone(BinaryNode *t) const{
    if(t == NULL)
        return NULL;
     return new BinaryNode(t->element, clone(t->left), clone(t->right));
}