Skip to content

Tree

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

Tree

README.md

BST (Binary Search Tree) 이진 탐색 트리

특징

  • 왼쪽 자식 < 부모 < 오른쪽 자식
  • 중복 값은 저장하지 않음
  • 중위 순회(inorder)하면 정렬된 순서로 출력됨

시간 복잡도

연산 평균 최악
삽입 O(log n) O(n)
검색 O(log n) O(n)
삭제 O(log n) O(n)
  • 평균: 트리가 균형 잡혀 있을 때 (높이 = log n)
  • 최악: 한쪽으로 치우친 경우 (1, 2, 3, 4... 순서로 삽입하면 사실상 연결 리스트)

삭제 시 3가지 케이스

  1. 리프 노드 (자식 없음) → 그냥 제거
  2. 자식 1개 → 자식을 위로 올림
  3. 자식 2개 → 오른쪽 서브트리의 최솟값(후계자)으로 교체 후 후계자 삭제

후계자를 오른쪽 서브트리의 최솟값으로 찾는 이유

  • "삭제할 노드보다 크면서 가장 작은 값"이기 때문
  • 이 값을 넣으면 BST 정렬 조건(왼쪽 < 부모 < 오른쪽)이 자동으로 유지됨
  • 바로 밑 자식과 교체하면 서브트리 구조가 꼬일 수 있음

순회 방식

  • 중위 (Inorder): 왼쪽 → 루트 → 오른쪽 (정렬 순서)
  • 전위 (Preorder): 루트 → 왼쪽 → 오른쪽
  • 후위 (Postorder): 왼쪽 → 오른쪽 → 루트

AVL 트리 (자가 균형 이진 탐색 트리)

왜 필요한가

  • 일반 BST는 한쪽으로 치우치면 최악 O(n) 이 됨 (1, 2, 3... 순서 삽입 시 연결 리스트처럼 됨)
  • AVL 트리는 삽입/삭제마다 스스로 균형을 잡아, 높이를 항상 log n 수준으로 유지함
  • 따라서 삽입·검색·삭제가 항상 O(log n) 보장 (최악도 O(log n))

균형 인수 (Balance Factor, BF)

  • BF = (왼쪽 서브트리 높이) - (오른쪽 서브트리 높이)
  • AVL 조건: 모든 노드의 |BF| ≤ 1
  • BF가 2 또는 -2가 되는 순간 → 회전(rotation) 으로 균형 복구

회전 4가지 케이스

케이스 상황 해결
LL 왼쪽-왼쪽이 무거움 (BF > 1, 왼쪽 자식 BF ≥ 0) 오른쪽 회전 1번
RR 오른쪽-오른쪽이 무거움 (BF < -1, 오른쪽 자식 BF ≤ 0) 왼쪽 회전 1번
LR 왼쪽-오른쪽이 무거움 (BF > 1, 왼쪽 자식 BF < 0) 왼쪽 회전 → 오른쪽 회전
RL 오른쪽-왼쪽이 무거움 (BF < -1, 오른쪽 자식 BF > 0) 오른쪽 회전 → 왼쪽 회전
  • LL / RR: 한 방향으로 쏠림 → 한 번 회전으로 해결
  • LR / RL: 꺾여 있음 → 먼저 자식을 회전해 일직선으로 만든 뒤, 다시 회전 (총 2번)

시간 복잡도

연산 평균 최악
삽입 O(log n) O(log n)
검색 O(log n) O(log n)
삭제 O(log n) O(log n)
  • BST와 달리 최악도 O(log n) 인 것이 핵심 (균형이 항상 유지되므로)

BST vs AVL

항목 BST AVL
균형 유지 안 함 자동
최악 시간 복잡도 O(n) O(log n)
삽입/삭제 비용 낮음 회전 비용 추가 (그래도 O(log n))
적합한 상황 입력이 랜덤할 때 정렬된 입력·검색이 잦을 때

정상 동작 검증 방법 (2가지 모두 만족해야 AVL)

  1. BST 조건: 중위 순회(inorder) 결과가 오름차순인가
  2. 균형 조건: 모든 노드의 |BF| ≤ 1 인가 (isBalanced())

