[2026.05.22] - TIL 36일차 정렬 알고리즘, 색인, 이진 검색 트리, 그래프 정리

목차
1 정렬
2 삽입 정렬
3 선택 정렬
4 퀵 정렬
5 병합 정렬
6 버블 정렬
7 색인
8 트리
9 이진 검색 트리
10 BinarySearchTree 클래스 구조
11 이진 검색 트리 검색 기능
12 이진 검색 트리 추가 기능
13 이진 검색 트리 삭제 기능
14 이진 검색 트리 출력 기능
15 그래프

1 정렬

1) 정렬의 개념

    (1) 정렬
    정렬은 데이터 집합을 특정 기준에 따라 순서대로 재배열하는 과정이다.
    숫자를 작은 순서대로 나열하거나, 이름을 가나다순으로 정리하는 것처럼 데이터를 보기 좋고 찾기 쉽게 만드는 작업이다.

    (2) 정렬을 사용하는 이유
    정렬된 데이터는 검색과 분석이 훨씬 쉬워진다.
    예를 들어 점수를 높은 순서대로 정렬하면 상위권을 쉽게 확인할 수 있고, 이름을 가나다순으로 정렬하면 특정 사람을 더 빠르게 찾을 수 있다.

    (3) 정렬 기준
    정렬 기준에는 오름차순과 내림차순이 있다.
    오름차순은 작은 값에서 큰 값으로 정렬하는 방식이고, 내림차순은 큰 값에서 작은 값으로 정렬하는 방식이다.

2) 정렬 알고리즘

    (1) 정렬 알고리즘의 의미
    정렬 알고리즘은 데이터를 어떤 방식으로 정렬할지 정해놓은 절차이다.
    같은 결과를 만들더라도 알고리즘에 따라 비교 횟수, 교환 횟수, 실행 속도, 메모리 사용량이 달라진다.

    (2) 정렬 알고리즘을 배우는 이유
    데이터의 크기와 상황에 따라 적합한 정렬 방식이 다르다.
    작은 데이터에서는 단순한 정렬도 충분하지만, 데이터가 많아지면 퀵 정렬이나 병합 정렬처럼 효율적인 알고리즘이 필요하다.

    (3) 주요 정렬 알고리즘
    오늘 실습에서는 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬, 버블 정렬을 다루었다.
    각각 데이터를 비교하고 이동시키는 방식이 다르기 때문에 흐름을 구분해서 이해하는 것이 중요하다.

2 삽입 정렬

단순삽입정렬

1) 삽입 정렬의 개념

    (1) 삽입 정렬
    삽입 정렬은 현재 선택한 요소를 앞쪽의 알맞은 위치에 끼워 넣는 정렬 방식이다.
    이미 정렬된 부분을 기준으로 새 값을 적절한 위치에 삽입하면서 정렬 범위를 넓혀간다.

    (2) 카드 정리와 비슷한 방식
    삽입 정렬은 손에 든 카드를 순서대로 정리하는 방식과 비슷하다.
    새 카드를 하나 뽑고, 이미 정렬된 카드들 사이에서 알맞은 자리를 찾아 끼워 넣는 방식이다.

    (3) 사용 상황
    데이터가 거의 정렬되어 있는 경우 삽입 정렬은 비교적 효율적으로 동작할 수 있다.
    구조가 단순해서 정렬의 기본 원리를 이해하기 좋다.

2) 삽입 정렬 코드 흐름

    (1) i의 역할
    i는 현재 삽입할 대상을 가리키는 인덱스이다.
    0번째 요소는 이미 정렬되어 있다고 가정하고, 1번째 요소부터 차례대로 정렬 위치를 찾는다.

    (2) tmp의 역할
    tmp는 현재 선택한 요소를 임시로 저장하는 변수이다.
    앞쪽 요소들을 뒤로 밀면 현재 값이 덮어써질 수 있기 때문에 tmp에 먼저 보관한다.

    (3) j의 역할
    j는 현재 선택한 요소가 들어갈 위치를 찾기 위해 앞쪽으로 이동하는 인덱스이다.
    tmp보다 큰 값이 있으면 그 값을 한 칸 뒤로 밀면서 빈자리를 만든다.

    (4) 삽입 과정
    tmp보다 큰 값들을 뒤로 밀고, 더 이상 밀 필요가 없는 위치에 tmp를 넣는다.
    이 과정을 반복하면 왼쪽부터 점점 정렬된 구간이 늘어난다.

