이진 트리 vs 이진 검색 트리
이진 트리
한 노드의 자식 노드가 두 개 이하인 트리
이진 검색 트리
왼쪽 서브트리의 모든 값은 부모의 값보다 작고, 오른쪽 서브트리의 모든 값은 부모보다 큰 이진 트리
성능
insert, erase, find, update 네개의 연산 모두 O(log N) 시간 복잡도를 갖는다
배열 vs 이진 검색 트리
배열은 insert는 O(1), erase, find, update 는 O(N) 시간을 가진다.
따라서 erase, find, update 연산이 잦은 경우 배열보다 이진 검색 트리를 활용하는 것이 좋다.
해시 vs 이진 검색 트리
해시는 충돌 때문에 성능이 저하될 수는 있지만 모든 연산의 시간 복잡도가 O(1) 으로 빠른 연산이 가능하다.
하지만 해시는 원소가 정렬되어 있지 않고 이진 검색 트리는 원소가 정렬되어 있다는 장점을 가지고 있다.
따라서 원소의 대소 관계를 파악할 필요가 있는 경우에는 이진 검색 트리를 활용하는 것이 좋다.
Erase
자식이 없는 노드를 제거하는 경우
해당 노드를 그냥 제거하면 된다
자식이 1개인 노드를 제거하는 경우
해당 노드를 제거하고 자식 노드가 그 자리를 대신하게 한다
자식이 2개인 노드를 제거하는 경우!
해당 노드의 오른쪽 트리에서 가장 작은 값, 또는 해당 노드의 왼쪽 트리에서 가장 큰 값으로 그 자리를 대신하도록 한다.
자가 균형 트리
모든 연산의 성능이 트리의 높이에 달려 있기 때문에, 트리가 한쪽으로 치우쳐 있으면 성능이 저하될 수 있다.
즉, 자가 균형 트리일 때 이진 검색 트리의 연산 속도가 O(logN)으로 보장된다.
그래서 트리의 높이를 조정하는 자가 균형 트리가 필요하다.
자가 균형 트리의 종류에는 대표적으로 AVL 트리, Red Black 트리가 있다.
STL
set
오름차순으로 정렬되어 있다
size, end, begin : O(1)
insert, erase, find, lower_bound, next, prev : O(log N)
advance
advance(설정하려는 iter, 이동하고 싶은 숫자)
advance는 한칸을 이동하는데에 O(logN) 이므로 advance(it, 100); 은 O(logN) 연산을 100번 수행할 수 있어서 주의해서 사용해야 한다
end
마지막 원소의 iterator를 반환하는게 아니라 마지막 원소의 다음 iterator를 반환하므로 주의해서 사용해야 한다
prev(T.begin()) 과 같이 마지막 원소에 접근할 수 있다
set 순회하기
c에서 배열 순회하는 것처럼 순회하려고 했으나, 배열처럼 순서대로 메모리에 있는 것이 아니어서 컴파일이 되지 않았다
- 올바르지 않은 형태 :
for (auto iter = D.begin(); iter < D.end(); iter++) - 올바른 형태 :
for (auto iter = D.begin(); iter != D.end(); iter++)
역순으로 순회하는 것도 위와 같은 이유로 불가능했다
그래서 찾아보니 rbegin(), rend() 함수를 활용해서 아래와 같이 순회할 수 있었다
for (auto iter = D.rbegin(); iter != D.rend(); iter++)
multiset
map
key를 기준으로 오름차순 정렬되어 있다