균형이 깨진 트리도 inorder는 오름차순으로 나올 수 있으므로, 두 가지를 함께 확인해야 함

RB 트리 (Red-Black Tree, 자가 균형 이진 탐색 트리)

왜 필요한가

  • AVL과 같은 목적: BST의 편향(최악 O(n))을 막아 항상 O(log n) 보장
  • 차이는 균형의 엄격함: AVL은 높이차 ≤ 1로 빡빡하게, RB는 느슨하게 잡음
  • 느슨한 대신 회전이 적게 발생 → 삽입·삭제가 잦은 환경에 유리
  • 실무 표준: Java TreeMap/TreeSet, C++ std::map/set, Linux 커널 rbtree

5가지 규칙

  1. 모든 노드는 Red 또는 Black
  2. 루트는 Black
  3. 모든 리프(NIL)는 Black (NIL = 데이터 없는 가상 노드, null 역할)
  4. Red의 자식은 Black (Red-Red 연속 금지)
  5. 임의 노드에서 모든 리프까지 경로의 Black 개수는 동일 (= 블랙 높이)

왜 O(log n)이 보장되나

  • 규칙 5 → 모든 경로의 Black 개수 동일 b개
  • 규칙 4 → Red는 연속 불가 → 한 경로의 Red ≤ Black
  • 따라서 가장 긴 경로(2b) ≤ 가장 짧은 경로(b) × 2 → 높이 ≤ 2 log(n+1)

삽입 (새 노드는 항상 Red)

  • 부모가 Black이면 → 끝 (위반 없음)
  • 부모가 Red면 Red-Red 위반 → 삼촌(부모의 형제) 색으로 판단
케이스 삼촌 색 해결
Case 1 Red 부모·삼촌 → Black, 조부모 → Red, 위로 전파
Case 2 Black 회전 (LL/RR 단일, LR/RL 이중) + 색 변경 → 종료

삼촌을 보는 이유: "부모 쪽만 Black으로 만들 때 반대쪽(삼촌)이 균형을 맞춰줄 수 있나"를 확인. Red면 같이 Black 되며 맞춰지고(색변경), Black이면 못 도와줘서 회전 필요.

삭제 — 이중 블랙(Double Black)

  • Black 노드를 지우면 그 경로의 Black이 하나 부족 → "블랙 빚"이 생김 (= 이중 블랙)
  • Red 노드 삭제나 Red 후계자면 → 그냥 끝 (빚 없음)
  • 빚은 형제(sibling) 색을 보고 갚음 (삽입의 삼촌과 대칭)
케이스 형제 조카 해결
Case 1 Red - 형제→Black, 부모→Red, 회전 → Case 2/3으로 전환
Case 2 Black 둘 다 Black 형제→Red, 빚을 부모로 전파
Case 3-1 Black 가까운 쪽만 Red 형제 회전 → Case 3-2로
Case 3-2 Black 먼 쪽 Red 색 변경 + 최종 회전 → 종료

큰 그림: 블랙 지우면 빚 발생 → 형제에게 빨간 조카 있으면 빌려서 청산(끝), 없으면 양쪽 깎아 위로 전파(반복), 빨강/루트 만나면 흡수(끝).

AVL vs RB

항목 AVL RB
균형 기준 높이차 ≤ 1 (엄격) 색 규칙 (느슨)
검색 속도 약간 빠름 약간 느림
삽입/삭제 회전 많음 적음
최악 높이 ~1.44 log n ~2 log n
적합한 상황 검색 위주 삽입·삭제 잦을 때

정상 동작 검증 방법 (2가지 모두 만족해야 RB)

  1. BST 조건: 중위 순회(inorder)가 오름차순인가
  2. RB 조건 (isBalanced()): 루트 Black + Red-Red 없음 + 모든 경로 블랙 높이 동일

대량 삽입·삭제 후에도 isBalanced()가 계속 true면 fixup 구현이 올바르다는 증거

B-트리 (B-Tree, 다분기 균형 탐색 트리)

왜 필요한가

  • AVL·RB는 자식이 2개뿐인 이진 트리 → 데이터가 많으면 높이가 그래도 깊어짐
  • B-트리는 노드 하나에 키를 여러 개 담아 자식이 여러 갈래 → 높이를 더 낮게 (log_t n) 유지
  • 핵심 목적: 디스크 접근(느린 I/O) 횟수 최소화 → 노드 하나 = 디스크 블록 하나로 맞춤
  • 실무: DB 인덱스(MySQL InnoDB, PostgreSQL), 파일 시스템(NTFS, ext4)

