二叉搜索树 Binary Search Tree

二叉搜索树 Binary Search Tree

定义

二叉搜索树（二叉排序树或二叉查找树）：

• 或者是一棵空树；
• 或者是具有如下特性的二叉树
  1. 若它的左子树不空，则左子树上所有节点
     的值均小于根节点的值；
  2. 若它的右子树不空，则右子树上所有节点
     的值均大于等于根节点的值；
  3. 它的左、右子树也都分别是二叉搜索树。

主要操作

查找某个数值

若二叉搜索树为空，则查找不成功；否则：

1. 若给定值等于根节点的关键字，则查找成功；
2. 若给定值小于根节点的关键字，则继续在左子树上进行搜索；
3. 若给定值大于根节点的关键字，则继续在右子树上进行搜索。

插入某个数值

插入操作在查找不成功时才进行；

若二叉搜索树为空树，则新插入的节点为根节点；否则，新插入的节点必为一个叶子节点，其插入位置由查找过程得到。

删除某个数值

删除一个节点后，仍是二叉排序树。可分三种情况讨论：

1. 被删除的节点是叶子：其双亲节点中相应指针域的值改为空

   

2. 被删除的节点只有左子树或者只有右子树：可以用结点p的左（右）子树替代结点p的子树，也就是直接用其左（右）孩子替代它（结点替代）。

   

3. 被删除的节点既有左子树，也有右子树：用左孩子的子孙里最大的节点取代被删除节点（间接删除）。

   

代码实现

struct node { 
    int val;
    node *lch, *rch;
};

bool find(node *p, int x) {
    if (p == NULL) return false;
    else if (x == p->val) return true;
    else if (x < p->val) return find(p->lch, x);
    else return find(p->rch, x);
}

node *insert(node *p, int x) {
    if (p == NULL) { 
        node *q = new node;
        q->val = x;
        q->lch = q->rch = NULL;
        return q; 
    }
    else { 
        if (x < p->val) p->lch = insert(p->lch, x);
        else p->rch = insert(p->rch, x);
        return p; 
    }
}

node *remove(node *p, int x) { 
    if (p == NULL) return NULL;
    else if (x < p->val) p->lch = remove(p->lch, x);
    else if (x > p->val) p->rch = remove(p->rch, x);
    else if (p->lch == NULL) { //第一种情况
        node *q = p->rch;
        delete p; 
        return q; 
    }
    else if (p->lch->rch == NULL) {//第二种情况
        node *q = p->lch;
        q->rch = p->rch;
        delete p; 
        return q; 
    }
    else { //第三种情况 
        node *q;
        for (q = p->lch; q->rch->rch != NULL; q = q->rch);
        node *r = q->rch;
        q->rch = r->lch;
        r->lch = p->lch;
        r->rch = p->rch;
        delete p;
        return r;
    }
    return p;
}

二叉排序树的查找性能

• 给定含n个关键字的集合，假设所有关键字不相同，对应有n!个关键字序列，每个关键字序列构造一棵二叉排序树，所有这些二叉排序树中查找每个关键字的平均时间为$O(log2n)$。

• 给定含n个关键字的关键字序列构造一棵二叉排序树。其中查找性能最好的是高度最小的二叉排序树，最好查找性能为$O(log2n)$。查找性能最坏的是高度为n的二叉排序树（单支树），最坏查找性能为$O(n)$。平均情况由具体的关键字序列来确定。所以常说二叉排序树的时间复杂度在$O(log2n)$和$O(n)$之间，就是指这种分析方法。

• 查找序列（$k_1，k_2，…，k_n$）的查找树画法是，每一层只有一个结点，首先$k_1$为根结点，再依次画出其他结点，若$k_{i+1}<k_i$，则$k_{i+1}$的结点作为$k_i$结点的左孩子，否则作为右孩子。