Tree

 

 

---

공통 질문

1. 이진 검색 트리 (BST: Binary Search Tree)
2. AVL 트리 (Adelson-Velsky and Landis Tree)
3. Red-Black 트리
4. B-트리 (Balanced Tree)

 

---

1. 이진 검색 트리 (BST: Binary Search Tree)

      50
     /  \
   30    70
  /  \   /  \
10   40 60   90

개념

• 각 노드의 왼쪽 서브트리는 부모보다 작은 값, 오른쪽 서브트리는 부모보다 큰 값을 가지는 트리.
• 균형을 유지하는 별도의 메커니즘이 없음 → 최악의 경우 한쪽으로 기울어진 **선형 트리(O(n))**가 될 수 있음.

특징

✅ 간단한 구현
✅ 탐색, 삽입, 삭제 연산: O(h) (h: 트리 높이)
❌ 균형이 깨질 경우 탐색 성능 저하 (O(n)까지 증가 가능)

적용 사례

• 정렬된 데이터를 빠르게 검색해야 하는 경우 사용하지만, 트리가 불균형해지면 성능이 급격히 저하됨.

 

 

 

---

2. AVL 트리 (Adelson-Velsky and Landis Tree)

      30
     /  \
   20    40
  /
10

균형 유지, 높이 차이 최대 1

개념

• BST의 변형으로, 균형을 유지하는 자기 균형 이진 트리(Self-balancing BST).
• 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이(균형 인수, Balance Factor)가 최대 ±1을 유지.
• 삽입/삭제 시 불균형이 발생하면 즉시 회전(Rotation) 연산을 수행하여 균형 유지.

특징

✅ 탐색, 삽입, 삭제 연산: O(log n) (항상 균형 유지)
✅ 트리 높이가 작아서 탐색 성능 우수
❌ 삽입 및 삭제 연산이 Red-Black 트리보다 상대적으로 느림 (회전 연산이 더 자주 발생)

적용 사례

• 읽기(Search) 연산이 빈번한 경우 (균형이 보장되므로 탐색 성능이 항상 좋음).
• 데이터가 자주 변경되지 않는 경우(삭제/삽입이 많으면 성능이 떨어질 수 있음).

 

---

3. Red-Black 트리

      30(B)
     /    \
  20(R)   40(R)
  /
10(B)

균형이 AVL보다는 덜 맞춰져 있지만, 성능이 더 좋음.

개념

• BST의 변형으로, 균형을 유지하는 자기 균형 이진 트리.
• AVL 트리와 달리 균형을 완벽하게 유지하지 않고, "적당한 균형"을 유지하여 삽입/삭제 성능을 개선.
• 각 노드가 "Red" 또는 "Black"으로 색칠되며, 특정 규칙을 통해 균형을 유지.
• 회전 연산이 AVL보다 적게 발생하여 삽입/삭제 속도가 빠름.

특징

✅ 탐색, 삽입, 삭제 연산: O(log n)
✅ 삽입 및 삭제 연산이 AVL보다 빠름 (균형이 완벽하지 않으므로 회전 횟수 감소)
❌ 탐색 성능은 AVL보다 약간 낮음 (완벽한 균형이 아니라서 높이가 약간 더 큼)

적용 사례

• 읽기와 쓰기가 모두 빈번한 경우 (삽입/삭제 속도가 중요).
• 운영체제(OS)의 메모리 할당, 파일 시스템, 데이터베이스 인덱싱 등에 사용.

Red-Black 트리 규칙

1. 루트 노드는 항상 Black
2. 연속된 Red 노드가 없음 (Red는 항상 Black 부모를 가져야 함)
3. 모든 리프(nil) 노드는 Black
4. 어느 경로에서든 Black 노드 개수가 동일해야 함

 

---

4. B-트리 (Balanced Tree)

자녀노드의 최대 개수를 늘리고 싶을 때

자식을 2개가 아니라 2개 이상으로 늘리고 싶을 때

 

 

 

B트리 추가

 

 

 

 

 

 

부모 분화

 

 

 

 

 

 

 

 

root 조정

 

 

 

넘쳐버림

70 승진

 

 

 

 

 

 

50 승진

 

50 승진

 

 

 

최종

 

B tree 삭제

 

3차/2 = 1.5

1.5 반올림 2