차수 표기법 — M 방식 vs t 방식

  • M (order): 노드가 가질 수 있는 최대 자식 수 (교재에서 흔히 쓰는 "M차")
  • t (minimum degree): 노드가 가져야 하는 최소 자식 수 (CLRS 방식)
  • 관계: M = 2t (짝수일 때 정확, 일반식은 t = ⌈M/2⌉)
  • 차수는 트리 생성 시 고정 (final), 삽입·삭제로 안 변함 → 노드 최대 크기도 고정

노드 규칙 (최소 차수 t 기준)

항목 최소 (루트 제외) 최대
키 개수 t - 1 2t - 1
자식 개수 t 2t
  • 자식 수 = 키 수 + 1
  • 노드 안 키는 오름차순 정렬, 중복 없음
  • 각 자식은 키 사이 "구간"을 담당 (child[i] = key[i-1]과 key[i] 사이 값)
  • 모든 리프는 같은 깊이 (균형 자동 보장)
  • 루트만 최소 조건 예외 (키 1개까지 허용) → 작은 트리도 가능

삽입 — 분할(split), Top-Down

  • 노드가 꽉 참(2t-1개) → 가운데 키(t-1번)를 부모로 올리고 좌우 t-1개씩 둘로 쪼갬
  • 내려가는 길에 꽉 찬 자식을 미리 분할 → 넣을 때 넘칠 걱정 없음
  • 루트가 꽉 찼을 때만 새 루트가 생기며 트리 높이 +1 (유일하게 높이 자라는 순간)

삭제 — 빌리기(borrow) / 병합(merge), Top-Down

  • 원칙: 내려가기 전에 자식이 최소치(t-1)면 미리 t개 이상으로 채움 → 빼도 안 모자람
  • 키를 찾았을 때:
경우 상황 해결
리프 리프에 있음 그냥 제거
내부 노드 왼쪽 자식 여유(≥t) 선행키(왼쪽 서브트리 최댓값)로 교체 후 삭제
내부 노드 오른쪽 자식 여유(≥t) 후행키(오른쪽 서브트리 최솟값)로 교체 후 삭제
내부 노드 양쪽 다 최소치 병합 후 삭제
  • 자식이 최소치라 내려갈 수 없을 때 (fill):
    • 형제가 여유(≥t) 있으면 → borrow (부모를 거친 회전, 직접 안 옮김)
    • 형제도 최소치면 → merge (자식 + 부모 구분키 + 형제를 하나로)
  • 삭제 후 루트 키가 0개가 되면 유일한 자식을 새 루트로 → 높이 -1

시간 복잡도

연산 평균 최악
삽입 O(log n) O(log n)
검색 O(log n) O(log n)
삭제 O(log n) O(log n)
  • 균형이 구조적으로 보장되어 최악도 O(log n) (정확히는 O(t · log_t n))
  • 차수 t가 클수록 높이가 낮아짐 → DB는 t를 크게 잡아 디스크 접근 최소화

삽입 분할 ↔ 삭제 보정 대칭

삽입 삭제
검사 자식이 꽉 찼나 (== 2t-1) 자식이 최소치인가 (< t)
조치 분할(split) 빌리기/병합(borrow/merge)
목적 넣어도 안 넘치게 빼도 안 모자라게
시점 내려가기 전 (top-down) 내려가기 전 (top-down)

AVL/RB vs B-트리

항목 AVL / RB (이진) B-트리 (다분기)
자식 수 2개 고정 t ~ 2t개
균형 유지 회전 분할 / 병합
균형 검사 필요 (BF, 색 규칙) 불필요 (구조상 항상 균형)
높이 성장 회전 중 루트 분할 시만
주 용도 메모리 내 자료구조 디스크 기반 (DB, 파일시스템)

정상 동작 검증 방법

  1. BST 조건: 중위 순회(inorder)가 오름차순인가
  2. B-트리 조건: 노드별 키 개수 범위(t-1~2t-1) + 키 정렬 + 모든 리프 같은 깊이