3) 삽입 정렬의 핵심

    (1) 앞쪽은 정렬된 상태라고 가정
    삽입 정렬은 현재 위치 기준으로 앞쪽 데이터들이 이미 정렬되어 있다고 보고 동작한다.
    그래서 현재 값을 앞쪽 정렬 구간의 알맞은 위치에 넣는 방식으로 진행된다.

    (2) 큰 값은 뒤로 이동
    현재 선택한 값보다 큰 값들은 한 칸씩 뒤로 이동한다.
    이동이 끝나면 생긴 빈자리에 현재 값을 넣는다.

    (3) 정렬 결과
    반복이 끝나면 배열 전체가 오름차순으로 정렬된다.
    실습 코드에서는 6, 4, 1, 7, 5, 3, 9, 8 배열이 작은 값부터 큰 값 순서로 정렬된다.

3 선택 정렬

선택정렬

1) 선택 정렬의 개념

    (1) 선택 정렬
    선택 정렬은 아직 정렬되지 않은 부분에서 가장 작은 값을 선택해 앞쪽으로 보내는 정렬 방식이다.
    가장 작은 값을 찾아 현재 위치와 교환하면서 정렬을 진행한다.

    (2) 선택 정렬을 사용하는 이유
    동작 방식이 단순해서 정렬 과정을 이해하기 쉽다.
    매번 최솟값을 찾아 앞에 배치한다는 흐름이 명확하다.

    (3) 선택 정렬의 특징
    선택 정렬은 비교를 많이 하지만 교환은 비교적 적게 일어난다.
    그러나 데이터가 많아질수록 전체를 반복해서 탐색해야 하므로 효율이 떨어질 수 있다.

2) 선택 정렬 코드 흐름

    (1) i의 역할
    i는 현재 최솟값을 넣을 위치를 의미한다.
    i가 0이면 배열의 첫 번째 자리에 들어갈 가장 작은 값을 찾는다.

    (2) min의 역할
    min은 가장 작은 값 자체가 아니라 가장 작은 값이 있는 인덱스를 저장한다.
    처음에는 현재 위치 i가 가장 작다고 가정하고 시작한다.

    (3) j의 역할
    j는 i 다음 위치부터 끝까지 이동하면서 더 작은 값이 있는지 찾는다.
    더 작은 값을 찾으면 min을 그 위치로 바꾼다.

    (4) swap
    최솟값의 위치를 찾은 뒤 현재 위치 i의 값과 min 위치의 값을 교환한다.
    이 과정을 반복하면 앞쪽부터 하나씩 정렬이 확정된다.

3) 선택 정렬의 핵심

    (1) 가장 작은 값 선택
    선택 정렬은 이름 그대로 매번 가장 작은 값을 선택한다.
    선택한 값을 현재 정렬 위치로 이동시킨다.

    (2) 마지막 요소는 자동 정렬
    마지막 하나의 요소만 남으면 이미 앞의 요소들이 정렬된 상태이므로 자동으로 정렬된 상태가 된다.
    그래서 반복은 배열 길이보다 하나 적게 수행해도 된다.

    (3) 정렬 결과
    실습 코드에서는 6, 4, 8, 5, 2, 10, 7 배열에서 가장 작은 값들을 차례로 앞으로 보내 오름차순 정렬을 만든다.

4 퀵 정렬

퀵 정렬

1) 퀵 정렬의 개념

    (1) 퀵 정렬
    퀵 정렬은 피벗을 기준으로 데이터를 작은 값 그룹과 큰 값 그룹으로 나눈 뒤, 각 그룹을 다시 정렬하는 방식이다.
    데이터를 계속 분할하면서 정렬하는 대표적인 분할 정복 알고리즘이다.

    (2) 피벗
    피벗은 데이터를 나눌 기준값이다.
    피벗보다 작은 값은 왼쪽으로, 피벗보다 큰 값은 오른쪽으로 보내는 것이 기본 흐름이다.

    (3) 퀵 정렬을 사용하는 이유
    퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘 중 하나이다.
    데이터가 많을 때도 효율적으로 동작하는 경우가 많다.

