二叉搜索树

概念

二叉查找树（Binary Search Tree，简称 BST），也称 二叉查找树、有序二叉树、排序二叉树

1. 空树是二叉搜索树
2. 左子树上所有节点的值 小于 根节点的值
3. 右子树上所有节点的值 大于 根节点的值
4. 任意节点的左、右子树也是二叉搜索树

操作

// 结点定义
struct node{
    int val;
    int siz; // 该节点子树大小
    int cnt; // 值为 val 的元素个数，用于处理重复值
    node* lc; // 左孩子指针
    node* rc; // 右孩子指针
    node(){
        val=0;
        cnt=siz=1;
        lc=rc=nullptr;
    }
};

遍历

L 表示遍历 左子树

R 表示遍历 右子树

D 表示访问 根节点

先根遍历（DLR）

void DLR(const node* root){
    if(root==nullptr) return;
    // display root
    DLR(root->lc);
    DLR(root->rc);
}

中根遍历（LDR）

二叉搜索树的 中根遍历序 是有序的

void LDR(const node* root){
    if(root==nullptr) return;
    LDR(root->lc);
    // display root
    LDR(root->rc);
}

后根遍历（LRD）

void LRD(const node* root){
    if(root==nullptr) return;
    LRD(root->lc);
    LRD(root->rc);
    // display root
}

最值查找

二叉搜索树上的最大（小）值为 右（左）链的顶点

node* find_max(node* root){
    if(root->rc==nullptr) return root;
    return find_max(root->rc);
}
node* find_min(node* root){
    if(root->lc==nullptr) return root;
    return find_min(root->lc);
}

插入

void insert(node*& root,int _val){
    if(root==nullptr){ // 找到插入点，插入
        root=new node;
        root->val=_val;
        return;
    }
    root->siz++; 
    // 更新 siz，注意在搜索时更新而不是回溯时更新
    // 更新 siz 之所以放在这里而不是开头或递归搜索前，是因为如果插入新 node，新 node 本身 cnt=1 不用加，放在开头就会多加一个，而如果已存在相同 val 的结点，则还要让这个节点的 cnt++，放在递归前面就会在找到 val 相同的结点后直接 return 掉而不会更新这个结点的 siz 了
    // 当然，也可以把 siz 更新语句写在下面的 if 循环里面，再把 root->siz++ 放到递归前面
    if(root->val==_val){ // 已存在 val，cnt++
        root->cnt++;
        return;
    }
    if(_val<root->val) return insert(root->lc,_val); // 递归搜索左子树，找插入点
    if(_val>root->val) return insert(root->rc,_val); // 递归搜索右子树，找插入点
}

删除

void left_del(node*& target,node*& root){
    if(root->lc==nullptr){
        swap(target->val,root->val);
        delete root;
        root=nullptr;
        return;
    }
    return left_del(target,root->lc);
}
void del(node*& root,int _val){
    if(root==nullptr) return;
    if(_val==root->val){
        if(root->cnt>1){
            root->cnt--;
            return;
        }
        if(root->lc==nullptr){
            if(root->rc==nullptr){
            // C1: lc=rc=nil（叶子节点）
                delete root;
                root=nullptr;
                return;
            }
            // C2: lc=nil rc!=nil（链节点）
            delete root;
            root=root->rc;
            return;
        }
        if(root->rc==nullptr){
        // C3: lc!=nil rc=nil（链节点）
            delete root;
            root=root->lc;
            return;
        }
        // C4: lc,rc!=nil（左右子节点均非空）
        // 使用 find_max 或 find_min 函数将难以置空父指针，故直接写一个递归删除函数
        left_del(root,root);
        return;
    }
    // 删除时，结点直接被删掉，不用考虑当前节点 siz 更新的问题，与插入一样，选择在搜索时更新而不是回溯时更新
    root->siz--;
    if(_val<root->val) del(root->lc,_val);
    if(_val>root->val) del(root->rc,_val);
}

计算各结点子树大小

void calc_siz(node*& root){ // 计算各节点子树大小
// 注意递归边界不能用 root==nullptr，因为这样回溯后 root 左右子节点均为空，无法计算 siz
    if(root->lc==nullptr){
        if(root->rc==nullptr){ // lc=rc=nil
            return;
        }
        // lc=nil rc!=nil
        calc_siz(root->rc);
        root->siz+=root->rc->siz;
        return;
    }
    if(root->rc==nullptr){ // lc!=nil rc=nil
        calc_siz(root->lc);
        root->siz+=root->lc->siz;
        return;
    }
    // lc,rc!=nil
    calc_siz(root->lc);
    root->siz+=root->lc->siz;
    calc_siz(root->rc);
    root->siz+=root->rc->siz;
    return;
}

求元素排名

定义：某个元素的排名指的是 小于该元素的元素个数 +1

int calc_rank(const node* root,int _val){
    // 根节点的 rank 只与其左子树大小有关
    // 对根节点的右孩子，有三部分比他小，1. 根节点的左子树 2. 根节点本身 3. 这个右孩子自己的左子树

    // 找到要求的结点，如果其左子树非空，则其左子树上所有结点都比它小，注意根据定义加一
    if(_val==root->val) return root->lc==nullptr ? 1 : root->lc->siz+1;
    // 从左侧回溯，回溯路上结点都比它大，不满足要求
    if(_val<root->val)  return calc_rank(root->lc,_val);
    // 从右侧回溯，回溯路上每个结点及其左子树都比它小
    if(_val>root->val)  return calc_rank(root->rc,_val)+root->lc->siz+root->cnt;
}

求排名为 k 的元素

node* get_kth(node* root,int k){
    // 首先，一个元素的排名定义为比他小的数的个数+1
    // 因此在一颗子树中，根节点的排名取决于其左子树的大小
    // 搜索中，考虑状态转移，如果向左儿子继续搜索，小于它的元素不发生改变
    // 如果向右儿子继续搜索，则根节点 根节点左子树所有元素都比它小，要从排名中减去
    if(root->lc==nullptr){
        if(k-1==0) return root;
        return nullptr;
    }
    if(root->lc->siz>k-1) return get_kth(root->lc,k);
    if(root->lc->siz+root->cnt<=k-1) return get_kth(root->rc,k-root->lc->siz-root->cnt);
    return root;
}

评论