230428 강의

조사했던 과제처럼 이진탐색트리에 대해서 강의했었습니다. 일단 이진탐색트리는 둘 중에 한 곳으로 내려갑니다. 이진법을 생각하면 0과 1로 2가지만 되어있는 것처럼 이진탐색트리도 둘 중 한 곳만 쓰기 때문에 이진탐색트리라는 이름이 붙었습니다.

이진탐색트리에도 종류가 많지만 완전이진트리에 대해 적어보겠습니다.

 

먼저 완전이진트리는 좌우 반씩 쪼개서 내려갈 수 있습니다. 가장 위에 있는 노드가 루트 노드이고 거기서부터 내려갈 때마다 탐색을 해야 되는 노드의 수는 절반 이하로 줄어들게 됩니다. 그래서 최대 레벨 도달 수는 최하단에 있는 노드가 됩니다. 그렇게 균형 잡힌 트리의 탐색에 유리한 구조가 자료구조 중의 map과 set입니다. 그럼 map과 set에 대해 알아보겠습니다.

 

먼저 map은 검색, 삽입, 삭제가 O(log n)으로 되어있는 레드블랙트리로 되어있습니다. 자료를 저장할 때 내부에서 자동으로 오름차순으로 정렬합니다. key와 데이터를 한 쌍으로 사용하고 중복 데이터 사용이 불가능합니다.

 

다음 set은 map처럼 key를 사용하지 않고 데이터로 접근하며 동적 할당으로 합니다. 하지만 중복 데이터를 사용할 수 없고 내부에서 오름차순으로 정렬되는 건 map과 공통적입니다.

 

만약 중복된 값을 사용하고 싶으면 multimap과 multiset을 사용하면 됩니다.

 

정확한 사용법은 다음 주에 알 수 있을 것 같습니다.

읽어주셔서 감사합니다.