2) 퀵 정렬 코드 흐름

    (1) left와 right
    left는 정렬할 구간의 시작 위치이고, right는 정렬할 구간의 끝 위치이다.
    퀵 정렬은 배열 전체가 아니라 특정 구간을 기준으로 재귀적으로 정렬한다.

    (2) lc와 rc
    lc는 왼쪽에서 오른쪽으로 이동하는 커서이고, rc는 오른쪽에서 왼쪽으로 이동하는 커서이다.
    두 커서는 피벗을 기준으로 위치가 잘못된 값을 찾기 위해 움직인다.

    (3) x의 역할
    x는 피벗 값이다.
    실습 코드에서는 현재 구간의 가운데 값을 피벗으로 선택한다.

    (4) 왼쪽 커서 이동
    a[lc]가 피벗보다 작으면 이미 왼쪽 그룹에 있어도 되는 값이므로 lc를 오른쪽으로 이동한다.
    피벗보다 크거나 같은 값을 만나면 멈춘다.

    (5) 오른쪽 커서 이동
    a[rc]가 피벗보다 크면 이미 오른쪽 그룹에 있어도 되는 값이므로 rc를 왼쪽으로 이동한다.
    피벗보다 작거나 같은 값을 만나면 멈춘다.

    (6) 값 교환
    lc와 rc가 멈췄다는 것은 왼쪽에는 큰 값이 있고 오른쪽에는 작은 값이 있다는 뜻이다.
    두 값을 교환하면 피벗 기준으로 위치가 더 알맞게 정리된다.

3) 퀵 정렬의 재귀 구조

    (1) 분할 완료
    lc와 rc가 엇갈리면 현재 구간은 피벗 기준으로 왼쪽 그룹과 오른쪽 그룹으로 나뉜 상태이다.
    이때부터 각 그룹을 다시 정렬한다.

    (2) 왼쪽 그룹 정렬
    left가 rc보다 작으면 왼쪽 그룹에 아직 정렬할 데이터가 남아 있는 것이다.
    quickSort를 다시 호출해 왼쪽 그룹을 정렬한다.

    (3) 오른쪽 그룹 정렬
    right가 lc보다 크면 오른쪽 그룹에 아직 정렬할 데이터가 남아 있는 것이다.
    quickSort를 다시 호출해 오른쪽 그룹을 정렬한다.

    (4) 정렬 결과
    재귀 호출이 모두 끝나면 배열 전체가 정렬된다.
    큰 문제를 작은 구간 정렬 문제로 나누어 해결하는 방식이다.

5 병합 정렬

병합정렬

1) 병합 정렬의 개념

    (1) 병합 정렬
    병합 정렬은 배열을 반으로 계속 나눈 뒤, 나눈 배열을 정렬하면서 다시 합치는 방식이다.
    퀵 정렬처럼 분할 정복을 사용하는 정렬 알고리즘이다.

    (2) 분할과 병합
    먼저 데이터를 더 이상 나누기 어려울 때까지 나눈다.
    그다음 작은 조각들을 정렬된 상태로 합치면서 전체 배열을 정렬한다.

    (3) 병합 정렬을 사용하는 이유
    병합 정렬은 안정적인 성능을 보이는 정렬 방식이다.
    다만 병합 과정에서 임시 저장 공간이 필요할 수 있다.

2) 병합 정렬 코드 구조

    (1) buff
    buff는 병합 과정에서 사용할 임시 저장 배열이다.
    원본 배열의 일부를 임시로 저장한 뒤, 다른 부분과 비교하면서 다시 원본 배열에 넣는다.

    (2) mergeSort
    mergeSort는 정렬을 시작하는 메소드이다.
    배열 크기만큼 buff를 만들고, 실제 재귀 정렬은 mSort에게 맡긴다.

    (3) mSort
    mSort는 left부터 right까지의 구간을 정렬한다.
    left가 right보다 작을 때만 더 나누고 병합을 진행한다.

