Computer Science/Data Structures

개요 얼마 전 백준에서 집합 자료형을 구현하는 문제를 보았습니다. 직접 구현하라고 하면 가물가물하면서 `std::set` 같은 컨테이너를 쓰는 것이 양심에 찔려서, 자료구조 공부도 다시 시작했습니다. 오늘은 가장 먼저 이진 탐색 트리(Binary Search Tree)를 살펴봅니다. 이진 탐색 트리란 정의와 성질 이진 탐색 트리는 이진 트리면서, 다음과 같은 재귀적인 성질을 가진 트리입니다. 이진 탐색 트리의 성질 노드를 기준으로 왼쪽 트리에 있는 노드들은 더 작은 키(key)를 가진다. 오른쪽 트리에 있는 노드들은 더 큰 키를 가진다. 성질에서 알 수 있듯, 이진 탐색 트리는 키-값(key-value)의 데이터를 저장하는 자료구조입니다. 이 글에서는 편의상 키와 값은 모두 정수이며, 두 값이 같다고 가..