2-1 = 1

 

최소 키 1개

 

 

 

 

 

 

재조정 조건

 

삭제 조건

 

동생한테 key 받음

 

 

형 도움 받기

 

 

 

 

 

조회

 

 

부모의 지원을 받고, 형제와 합치기

 

 

 

부모님 도움 받기, 형이랑 합치기

 

 

 

형제 합치기

 

부모님이 문제 생김

형제도 여유없음

 

부모 지원 받음

 

형제 합치기

 

root 삭제

 

 

 

 

중간 데이터 삭제

 

 

선임자 후임자로 자리 바꾸기

 

 

삭제 예시

 

 

자리 바꾸기, 나의 왼쪽 서브 트리에서 가장 큰 값 가져오기

 

 

 

노드 개수 부족하니, 형제한테 빌려오기

 

 

root 삭제

 

왼쪽 서브 트리에서 가장 큰 값 교환

 

 

형제에게 도움 받기 -> 실패

부모님한테 도움 받기

30 내려옴

형제 끼리 합치기

 

 

부모가 최소한의 key 개수 부족함

 

형제도 부족함, 부모님께 도움 받기

 

 

위치 바꾸기

 

순서 재조정

 

형제한테 하나 지원받기

 

 

        [30, 50]
       /   |   \
    [10] [40] [60, 70]

B-트리는 AVL이나 Red-Black 트리보다 높이가 낮고, 노드당 여러 개의 키를 저장.

개념

• 이진 트리가 아닌, M-Way Tree (각 노드가 2개 이상의 자식을 가질 수 있음).
• 데이터베이스와 파일 시스템에서 많이 사용됨.
• 노드 하나에 여러 개의 키(값)를 저장하여, 높이를 낮추고 탐색을 빠르게 수행.
• 디스크 I/O 최적화를 위해 설계됨.

특징

✅ 탐색, 삽입, 삭제 연산: O(log n)
✅ 트리 높이가 낮아서 대량의 데이터를 빠르게 탐색 가능
✅ 디스크 I/O 최적화
❌ 구현이 복잡하고, 삽입/삭제 연산 시 노드 분할/병합이 필요

적용 사례

• 데이터베이스 인덱스(MySQL, PostgreSQL, Oracle 등).
• 파일 시스템(Ext4, NTFS, HFS+ 등).

 

 

출처: https://www.youtube.com/watch?v=bqkcoSm_rCs

 

 

 

---

5. BST, AVL, Red-Black , B-Tree

 

 

• 탐색 속도가 가장 중요한 경우 → AVL 트리
• 삽입/삭제가 빈번한 경우 → Red-Black 트리
• 파일 시스템, 데이터베이스 인덱스 → B-트리
• 단순한 검색과 정렬 → 기본 이진 검색 트리(BST)

 

• BST: 기본적인 검색 트리지만 균형이 깨질 수 있음.
• AVL 트리: 완벽한 균형 유지, 탐색이 빠름(읽기 최적화), 하지만 삽입/삭제 속도가 느릴 수 있음.
• Red-Black 트리: 적절한 균형 유지, 삽입/삭제 속도가 빠름(쓰기 최적화).
• B-트리: 다중 자식을 가지는 구조로, 데이터베이스 및 파일 시스템에서 사용.

---

출처: https://www.youtube.com/watch?v=ohrwGtqeW-I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

노드의 크기: 자신을 포함한 자손 노드의 수

 

트리의 크기 : 10 모든 노드의 수

 

서브 트리

 

 

트리 특징

 

 

 

 

 

 

---

이진 트리

 

이진 트리 종류

 

 

 

 

변질 이진 트리 종류

 

 

 

 

 

balance binary tree

 

 

 

 

---

출처: https://www.youtube.com/watch?v=liPSnc6Wzfk

 

db index는 왜 b+ tree 로 사용할까?

 

 

 

 

swap

 

 

 

 

블록 단위로 읽어온다

 

불필요한 데이터까지 읽어옴

 

 

 

1. second에 접근을 덜하도록

 

 

2. 비슷한 데이터를 모아서 저장

 

 

 

가정

 

 

 

avl tree index

 

 

b tree index

 

 

 

 

 

root에서 leaf까지 가는 거리가 짧아진다.

 

블록 단위 읽기