3) 병합 정렬 코드 흐름

    (1) center 계산
    center는 현재 구간을 반으로 나누는 기준 위치이다.
    left와 right의 중간값으로 구한다.

    (2) 왼쪽과 오른쪽 나누기
    mSort를 왼쪽 구간과 오른쪽 구간에 각각 재귀 호출한다.
    이 과정에서 배열은 계속 반씩 나뉜다.

    (3) 왼쪽 구간 복사
    왼쪽 구간의 값들을 buff에 복사한다.
    이후 오른쪽 구간과 buff에 저장된 왼쪽 구간을 비교하면서 병합한다.

    (4) 비교하며 병합
    buff의 값과 오른쪽 구간의 값을 비교해 더 작은 값을 원본 배열에 넣는다.
    이렇게 하면 병합되는 과정에서 정렬된 상태가 유지된다.

    (5) 남은 값 복사
    오른쪽 구간이 먼저 끝나고 buff에 값이 남아 있으면 남은 값을 원본 배열에 복사한다.
    병합이 끝나면 해당 구간은 정렬된 상태가 된다.

6 버블 정렬

1) 버블 정렬의 개념

    (1) 버블 정렬
    버블 정렬은 인접한 두 요소를 비교해서 순서가 잘못되어 있으면 서로 교환하는 정렬 방식이다.
    큰 값이 반복 과정에서 점점 뒤쪽으로 밀려나는 구조이다.

    (2) 이름의 의미
    큰 값이 거품처럼 오른쪽으로 떠오르듯 이동한다고 해서 버블 정렬이라고 부른다.
    비교와 교환을 반복하면서 정렬이 진행된다.

    (3) 버블 정렬의 특징
    구현이 쉽고 동작 원리가 직관적이다.
    하지만 데이터가 많아지면 비교와 교환이 많이 발생해 비효율적일 수 있다.

2) 뒤에서부터 비교하는 방식

    (1) bubbleSort
    첫 번째 방식은 배열의 뒤쪽에서 앞쪽으로 이동하며 인접한 두 값을 비교한다.
    작은 값을 앞쪽으로 보내면서 정렬을 진행한다.

    (2) swap
    앞의 값이 뒤의 값보다 크면 두 값을 교환한다.
    이 교환이 반복되면서 작은 값들이 앞쪽으로 이동한다.

    (3) cnt
    cnt는 한 바퀴 동안 교환이 몇 번 일어났는지 세는 변수이다.
    교환이 한 번도 일어나지 않으면 이미 정렬된 상태이므로 반복을 종료한다.

3) 앞에서부터 비교하는 방식

    (1) bubbleSort2
    두 번째 방식은 배열의 앞쪽에서 뒤쪽으로 이동하며 인접한 두 값을 비교한다.
    큰 값을 오른쪽으로 밀어내는 방식이다.

    (2) 정렬 확정 구간
    한 바퀴가 끝나면 가장 큰 값이 맨 오른쪽으로 이동한다.
    그래서 다음 반복에서는 이미 정렬된 마지막 칸을 제외하고 비교한다.

    (3) 조기 종료
    한 번의 반복 동안 교환이 없으면 배열이 이미 정렬된 상태이다.
    이때 break를 사용해 불필요한 반복을 줄인다.

7 색인

1) 색인의 개념

    (1) 색인
    색인은 데이터를 빠르게 검색할 수 있도록 돕는 구조이다.
    책의 목차나 찾아보기처럼, 전체 데이터를 처음부터 끝까지 뒤지지 않고 원하는 데이터를 빠르게 찾게 해준다.

    (2) 색인이 사용되는 곳
    색인은 데이터베이스, 검색 엔진, 파일 시스템 등에서 사용된다.
    데이터가 많을수록 검색 속도를 높이기 위해 색인이 중요해진다.

    (3) 검색 속도 향상
    색인이 있으면 전체 데이터 집합을 모두 탐색하지 않아도 된다.
    그래서 원하는 데이터를 빠르게 찾을 수 있다.

2) 색인의 특징

    (1) 검색 효율성
    색인은 검색 효율을 높인다.
    특히 데이터 양이 많고 특정 값을 자주 찾는 경우 효과가 크다.

    (2) 다양한 형태
    색인은 해시 테이블, B-트리, 비트맵 색인 등 여러 형태로 구현될 수 있다.
    데이터의 성격과 검색 방식에 따라 적절한 구조를 사용한다.

    (3) 업데이트 비용
    데이터가 추가되거나 삭제되면 색인도 함께 업데이트되어야 한다.
    검색은 빨라지지만, 데이터 변경이 많을 경우 색인을 유지하는 비용이 발생한다.

