이진 검색 트리

이진 검색 트리

정의와 성질

• 정점(Vertex/Node): 트리에서 각 원소
• 루트(Root): 트리에서 가장 꼭대기의 정점
• 리프(leaf): 제일 말단에 위치해 자식이 없는 정점
• 간선(Edge): 정점을 연결하는 선
• 이진 트리(Binary Tree): 각 노드의 자식이 2개 이하인 트리
• 이진 검색 트리(Binary Search Tree): 왼쪽 서브트리의 모든 값은 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리
• insert,erase,find,update: O(lgN)
• 원소가 크기 순으로 정렬되어 있음

  자가 균형 트리

• AVL트리, Red Black트리
• STL에 있는 이진 검색 트리는 Red Black트리 이용

  Tip

• unordered_set, unordered_map이 평균적으로 set,map보다 빠름 하지만 unordered_set, unordered_map은 충돌이 빈번하면 속도의 저하가 발생할 수 있음(O(N)이 될 수 있음)
• set, map의 경우 O(lgN)이지만 같은 O(lgN)알고리즘들과 비교해서 많이 느림

  STL

• Set

  #include<iostream>
  #include<set>
  using namespace std;
  int main(void){
    set<int> s;
    s.insert(-10);
    s.insert(100);
    s.insert(15);// {-10,15,100}
    s.insert(-10);// {-10,15,100}
    cout<<s.erase(100)<<'\n'; // 출력: 1 {-10,15}
    cout<<s.erase(20)<<'\n'; // 출력: 0 {-10,15}
    if(s.find(15)!=s.end()){
        cout<<"yes\n";
    }
    else{
        cout<<"no\n";
    }
    cout<<s.size()<<'\n'; // 2
    cout<<s.count(50)<<'\n';// 0
    for(auto e: s){
        cout<<e<<' '; //-10 15
    }
    cout<<'\n';
    s.insert(-40); // {-40,-10,15}
    set<int>::iterator it1 = s.begin();// {-40,-10,15}
    it1++;
    auto it2=prev(it1);
    it2=next(it1);
    advance(it2,-2); // 한 칸 움직일때 O(lgN) 현재는 O(lgN)*2
    auto it3 = s.lower_bound(-20);
    auto it4 = s.find(15);
    cout<<*it1<<'\n';// -10
    cout<<*it2<<'\n';// -40
    cout<<*it3<<'\n';// -10
    cout<<*it4<<'\n';// 15
    return 0;
  }
  

• Multiset

  #include<iostream>
  #include<set>
  using namespace std;
  int main(void){
    multiset<int> ms;
    ms.insert(-10);
    ms.insert(100);
    ms.insert(15);// {-10,15,100}
    ms.insert(-10);// {-10,-10,15,100}
    ms.insert(15);// {-10,-10,15,15,100}
    cout<<ms.size()<<'\n';// 5
    for(auto e:ms){
        cout<<e<<' '; // -10 -10 15 15 100
    }
    cout<<'\n';
    cout<<ms.erase(15)<<'\n'; // 출력: 2 {-10,-10,100}
    ms.erase(ms.find(-10)); //{-10,100}
    ms.insert(100);//{-10,100,100}
    cout<<ms.count(100)<<'\n';// 2
    auto it1 = ms.begin();
    auto it2 = ms.upper_bound(100);
    auto it3 = ms.find(100);
    cout<<*it1<<'\n';// -10
    cout<<(it2==ms.end())<<'\n';// 1 end를 가리키고 있으므로 *it2를 출력하면 에러 발생
    cout<<*it3<<'\n';// 100
    return 0;
  }
  

• Map

  #include<iostream>
  #include<map>
  using namespace std;
  int main(void){
    map<string,int> m;
    m["hi"]=123;
    m["bird"]=1000;
    m["gogo"]=165; //{"bird",1000},{"gogo",165},{"hi",123}
    cout<<m.size()<<'\n'; //3
    m["hi"]=-7; //{"bird",1000},{"gogo",165},{"hi",-7}
    if(m.find("hi")!=m.end()){
        cout<<"yes\n";
    }
    else{
        cout<<"no\n";
    }
    m.erase("bird");//{"gogo",165},{"hi",-7}
    for(auto e:m){
        cout<<e.first<<' '<<e.second<<'\n'; //gogo 165
                                            //hi -7
    }
    auto it1 = m.find("gogo");
    cout<<it1->first<<' '<<it1->second<<'\n';// gogo 165
    return 0;
  }