C++ 資料結構 Binary Search Tree

Binary Search Tree (二元搜尋樹)，是用來存放多筆資料，並快速搜尋的資料結構。大概的原則就是，大的放右邊，小的放左邊。

新增，刪除一個值都只要O(log(N))

以下為實作範例

#include
using namespace std;

template
class bst{
    private:
        struct node{
            T val;
            node* l,r;

            node(){
                l=r=nullptr;
            }
            node(T v){
                l=r=nullptr;
                val=v;
            }
        };

        bool find(node *n,T v){
            if(n->val==v){
                return true;
            }else if(n->val > v && n->r!=nullptr){
                find(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                find(n->l,v);
            }else{
                return false;
            }
        }

        void insert(node *&n,T v){
            if(n==nullptr){
                node nd=new node(v);
                n=&nd;
            }else if(n->val > v && n->r!=nullptr){
                insert(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                insert(n->l,v);
            }
        }

        void DeleteNode(node *&n){
            if(n->l==nullptr && n->r==nullptr){
                delete n;
                n=nullptr;
            }else{
                node *left,*right;
                if(n->l==nullptr){
                    right=n->r;
                    n->val=right->val;
                    n->l=right->l;
                    n->r=right->r;
                    delete right;
                }else if(n->r==nullptr){
                    left=n->l;
                    n->val=left->val;
                    n->l=left->l;
                    n->r=left->r;
                    delete left;
                }else{
                    right=n;
                    left=n->l;
                    while(left->r!=nullptr){
                        right=left;
                        left=left->l;
                    }
                    n->val=left->val;
                    if(right!=n)
                        right->r=left->l;
                    else
                        right->l=left->l;
                    delete left;
                }
            } 
        }

        void erase(node *n,T v){
            if(n->val==v){
                DeleteNode(n);
            }else if(n->val > v && n->r!=nullptr){
                erase(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                erase(n->l,v);
            }
        }

        void DeleteTree(node *n){
            if(n->l!=nullptr)
                DeleteTree(n->l);
            if(n->r!=nullptr)
                DeleteTree(n->r);
            delete n;
        }
    public:
        bst(){
            root=nullptr;
            sz=0;
        }

        ~bst(){
            if(root!=nullptr)
                DeleteTree(root);
        }

        bool find(T v){
            if(root!=nullptr)
                return find(root,v);
        }

        void insert(T v){
            if(root==nullptr){
                node n=new node(v);
                root=&n;
            }else{
                insert(root,v);
            }
            sz++;
        }

        void erase(T v){
            if(root==nullptr) return;
            erase(root,v);
            sz--;
        }

        int size(){
            return sz;
        }
    private:
        node *root;
        int sz;
};

相同的，C++都幫你做好了，就是所謂的Set & Map。

以下為使用範例

#include
using namespace std;

int main(){
    vector v(100);
    for(int i=0;i<100;++i){
        v[i]=i;
    }
    random_shuffle(v.begin(),v.end());

    set s;
    for(auto a:v){
        s.insert(a);
    }

    random_shuffle(v.begin(),v.end());

    for(auto a:v){
        cout<<*s.lower_bound(a)<<" ";
        cout<<*s.upper_bound(a)<<"\n";
    }
    s.erase(10);
    cout<<*s.lower_bound(10);
}

我相信許多人跟我一樣，一開始不知道這些東西要用在哪？

以下我找了幾個範例

1. 在O(Nlog(26))以內找出是否有一個字母在兩個字串中均能被找到(題目連結：Two Strings | HackerRank)

string twoStrings(string s1, string s2) {
    set s;
    for(auto a:s1){
        s.insert(a);
    }
    for(auto a:s2){
        if(s.count(a)){
            return "YES";
        }
    }
    return "NO";
}

2. 以O(N^3log(N))找出一個字串中無序變形子串對的數目(題目連結：Sherlock and Anagrams | HackerRank) 最重要的，就是其刪除快速的特性

int sherlockAndAnagrams(string s) {
    int ct=0,len=s.size();
    for(int i=0;i st,tt;
            for(int k=i;k<=j;k++){
                st.insert(s[k]);
                tt.insert(s[k]);
            }

            for(int k=i+1;k

vector freqQuery(vector> q) {
    vector ans;
    map m,ct;
    for(auto a:q){
        if(a[0]==1){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]++;
            ct[m[a[1]]]++;
        }else if(a[0]==2){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]=max(m[a[1]]-1,0);
            ct[m[a[1]]]++;
        }else{
            ans.push_back(bool(ct[a[1]]));
        }
    }
    return ans;
}