8 트리

1) 트리의 개념

    (1) 트리
    트리는 노드들이 부모와 자식 관계로 연결된 계층적 자료구조이다.
    조직도, 폴더 구조, 카테고리 구조처럼 위아래 관계가 있는 데이터를 표현하기 좋다.

    (2) 노드
    노드는 트리를 구성하는 기본 단위이다.
    각 노드는 데이터를 가지고, 자식 노드에 대한 참조를 가질 수 있다.

    (3) 부모와 자식
    어떤 노드에서 아래로 연결된 노드는 자식 노드이고, 그 자식을 가리키는 위쪽 노드는 부모 노드이다.
    트리는 이러한 부모 자식 관계를 통해 계층 구조를 만든다.

2) 트리의 종류

    (1) 이진 트리
    이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리이다.
    보통 왼쪽 자식과 오른쪽 자식으로 구분한다.

    (2) 이진 검색 트리
    이진 검색 트리는 왼쪽에는 작은 값, 오른쪽에는 큰 값이 오도록 저장하는 트리이다.
    데이터를 빠르게 검색하기 위해 사용한다.

    (3) B-트리
    B-트리는 데이터베이스나 파일 시스템에서 많이 사용하는 트리 구조이다.
    많은 데이터를 효율적으로 저장하고 검색하기 위해 사용된다.

    (4) 균형 이진 트리
    균형 이진 트리는 한쪽으로 치우치지 않도록 균형을 유지하는 이진 트리이다.
    검색 성능이 나빠지는 것을 막기 위해 사용한다.

3) 트리의 장단점

    (1) 장점
    트리는 계층적 데이터를 표현하기 좋고, 구조가 잘 유지되면 검색이 효율적이다.
    삽입과 삭제도 노드 단위로 처리할 수 있어 동적 데이터 관리에 적합하다.

    (2) 단점
    노드 간 연결 정보를 저장해야 하므로 메모리를 추가로 사용한다.
    구현이 배열이나 리스트보다 복잡하고, 트리가 한쪽으로 치우치면 성능이 저하될 수 있다.

9 이진 검색 트리

1) 이진 검색 트리의 개념

    (1) 이진 검색 트리
    이진 검색 트리는 이진 탐색의 아이디어를 트리 구조에 적용한 자료구조이다.
    값을 정렬 규칙에 맞게 저장해서 검색 속도를 높인다.

    (2) 이진 탐색과의 관계
    이진 탐색은 정렬된 데이터에서 중간값을 기준으로 탐색 범위를 반씩 줄이는 방식이다.
    이진 검색 트리는 현재 노드와 비교한 뒤 왼쪽 또는 오른쪽으로 이동하면서 비슷한 방식으로 탐색한다.

2) 이진 검색 트리 규칙

    (1) 왼쪽 서브트리
    왼쪽 서브트리에는 부모 노드의 키보다 작은 값들이 저장된다.
    검색하려는 키가 현재 노드보다 작으면 왼쪽으로 이동한다.

    (2) 오른쪽 서브트리
    오른쪽 서브트리에는 부모 노드의 키보다 큰 값들이 저장된다.
    검색하려는 키가 현재 노드보다 크면 오른쪽으로 이동한다.

    (3) 중복 키 처리
    실습 코드에서는 이미 같은 키가 존재하면 새 노드를 추가하지 않는다.
    키는 데이터를 구분하는 기준이므로 중복되지 않게 관리한다.

3) 이진 검색 트리의 장점

    (1) 효율적인 검색
    왼쪽과 오른쪽 중 한 방향으로 탐색 범위를 줄일 수 있기 때문에 평균적으로 검색이 빠르다.
    전체 데이터를 처음부터 끝까지 탐색하지 않아도 된다.

    (2) 동적 데이터 관리
    노드를 추가하거나 삭제하면서 데이터를 관리할 수 있다.
    배열처럼 모든 데이터를 한 번에 옮기지 않아도 된다.

    (3) 직관적인 구조
    현재 노드보다 작으면 왼쪽, 크면 오른쪽이라는 규칙이 명확하다.
    이 규칙을 이해하면 검색, 추가, 삭제 흐름을 따라가기 쉽다.

