경일 메타버스 20220805 18주차 2일 특강 수업내용. 자료구조와 알고리즘 - 이진 검색 트리

자료 :
https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit#

이진 검색 트리

• STL에서는 std::set, std::map, std::multiset, std::multimap으로 구현이 되어 있다.

  • multi가 붙은 자료구조는 데이터의 중복을 허용한다는 의미

• STL에서는 연관 컨테이너(Associative Container)라고 한다.

  • 이진 검색 트리를 구성하는데 사용하는 키(Key)와 이 키에 연관되는 값(Value)
    의 형태로 구조가 만들어져 있기 때문이다.

• std::set ⇒ 키만 있는 자료구조
  std::map ⇒ 키와 값 둘 다 존재하는 자료구조

• 데이터가 항상 정렬되어야 한다면, 이러한 이진 검색 트리의 사용을 고려해볼 수 있다.

std::set

• 집합

• 키만 있다.

• 예시코드

  2022. 08. 05 std:set 예시 코드

• C# : SortedSet

std::map

• std::set의 사용과 크게 다르지 않다.

• 키와 값을 갖는다.

• 템플릿 파라미터를 두 개 갖는다.

  • 키 타입

  • 값 타입

• 예시 코드

2022. 08. 05 std:map 예시 코드

• C# : SortedDictionary