B-트리는 균형이 구조적으로 보장되므로 AVL·RB의 isBalanced 같은 균형 검사가 개념적으로 불필요. 검증 메서드는 구현 디버깅용 선택 사항일 뿐이다.

B+트리 (B+Tree, 순차 접근에 강한 B-트리 변형)

왜 필요한가

  • B-트리는 데이터가 모든 노드에 흩어져 있어, 정렬 순서로 전체를 훑는 순차·범위 검색을 하려면 트리를 계속 오르내려야 함 (중위 순회로 트리 전체 탐색)
  • B+트리는 모든 데이터를 리프에만 두고 리프끼리 연결 리스트로 이어 → 순차 접근을 리프만 따라가며 O(1) 이동으로 처리
  • 실무: DB 인덱스 대부분(MySQL InnoDB 등)이 사실상 B-트리가 아니라 B+트리

구조 — 인덱스 집합 vs 순차 집합

  • 순차 집합 (Sequence Set): 리프 노드. 실제 데이터 저장 + next 포인터로 연결 리스트 구성
  • 인덱스 집합 (Index Set): 내부 노드. 데이터 없이 분리키(라우팅용) + 포인터만 보유
  • 같은 값이 리프(데이터) + 인덱스(안내판)에 공존 가능 (B-트리는 키가 한 곳에만 유일하게)
  • 분리키 = 오른쪽 서브트리의 최솟값 (= 오른쪽 첫 리프의 첫 키)

노드 규칙 (최소 차수 t 기준) — B-트리와 동일

항목 최소 (루트 제외) 최대
키 개수 t - 1 2t - 1
자식 개수 (내부) t 2t
  • 리프·내부 모두 최소 조건(t-1 이상)을 지켜야 함 (루트만 예외)
  • 데이터 = 리프에만, 내부 키 = 순수 인덱스

검색 (Search)

  • 라우팅: data ≥ 분리키 → 오른쪽(findChild가 >= 0)
    • 분리키가 오른쪽 리프에 실제로 존재하는 값이라, 같으면 오른쪽으로 가야 찾을 수 있음
  • B-트리와 달리 항상 리프까지 내려가야 함 (내부엔 데이터가 없으므로 Best Case 조기 종료 없음)

삽입 (Insert) — 분할 시 copy-up

  • 리프가 꽉 참(2t-1) → 절반으로 쪼개고 오른쪽 리프의 첫 키를 "복사"해 부모로 올림 (copy-up). 데이터는 리프에 그대로 남김
  • 내부가 꽉 참 → B-트리처럼 가운데 키를 "이동"(push-up), 아래에선 제거
  • 분할이 없는 평범한 삽입은 부모 분리키를 손대지 않음 (삽입값은 이미 분리키 ≥ 조건을 통과했으므로 경계가 안 깨짐)

삭제 (Delete)

  • 데이터는 리프에만 있으므로 항상 리프에서 삭제
  • 삭제 후 최소치(t-1) 미만이면 → 형제에게 빌리거나(borrow) 병합(merge). 리프용/내부용 처리가 다름

시간 복잡도

연산 평균 최악
삽입 O(log n) O(log n)
검색 O(log n) O(log n)
삭제 O(log n) O(log n)
범위 검색 O(log n + k) O(log n + k)
  • 단일 검색은 B-트리와 동일, 범위 검색은 리프 연결 리스트 덕에 압도적 (k = 결과 개수)

B-트리 vs B+트리

항목 B-트리 B+트리
데이터 위치 모든 노드 리프만
키 중복 없음 (유일) 리프·인덱스에 공존
리프 연결 없음 연결 리스트
검색 종료 임의 노드 가능 항상 리프까지
분할 시 가운데 키 이동(push-up) 리프는 복사(copy-up) / 내부는 이동
순차·범위 검색 느림 (중위 순회) 빠름 (리프 순회)

정상 동작 검증 방법

  1. 리프 순회 조건: printLeaves(리프 연결 리스트)가 오름차순인가
  2. B+트리 조건: 노드별 키 범위(t-1~2t-1) + 키 정렬 + 모든 리프 같은 깊이 + 데이터가 리프에만 존재