4) 이진 검색 트리의 단점

    (1) 불균형 문제
    데이터를 삽입하는 순서에 따라 트리가 한쪽으로 길게 치우칠 수 있다.
    이 경우 트리가 리스트처럼 변해 검색 성능이 떨어질 수 있다.

    (2) 균형 유지 필요
    좋은 성능을 유지하려면 트리의 균형이 중요하다.
    균형을 자동으로 맞추는 구조는 구현이 더 복잡해질 수 있다.

10 BinarySearchTree 클래스 구조

1) 제네릭 구조

    (1) K와 V
    BinarySearchTree<K, V>에서 K는 검색 기준이 되는 key 타입이고, V는 저장할 data 타입이다.
    key로 데이터를 찾고, 실제 저장된 값은 data로 관리한다.

    (2) 제네릭을 사용하는 이유
    제네릭을 사용하면 Integer 키, String 키, 사용자 정의 객체 등 다양한 타입을 사용할 수 있다.
    자료구조를 특정 타입에만 묶어두지 않고 재사용할 수 있게 만든다.

2) Node 클래스

    (1) key
    key는 노드를 검색하고 정렬하는 기준값이다.
    이진 검색 트리에서는 key를 기준으로 왼쪽 또는 오른쪽 이동을 결정한다.

    (2) data
    data는 실제로 저장할 값이다.
    실습에서는 Data 객체가 저장되어 이름 정보를 출력할 수 있다.

    (3) left
    left는 현재 노드의 왼쪽 자식 노드를 가리킨다.
    현재 key보다 작은 key를 가진 노드들이 왼쪽에 연결된다.

    (4) right
    right는 현재 노드의 오른쪽 자식 노드를 가리킨다.
    현재 key보다 큰 key를 가진 노드들이 오른쪽에 연결된다.

3) root와 comparator

    (1) root
    root는 트리의 시작 노드이다.
    모든 검색, 추가, 삭제는 root에서 시작된다.

    (2) comparator
    comparator는 key의 대소관계를 판단하는 기준이다.
    기본 비교 기준을 사용하거나, 사용자가 직접 만든 비교 기준을 사용할 수 있다.

    (3) com 메소드
    com 메소드는 두 key를 비교해서 양수, 음수, 0 중 하나의 결과를 만든다.
    결과가 음수이면 첫 번째 key가 더 작고, 양수이면 더 크며, 0이면 같은 값이다.

11 이진 검색 트리 검색 기능

1) search 메소드

    (1) search의 역할
    search는 key를 기준으로 트리에서 원하는 데이터를 찾는 메소드이다.
    key와 일치하는 노드를 찾으면 해당 노드의 data를 반환한다.

    (2) root에서 시작
    검색은 항상 root 노드에서 시작한다.
    현재 노드와 찾으려는 key를 비교하면서 이동 방향을 결정한다.

2) 검색 흐름

    (1) 현재 노드가 없는 경우
    현재 노드가 null이면 더 이상 탐색할 노드가 없다는 뜻이다.
    이 경우 찾는 key가 트리에 없으므로 null을 반환한다.

    (2) key가 같은 경우
    비교 결과가 0이면 검색하려는 key와 현재 노드의 key가 같은 것이다.
    이때 현재 노드의 data를 반환한다.

    (3) key가 작은 경우
    검색하려는 key가 현재 노드의 key보다 작으면 왼쪽 자식으로 이동한다.
    이진 검색 트리 규칙상 작은 값은 왼쪽에 있기 때문이다.

    (4) key가 큰 경우
    검색하려는 key가 현재 노드의 key보다 크면 오른쪽 자식으로 이동한다.
    큰 값은 오른쪽에 있기 때문이다.

12 이진 검색 트리 추가 기능

