---
tags: codebook
---
{%hackmd theme-dark %}
# Binary search tree

## 概念
1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值
2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於或等於它的根節點的值
3. 任意節點的左、右子樹也分別為二元搜尋樹

## 範例

digraph tree{
    node[fontcolor = white;color=white]
    edge[color=white]
    bgcolor = "#343434"
    8 -> {3 10}
    3 -> {1  6}
    6 -> {4  7}
    10 -> {tmp1[label=nul] 14}
    14 -> {tmp2[label=nul] 13}
    1->{tmp3[label=nul] tmp4[label=nul]}
    4->{tmp5[label=nul] tmp6[label=nul]}
    7->{tmp7[label=nul] tmp8[label=nul]}
    13->{tmp10[label=nul] tmp9[label=nul]}
}

#include<iostream>
#include<vector>
#include<random>
#include<numeric>
#include<utility>
#include<ctime>
using namespace std;

mt19937 rd;
template<typename T>
struct bst{
    struct node{
        using nptr=node*;
        T v; nptr l,r;
        node(const T& x):v(x){l=r=nullptr;}
    } *root;
    using nptr=node*;
    void print(ostream& os,nptr cur){
        if(!cur) return;
        print(os,cur->l);
        os<<cur->v<<' ';
        print(os,cur->r);
    }
    void print(ostream& os){print(os,root);}
    nptr merge(nptr a,nptr b){
        if(!a) return b;
        if(!b) return a;
        if(rd()&1){
            a->r=merge(a->r,b);return a;
        }else{
            b->l=merge(a,b->l);return b;}
    } 
    bst merge(bst b){
        root=merge(root,b.root);return *this;
    }
    void split(nptr cur,const T& x,nptr& a,nptr& b){
        if(!cur){a=b=nullptr;return;}
        if(cur->v<x)
            a=cur,split(a->r,x,a->r,b);
        else
            b=cur,split(b->l,x,a,b->l);
    }
    auto split(const T& x){
        bst a,b;
        split(root,x,a.root,b.root);
        return make_pair(a,b);
    }
    void insert(const T& x,nptr& cur){
        if(!cur) cur=new node(x);
        else if(cur->v==x) return;
        else insert(x,(x<cur->v?cur->l:cur->r));
    }
    void insert(const T& x){insert(x,root);}
    void erase_r(nptr& rt,nptr& cur){
        if(!cur) rt=rt->l;
        else if(cur->l) erase_r(rt,cur->l);
        else rt->v=cur->v,cur=cur->r;
    }
    void erase(const T& x,nptr& cur){
        if(!cur) return;
        if(cur->v==x) erase_r(cur,cur->r);
        else erase(x,(x<cur->v?cur->l:cur->r));
    }
    void erase(const T& x){erase(x,root);}
    bool count(const T& x,node* cur){
        if(!cur) return false;
        else if(cur->v==x) return true;
        else return count(x,(x<cur->v?cur->l:cur->r));
    } 
    bool count(const T& x){return count(x,root);}
    bst(const vector<T>& v={}):root(nullptr){
        for(const auto& i:v) insert(i);
    }
};
ostream& operator<<(ostream& os,const vector<T>& v){
    for(const auto& i:v) os<<i <<' ';
    return os;
}
ostream& operator<<(ostream& os,bst t){
    t.print(os);return os;
}