이진 검색 트리의 단점:
이진 검색 트리 자체를 구현하는 것에 실수할 여지가 많고 자가 균형 트리가 적용되지 않은 이진 검색 트리는 시간복잡도가 안좋아서 높은 확률로 시간 초과가 발생하게 된다. 따라서, STL을 사용할 수 없는 환경에서의 이진 검색 트리를 사용하려고 노력하지 말자.
이진 트리 정의
이진 검색 트리를 정의하기 이전에 전에 공부했었던 이진 트리의 정의를 다시 떠올려보자.
각 노드의 자식이 2개 이하인 트리를 말합니다. 자식이 2개 이하이기 때문에 왼쪽 자식과 오른쪽 자식을 구별할 수 있다.
이진 검색 트리의 정의
왼쪽 서브트리의 모든 값은 모든 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리이다.
이진 검색 트리의 장점
순차적인 원소에 접근하게 된다면, 배열이나 연결 리스트를 활용하면 되지 않느냐? 라는 의문이 들 수 있다.
이진 검색 트리를 활용하게 된다면, insert, update, find, erase를 모두 O(lgN) 실행동안 처리할 수 있다.
즉, 프로그램의 실행의 erase, update가 자주 실행되어질수록 이진 검색 트리를 활용할수록 좋다.
또한, 원소 크기각 순차적으로 정렬된다는 특징은 순차적이지 않은 원소의 위치나 크기를 O(lgN) 실행시간동안 빠르게
찾아낼 수 있다는 장점이 존재한다.
하지만 우측 트리의 그래프가 다음과 같이 편향되는 모습을 보인다면 어떻게 해야할까?
우리는 O(lgN)에 수행하기 위해 이진 트리를 사용하게 되는데 다음과 같이 연결 리스트와 별반 차이가 나지 않게 되었을 때 이진 트리를 쓰게 되는 이유가 없어지게 된다. 순차적인 값들이 노드에 삽입되는 경우에 편향된 그래프 트리가 만들어지게 되기 떄문에 해당 사항을 해결하기 위한 방법을 고민해야한다.
이를 해결하기 위해, 자가 균형 트리가 나왔다!
이러한, 트리를 자가 균형 트리(Self-Balancing Tree)라고 부르는데 대표적으로 AVL 트리, Red Black 트리가 있다.
극단적으로 얘기를 하자면, 트리 자체를 꺽어버리는 방식이다. 이러한, 이진 검색트리는 STL의 해시를 통해 단순히 구현할 수 있게 된다.
STL에 구현된 해시에는 unorered_set, unordered_multiset, unordered_map가 존재한다.
.
Set
void set_example(){
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'; // {-10, 15}, 1
cout << s.erase(20) << '\n'; // {-10, 15}, 0
if(s.find(15) != s.end()) cout << "15 in s\n";
else cout << "15 not in s\n";
cout << s.size() << '\n'; // 2
cout << s.count(50) << '\n'; // 0
for(auto e : s) cout << e << ' ';
cout << '\n';
s.insert(-40); // {-40, -10, 15}
set<int>::iterator it1 = s.begin(); // {-40(<-it1), -10, 15}
it1++; // {-40, -10(<-it1), 15}
auto it2 = prev(it1); // {-40(<-it2), -10, 15}
it2 = next(it1); // {-40, -10, 15(<-it2)}
advance(it2, -2); // {-40(<-it2), -10, 15}
auto it3 = s.lower_bound(-20); // {-40, -10(<-it3), 15}
auto it4 = s.find(15); // {-40, -10, 15(<-it4)}
cout << *it1 << '\n'; // -10
cout << *it2 << '\n'; // -40
cout << *it3 << '\n'; // -10
cout << *it4 << '\n'; // 15
}
multiset
void multiset_example(){
multiset<int> ms;
// {-10, 15, 100}
ms.insert(-10); ms.insert(100); ms.insert(15); // {-10, -10, 15, 15, 100}
ms.insert(-10); ms.insert(15);
cout << ms.size() << '\n'; // 5
for(auto e : ms) cout << e << ' ';
cout << '\n';
cout << ms.erase(15) << '\n'; // {-10, -10, 100}, 2
ms.erase(ms.find(-10)); // {-10, 100}
ms.insert(100); // {-10, 100, 100}
cout << ms.count(100) << '\n'; // 2
auto it1 = ms.begin(); // {-10(<-it1), 100, 100}
auto it2 = ms.upper_bound(100); // {-10, 100, 100} (<-it2)
auto it3 = ms.find(100); // {-10, 100(<-it3), 100}
cout << *it1 << '\n'; // -10
cout << (it2 == ms.end()) << '\n'; // 1
cout << *it3 << '\n'; // 100
}map
void map_example(){
map<string, int> m;
m["hi"] = 123;
m["bkd"] = 1000;
m["gogo"] = 165; // ("bkd", 1000), ("gogo", 165), ("hi", 123)
cout << m.size() << '\n'; // 3
m["hi"] = -7; // ("bkd", 1000), ("gogo", 165), ("hi", -7)
if(m.find("hi") != m.end()) cout << "hi in m\n";
else cout << "hi not in m\n";
m.erase("bkd"); // ("gogo", 165), ("hi", 123)
for(auto e : m)
cout << e.first << ' ' << e.second << '\n';
auto it1 = m.find("gogo");
cout << it1->first << ' ' << it1->second << '\n'; // gogo 165
}