1) add 메소드

    (1) add의 역할
    add는 새로운 key와 data를 가진 노드를 트리에 추가하는 메소드이다.
    추가 후에도 이진 검색 트리의 규칙이 유지되어야 한다.

    (2) root가 없는 경우
    root가 null이면 트리가 비어 있는 상태이다.
    이때 새 노드를 root로 만든다.

    (3) root가 있는 경우
    root가 이미 있으면 addNode 메소드가 실제 삽입 위치를 찾는다.
    현재 노드와 key를 비교하면서 왼쪽 또는 오른쪽으로 이동한다.

2) addNode 메소드

    (1) 같은 key인 경우
    비교 결과가 0이면 이미 같은 key가 존재한다는 뜻이다.
    실습 코드에서는 중복 key를 추가하지 않고 그대로 종료한다.

    (2) 추가할 key가 작은 경우
    추가하려는 key가 현재 노드의 key보다 작으면 왼쪽으로 가야 한다.
    왼쪽 자식이 비어 있으면 그 자리에 새 노드를 추가하고, 비어 있지 않으면 왼쪽 자식에서 다시 addNode를 호출한다.

    (3) 추가할 key가 큰 경우
    추가하려는 key가 현재 노드의 key보다 크면 오른쪽으로 가야 한다.
    오른쪽 자식이 비어 있으면 그 자리에 새 노드를 추가하고, 비어 있지 않으면 오른쪽 자식에서 다시 addNode를 호출한다.

3) 추가 실습 흐름

    (1) key 기준 저장
    MTest에서는 5, 10, 1, 12, 8, 9, 13을 key로 가진 데이터를 추가한다.
    각 값은 이진 검색 트리 규칙에 따라 왼쪽 또는 오른쪽 위치에 저장된다.

    (2) data 저장
    key는 검색 기준이고, data에는 이름 정보가 들어간 Data 객체가 저장된다.
    나중에 search를 하면 key에 해당하는 Data 객체를 찾을 수 있다.

13 이진 검색 트리 삭제 기능

1) remove 메소드

    (1) remove의 역할
    remove는 key를 기준으로 노드를 찾아 삭제하는 메소드이다.
    삭제 후에도 이진 검색 트리의 규칙이 유지되어야 한다.

    (2) 삭제할 노드 탐색
    먼저 root부터 시작해 삭제할 key를 가진 노드를 찾는다.
    이때 p는 삭제할 노드, parent는 삭제할 노드의 부모 노드를 의미한다.

    (3) isLeftChild
    isLeftChild는 삭제할 노드가 부모의 왼쪽 자식인지 오른쪽 자식인지 기억하는 변수이다.
    삭제 후 부모가 어떤 자식 링크를 바꿔야 하는지 판단할 때 필요하다.

2) 자식이 없는 경우와 하나인 경우

    (1) 왼쪽 자식이 없는 경우
    삭제할 노드의 왼쪽 자식이 없으면 오른쪽 자식을 부모에게 연결하면 된다.
    삭제할 노드가 root이면 root를 오른쪽 자식으로 바꾼다.

    (2) 오른쪽 자식이 없는 경우
    삭제할 노드의 오른쪽 자식이 없으면 왼쪽 자식을 부모에게 연결하면 된다.
    삭제할 노드가 root이면 root를 왼쪽 자식으로 바꾼다.

    (3) 연결을 바꾸는 이유
    삭제할 노드를 그냥 없애면 그 아래 자식 노드들이 끊어질 수 있다.
    그래서 삭제할 노드의 자식을 부모에게 다시 연결해야 한다.

3) 자식이 두 개인 경우

    (1) 삭제가 복잡한 이유
    삭제할 노드에 왼쪽 자식과 오른쪽 자식이 모두 있으면 단순히 한쪽 자식만 올릴 수 없다.
    이진 검색 트리의 왼쪽은 작고 오른쪽은 커야 한다는 규칙을 유지해야 하기 때문이다.

    (2) 왼쪽 서브트리의 최댓값 사용
    실습 코드에서는 삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드를 찾는다.
    이 값은 삭제할 노드보다 작으면서, 왼쪽 서브트리 안에서는 가장 큰 값이므로 대체 노드로 사용할 수 있다.

    (3) key와 data 덮어쓰기
    왼쪽 서브트리의 최댓값 노드의 key와 data를 삭제할 노드에 복사한다.
    이렇게 하면 삭제 대상 노드의 내용이 대체된다.

    (4) 대체 노드 제거
    key와 data를 복사한 뒤, 원래 위치에 있던 대체 노드는 제거해야 한다.
    이때 대체 노드의 왼쪽 자식을 부모에게 연결해 트리 구조를 정리한다.

4) 삭제 실습 흐름

    (1) remove 10
    MTest에서는 key가 10인 노드를 삭제한다.
    삭제 후 print를 호출해 트리 구조가 이진 검색 트리 규칙을 유지하는지 확인한다.

    (2) 삭제 결과 확인
    삭제가 끝난 뒤에도 중위 순회로 출력하면 key가 정렬된 순서로 출력된다.
    이것은 삭제 후에도 트리 규칙이 유지되고 있다는 의미이다.

14 이진 검색 트리 출력 기능

1) print 메소드

    (1) print의 역할
    print는 트리 전체 데이터를 출력하는 메소드이다.
    내부적으로 printSubTree를 호출해 root부터 출력한다.

2) 중위 순회

    (1) 중위 순회
    printSubTree는 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 출력한다.
    이 방식을 중위 순회라고 한다.

    (2) 이진 검색 트리에서 중위 순회의 의미
    이진 검색 트리는 왼쪽이 작고 오른쪽이 큰 구조이다.
    따라서 중위 순회로 출력하면 key가 작은 순서부터 큰 순서로 정렬되어 출력된다.

    (3) 실습 출력 의미
    tree.print를 실행하면 추가한 순서와 상관없이 key가 오름차순으로 출력된다.
    이진 검색 트리가 내부적으로 데이터를 정렬 규칙에 맞게 저장하기 때문이다.

15 그래프

1) 그래프의 개념

    (1) 그래프
    그래프는 정점과 간선으로 구성된 비선형 자료구조이다.
    여러 대상 사이의 관계를 표현할 때 사용한다.

    (2) 그래프를 사용하는 이유
    그래프는 네트워크, 소셜 미디어 친구 관계, 지도 경로, 웹페이지 링크처럼 복잡한 연결 관계를 표현하기 좋다.
    단순한 순서나 계층 구조로 표현하기 어려운 관계를 다룰 수 있다.

2) 그래프의 기본 구성

    (1) 정점
    정점은 그래프의 기본 단위이다.
    사람, 도시, 컴퓨터, 데이터 같은 하나의 대상을 표현한다.

    (2) 간선
    간선은 정점과 정점 사이의 관계를 나타내는 선이다.
    두 정점이 서로 연결되어 있음을 의미한다.

3) 그래프의 종류

    (1) 유향 그래프
    유향 그래프는 간선에 방향이 있는 그래프이다.
    A에서 B로 가는 관계와 B에서 A로 가는 관계가 다를 수 있다.

    (2) 무향 그래프
    무향 그래프는 간선에 방향이 없는 그래프이다.
    A와 B가 연결되어 있다면 양쪽 모두 같은 관계로 본다.

    (3) 가중치 그래프
    가중치 그래프는 간선에 비용, 거리, 시간 같은 값이 붙어 있는 그래프이다.
    최단 경로 문제처럼 비용을 고려해야 할 때 사용한다.

    (4) 비가중치 그래프
    비가중치 그래프는 간선에 별도의 비용이 없는 그래프이다.
    두 정점이 연결되어 있는지 여부만 중요할 때 사용한다.

    (5) 사이클 그래프
    사이클 그래프는 어떤 정점에서 출발해 다시 그 정점으로 돌아오는 경로가 존재하는 그래프이다.
    순환 관계가 있는 구조를 표현할 수 있다.

    (6) 비순환 그래프
    비순환 그래프는 사이클이 없는 그래프이다.
    작업 순서나 의존 관계처럼 순환이 없어야 하는 구조에 사용할 수 있다.

    (7) 연결 그래프
    연결 그래프는 모든 정점 사이에 경로가 존재하는 그래프이다.
    어떤 정점에서 출발해도 다른 정점으로 이동할 수 있다.

    (8) 비연결 그래프
    비연결 그래프는 서로 연결되지 않은 부분 그래프가 존재하는 그래프이다.
    전체 그래프 안에 독립적인 그룹이 나뉘어 있는 구조이다.