TREE(Binary Tree, BST, B-Tree,B+Tree, AVL Tree,Red-Black Tree)

📌 1. Tree란?

• **Tree(트리)**는 계층적(hierarchical) 구조를 가진 비선형 자료구조입니다.
• **부모-자식 관계(Parent-Child)**로 노드들이 연결됩니다.
• 루트(Root)에서 시작해 리프(Leaf) 노드까지 이어지는 구조입니다.

🧩 2. Tree의 기본 용어 (Node 구성 요소)

Node(노드)	데이터를 저장하는 기본 단위
Root(루트 노드)	트리의 시작점 (부모가 없음)
Leaf(리프 노드)	자식이 없는 노드
Edge(간선)	노드 간의 연결선
Depth(깊이)	루트에서 특정 노드까지의 거리
Height(높이)	특정 노드에서 가장 깊은 리프까지의 거리

 

💡 Node의 구성 요소

• 데이터(Data): 노드에 저장되는 값
• 포인터(Pointer): 자식 노드를 가리키는 참조 주소
• 자바에서는 클래스 객체로 표현:

class TreeNode {     int value;           // 데이터     TreeNode left;       // 왼쪽 자식 노드     TreeNode right;      // 오른쪽 자식 노드     TreeNode(int value) {         this.value = value;         this.left = null;         this.right = null;     } }

 

🌳 트리(Tree)에서 이진 트리(Binary Tree), 이진 탐색 트리(BST), 그리고 B-Tree가 나온 배경과 발전 과정

---

📌 1. 트리(Tree)에서 이진 트리(Binary Tree)가 나온 이유

배경:

• 일반적인 트리는 부모 노드가 여러 자식 노드를 가질 수 있는 비선형 자료구조입니다.
• 하지만 자식 수를 제한하지 않으면 복잡도가 증가하고, 검색·삽입·삭제 성능이 저하됩니다.

이진 트리(Binary Tree)란?

• 각 노드가 최대 두 개의 자식(왼쪽/오른쪽)을 가지는 트리입니다.
• 간단한 구조 덕분에 재귀적 탐색 및 구현이 용이합니다.

📊 이진 트리가 나온 이유:

• 메모리 절약: 포인터가 2개로 고정되어 관리가 쉽다.
• 빠른 탐색: O(log n)의 탐색 효율성 (완전 이진 트리일 경우).
• 재귀적 표현: 코드 구현이 간단해짐.

---

📍 2. 이진 탐색 트리(BST: Binary Search Tree)가 나온 이유

배경:

• 일반 이진 트리는 자식 노드의 배치에 **규칙이 없어 탐색 시 O(n)**의 시간이 걸릴 수 있음.
• 정렬된 데이터를 빠르게 탐색할 수 있는 구조가 필요해짐.

💡 이진 탐색 트리(BST)란?

• 이진 트리의 규칙 + 탐색 규칙을 추가한 트리.

🌳 이진 트리(Binary Tree)와 이진 탐색 트리(BST)의 차이점은 규칙에 있다!

📌 결론부터:

• 이진 트리(Binary Tree): 형태(구조)만 정의됨 → **“노드당 최대 2개의 자식”**만 규칙.
• 이진 탐색 트리(BST): 데이터 정렬 규칙이 추가됨 → “왼쪽 < 부모 < 오른쪽” + 재귀적 규칙.

🧩 핵심 차이: "모든 서브트리가 BST 규칙을 따라야 한다"

 

📍 1. 이진 트리(Binary Tree)의 규칙

• 노드당 최대 두 개의 자식(left, right)만 가지는 형태적 구조.
• 값의 크기에 대한 규칙은 없음.
• 왼쪽 자식이 부모보다 클 수도, 오른쪽 자식이 부모보다 작을 수도 있음.
• 정렬이나 탐색 효율이 보장되지 않음.

예제: 이진 트리 (BST 아님)

10       /  \     20    5   ← 규칙 깨짐 (왼쪽 자식이 부모보다 큼)

 

📍 2. 이진 탐색 트리(BST)의 규칙

• 이진 트리의 모든 자손(서브트리)까지 탐색 규칙을 강제함.
• 모든 노드가 반드시:
  • 왼쪽 서브트리의 값은 부모보다 작음
  • 오른쪽 서브트리의 값은 부모보다 큼
• 이 규칙이 서브트리까지 재귀적으로 적용되어야 함.

예제: 이진 탐색 트리(BST)

10       /  \      5    20     / \   / \    3   7 15 25  ← 모든 서브트리가 규칙을 지킴

 

 

📊 3. 이진 트리와 이진 탐색 트리의 차이점 정리

구분	이진 트리 (Binary Tree)	이진 탐색 트리 (BST)
구조 규칙	노드당 최대 2개의 자식	노드당 최대 2개의 자식
값 배치 규칙	없음	모든 서브트리까지 왼쪽 < 부모 < 오른쪽
서브트리 규칙 적용	❌ 일부만 지켜도 됨	✅ 모든 노드와 서브트리가 동일 규칙을 적용
탐색 속도	O(n) (무질서할 수 있음)	O(log n) (정렬된 상태 유지)
삽입 및 삭제 속도	O(n) (규칙이 없어 재배열 필요)	O(log n) (정렬 유지 덕분에 빠름)

 

📌 1. B-트리가 나온 배경: BST의 한계점

⚠️ BST의 문제점 (특히 대용량 데이터에서는):

1. 트리의 깊이가 깊어질 수 있음:
   • 특히, 편향된(skewed) BST는 성능이 O(n)으로 나빠짐.
2. 디스크 I/O 비용:
   • 데이터베이스(DB)나 파일 시스템에서는 메모리보다 디스크 I/O 비용이 훨씬 큼.
   • BST는 자식이 2개라 트리가 깊어지면, 디스크 접근 횟수가 많아짐.

💡 해결책:

• 한 번에 더 많은 키를 담는 노드를 만들고,
• 자식 수도 늘려 트리 높이를 낮추어 디스크 접근을 최소화하자!

---

📍 2. B-트리(B-Tree)란?

💡 B-트리는 M-Way(다분기) 균형 트리:

• 자식 노드 수(M): 각 노드는 최대 M개의 자식을 가질 수 있음.
• 키(Key) 수: 각 노드는 최대 M-1개의 키를 가짐.
• 모든 리프는 같은 깊이(균형 유지).
• 디스크 I/O를 최소화하기 위해 설계됨.
• 데이터베이스 및 파일 시스템의 표준 인덱스 구조.

⚙️ B-트리의 규칙:

1. 모든 키는 오름차순 정렬.
2. 각 노드는 (M-1)개의 키와 M개의 자식 포인터를 가짐.
3. 모든 리프 노드는 같은 깊이.
4. 자식 노드는 부모 키의 구간에 속하는 값만 포함.
5. 키 개수가 너무 많아지면 분할(Split), 너무 적어지면 병합(Merge)

📊 3. 이진 탐색 트리(BST)와 B-트리의 주요 차이점

구분	이진 탐색 트리 (BST)	B-트리 (B-Tree)
자식 수	최대 2개 (left, right)	최대 M개 (M-Way Tree)
노드당 키 수	1개 (이진)	최대 M-1개
트리 높이	편향되면 높이가 커짐 (O(n))	자식 수가 많아 높이가 낮음 (O(log n))
디스크 I/O	깊이가 깊어 디스크 접근이 잦음	한 번에 많은 키를 읽어 I/O 최소화
균형 유지	편향되면 성능 저하 (균형 트리 필요)	자동으로 균형 유지 (모든 리프 동일 깊이)
용도	메모리 내 탐색용 (예: TreeMap)	대규모 데이터, 데이터베이스 인덱스, 파일시스템

 

 

📈 4. B-트리와 BST의 시각적 비교 (그림 포함)

📍 (1) 이진 탐색 트리 (BST) 예제:

BST는 자식이 2개뿐이라, 데이터가 많아지면 트리가 매우 깊어질 수 있음.

30       /  \     20    50    /     /  \   10    40   60

 

 

📍 (2) B-트리 예제 (M=4):

B-트리는 하나의 노드에 여러 키를 담아 트리의 높이를 크게 줄임.

[30 | 50]          /     |     \   [10 | 20] [40]   [60 | 70 | 80]

• 한 번의 디스크 접근으로 여러 키를 검색할 수 있음.
• 트리 높이가 낮아져 탐색 속도가 빨라짐.

---

🚀 5. B-트리가 BST보다 더 나은 이유 (특히 DB에서):

• 📉 트리의 높이가 낮아짐:
  • 높이가 O(log n)로 매우 낮음, 데이터가 수백만 건이어도 효율적.
• 💾 디스크 I/O 감소:
  • 노드 1개 = 디스크 블록 1개
  • 한 번에 여러 키를 읽어 I/O 비용 최소화
• 🔄 자동 균형 유지:
  • 삽입/삭제 시 노드 자동 분할 및 병합으로 항상 균형(Balanced) 유지.
• 📂 데이터베이스 인덱스 최적화:
  • MySQL(InnoDB), PostgreSQL, Oracle은 모두 B+Tree 기반 인덱스 사용.

---

💡 6. 요약: B-트리가 BST를 개선한 이유

🚩 BST의 단점	🚀 B-트리에서 해결한 점
편향되면 높이가 깊어져 느림	다중 자식(M-Way)으로 트리 높이를 낮춤 (O(log n))
자식 수가 2개라 디스크 I/O 증가	한 번에 여러 키와 자식을 저장해 I/O 최소화
균형을 유지하려면 AVL/Red-Black 필요	삽입/삭제 시 자동으로 균형 유지
메모리 내 탐색에 적합	디스크 기반 대규모 데이터 처리에 최적화

 

• BST는 메모리 내 탐색용으로 좋지만, **대규모 데이터 처리(DB)**에는 비효율적입니다.
• B-트리는 트리 높이를 낮추고, I/O 비용을 줄여 대규모 데이터베이스에 최적화된 구조입니다.

🌳 B-Tree 노드 vs B+Tree 노드 차이점 및 개선점

---

📌 1. B-Tree와 B+Tree 노드 구조 차이

📊 (1) B-Tree 노드 구조

• 한 노드에 키(key)와 데이터(data) 모두 저장.
• 리프 노드와 내부 노드 모두 데이터를 가짐.
• 탐색 시 리프에 도달하지 않아도 데이터를 찾을 수 있음.

---------------------------------------------------------------------------------------------------

 

• 모든 노드에 키와 데이터가 함께 저장됨.
• 범위 탐색 시 리프 노드뿐 아니라 여러 노드를 탐색해야 함.

 

[30]            /   \      [10, 20]  [40, 50, 60]

 

 

• 탐색 예시 (키: 50):
  1. 루트(30) 비교 → 오른쪽 자식 이동
  2. 자식 노드에서 [40, 50, 60] 중 50 탐색
• 범위 검색: 루트부터 탐색해야 하므로 속도가 느림.

 

 

📊 (2) B+Tree 노드 구조 (B-Tree 개선판)

• 모든 데이터는 리프 노드에만 저장.
• 내부 노드(인덱스 노드)에는 키(key)만 저장.
• 리프 노드는 양옆으로 연결리스트(Linked List)되어 있음.
• 범위 검색 및 순차 탐색(RANGE QUERY)이 빠름.

[30 | 50]           /         \      [10, 20]     [40, 50, 60]          ↔            ↔

 

 

• 탐색 예시 (키: 50):
  1. 루트(30, 50) 비교 → 오른쪽 자식 이동
  2. 리프 노드 [40, 50, 60]에서 바로 데이터 탐색
• 범위 검색: 리프 노드를 Linked List로 따라가서 빠르게 검색.

 

 

💡 2. B+Tree의 주요 개선점 및 장점

📌 (1) 디스크 I/O 감소 (대규모 데이터 최적화)

• 내부 노드에 데이터 없음 → 한 노드에 더 많은 키(key) 저장
  ⇒ 트리 높이 감소 → 디스크 I/O 최소화.
• 대규모 데이터(수백 GB ~ 수 TB)에서 효율적.

---

📌 (2) 빠른 범위 검색 (Range Query)

• 리프 노드가 Linked List로 연결되어 있음.
  ⇒ WHERE BETWEEN 쿼리 등 순차 탐색이 매우 빠름.
• B-Tree는 범위 탐색 시 리프 노드를 모두 탐색해야 함.

---

📌 (3) 일관된 트리 구조 (Insert/Delete 시 구조 안정성)

• 데이터는 항상 리프 노드에만 저장
  ⇒ 삽입/삭제 시 내부 노드 구조 영향 적음
  ⇒ B-Tree보다 구조 재조정이 빠르고 간단함.

---

📌 (4) 효율적인 메모리 캐싱 (DBMS 성능 향상)

• 내부 노드에 데이터가 없고 키만 있음 → 더 작은 노드 크기 → 메모리 캐싱 효율적.
• 트리 깊이 얕아짐 → 탐색 시 캐싱 효율성 증가.

---

🛠️ 3. 왜 B+Tree가 데이터베이스에서 주로 사용될까?

 

🚩 B-Tree 단점	🚀 B+Tree의 해결 방식
디스크 I/O 많음	내부 노드에 데이터 제거 → 한 노드에 많은 키 저장 → 트리 높이 감소
범위 탐색 느림	리프 노드를 Linked List로 연결 → 빠른 순차 탐색
삽입/삭제 시 재조정 복잡	데이터는 리프에만 저장 → 내부 노드 영향 최소화
메모리 캐싱 효율 낮음	내부 노드는 키만 저장 → 작은 크기 → 캐싱 효율 향상

---

 

🌳 AVL Tree 개념과 동작 원리: BST의 편향 문제 해결

---

📌 1. AVL Tree란?

**AVL Tree(Adelson-Velsky and Landis Tree)**는 **이진 탐색 트리(BST)**에서 발생하는 편향(Skew) 문제를 해결하기 위해 **자기 균형(Self-Balancing)**을 유지하는 이진 탐색 트리입니다.

 

🧩 2. 왜 AVL Tree가 필요한가? (BST의 편향 문제)

🚩 BST의 문제: 편향(Skewed) 트리

 

일반적인 **이진 탐색 트리(BST)**는 삽입 순서에 따라 한쪽으로 쏠릴 수 있습니다. 이를 **편향 트리(Skewed Tree)**라고 하며, 이 경우 **탐색 속도가 O(N)**까지 느려집니다.

 

📊 예제: BST의 편향 문제

입력 순서: 10 → 20 → 30 → 40 → 50

BST (편향 트리):     10       \        20          \           30             \              40                \                 50

 

탐색 복잡도: O(N) (연결 리스트와 동일한 성능 저하)

 

💡 3. AVL Tree는 어떻게 편향 문제를 해결할까?

 

📌 (1) 균형 조건 (Balance Factor)

• 각 노드의 Balance Factor(BF):
   

  BF = (왼쪽 서브트리 높이) - (오른쪽 서브트리 높이)

   
• AVL Tree의 조건: 모든 노드의 BF는 -1, 0, +1만 가능해야 함.
  ⇒ 만약 이 범위를 벗어나면 **"회전(Rotation)"**을 통해 균형을 맞춤.

📊 [예제] LL (Left-Left) 회전 예제

삽입 순서: 10 → 20 → 30

1️⃣ BST (편향 발생):

10       \        20          \           30 (Balance Factor가 +2 → LL Case)

2️⃣ LL 회전 (Single Right Rotation):

20      /  \    10   30

✅ 균형 회복 (모든 노드 BF: -1, 0, +1)
✅ 탐색 복잡도: O(log N) 유지

 

📊 [예제] RR (Right-Right) 회전 예제

삽입 순서: 30 → 20 → 10

 

1️⃣ BST (편향 발생):

30       /     20    /   10 (Balance Factor가 -2 → RR Case)

2️⃣ RR 회전 (Single Left Rotation):

20      /  \    10   30

✅ 균형 회복 (모든 노드 BF: -1, 0, +1)
✅ 탐색 복잡도: O(log N) 유지

 

💡 4. AVL Tree의 장점과 특징

🚀 특징	📝 설명
균형 유지 (Self-Balancing)	모든 노드의 높이 차이(BF)가 -1, 0, +1로 유지
빠른 탐색 (O(log N))	균형 유지 덕분에 탐색, 삽입, 삭제 모두 O(log N)
회전(Rotation)으로 복구	균형이 깨지면 회전을 통해 즉시 복구
BST 대비 성능 안정성 확보	BST의 최악 O(N) 상황을 방지

 

• BST의 편향 문제(Skew Problem)를 해결하기 위해 나온 자기 균형 이진 탐색 트리
• **Balance Factor (BF)**와 **회전(Rotation)**을 통해 항상 O(log N) 유지
• 읽기(read)가 많은 시스템에 적합 (e.g. 메모리 캐싱, 인메모리 데이터베이스 등)
• Red-Black Tree는 쓰기(write)가 많을 때 더 유리함

🟥⚫ Red-Black Tree: 등장 배경, AVL Tree와의 차이점 및 개선점

---

📌 1. Red-Black Tree란?

 

Red-Black Tree는 자기 균형 이진 탐색 트리(Self-Balancing Binary Search Tree) 중 하나로, AVL Tree의 단점(높은 회전 비용)을 개선하기 위해 만들어졌습니다.

 

💡 등장 배경:

• AVL Tree는 삽입/삭제 시 균형을 유지하려고 **회전(Rotation)**을 자주 수행하여 삽입/삭제 성능이 낮아짐.
• Red-Black Tree는 회전 비용을 줄이고 삽입/삭제 시 균형을 더 효율적으로 유지하기 위해 1978년 Bayer와 Guibas가 고안.
• 현재 자바의 TreeMap, TreeSet, C++의 std::map, std::set, Linux 커널 파일 시스템 등에 사용됨.

---

🧩 2. Red-Black Tree의 규칙 (색깔 규칙으로 균형 유지)

Red-Black Tree는 각 노드에 Red(빨간색) 또는 Black(검은색) 속성을 부여해 균형을 유지합니다.

 

✅ Red-Black Tree 규칙(5가지)

1. 각 노드는 빨간색(Red) 또는 검은색(Black) 중 하나이다.
2. 루트 노드는 항상 검은색이다.
3. 모든 리프 노드(NIL)는 검은색이다.
4. 빨간색 노드는 빨간색 자식을 가질 수 없다. (Red는 Red와 연속될 수 없음, Red 위에는 반드시 Black)
5. 모든 경로에서 리프(NIL) 노드까지의 검은색 노드 수는 같아야 한다. (Black-height 동일)

📊 Black-height란?

• 루트에서 리프까지 가는 경로에서 만나는 검은색 노드의 개수.
• Red-Black Tree는 Black-height가 모든 경로에서 같게 유지됨으로써 균형을 유지합니다.

---

💡 3. AVL Tree와 Red-Black Tree의 차이점과 개선점

구분	AVL Tree	Red-Black Tree
균형 조건	모든 노드의 Balance Factor(BF): -1, 0, +1 유지	Black-height 동일 (균형 완화)
회전 빈도	삽입/삭제 시 회전이 자주 발생	삽입/삭제 시 회전이 덜 발생 (빠름)
탐색 성능	탐색 속도 빠름 (O(log N)) (높이 더 낮음)	탐색 속도 **O(log N)**으로 거의 동일
삽입/삭제 성능	삽입/삭제 느림 (회전 많음)	삽입/삭제 빠름 (회전 적음)
사용 사례	읽기(read)가 많은 시스템	쓰기(write)가 많은 시스템 (DB, TreeMap, TreeSet)

 

🧩 4. Red-Black Tree 예제와 회전 과정

📌 [예제] Red-Black Tree 삽입 및 회전 과정

삽입 순서: 20 → 15 → 30 → 10 → 18 → 25 → 40 → 16

 

1️⃣ 초기 삽입:

20(B)    /    \   15(R)  30(R)

 

2️⃣ 18 삽입 (Red) → 규칙 위반 (연속된 Red):

20(B)    /    \   15(R)  30(R)     \     18(R)  ← Red-Red Conflict 발생

 

문제 발생: Red-Red Conflict

• Red-Red Conflict가 발생합니다. 왜냐하면 **15와 18이 빨간색(Red)**이기 때문입니다. Red-Black Tree 규칙에 따르면, 연속된 빨간색 노드는 허용되지 않음.

이 상태에서 Red-Black Tree의 균형을 맞추기 위해 회전과 색상 변경을 수행해야 합니다.

 

 

 

3️⃣ 해결 방법: 색상 변경 및 회전(LR Case):

• 색상 교체: 15 → Black, 20 → Red
• Left Rotation 후 Right Rotation(LR 회전)

18(B)    /    \   15(R)  20(R)            \            30(R)

 

 

이 문제를 해결하기 위한 절차는 다음과 같습니다:

1. 회전 및 색상 변경:

• 15는 빨간색이고, 20은 검은색이므로 회전 및 색상 변경을 진행합니다.
• 15와 20의 색상은 바뀌고, 트리 구조는 Left Rotation을 통해 균형을 맞춥니다.

2. 회전 과정 설명:

• Left Rotation: 20이 **자식 노드(15)**보다 크므로, 20을 왼쪽으로 회전시켜 18이 새로운 Root가 되도록 합니다.
• 색상 변경: 18은 검은색으로 바뀌고, 15와 20은 빨간색으로 변경됩니다.
• 이렇게 회전 및 색상 변경이 이루어짐으로써 트리의 균형을 맞추게 됩니다.

18(B)    /    \   15(R)  20(R)            \            30(R)

 

3. 왜 3 depth에서 2 depth로 바뀌었는가?

• 최초 트리에서 Depth가 3이었지만, 회전 후에는 트리가 2 depth로 줄어든 이유는 Root가 18로 변경되었기 때문입니다. 회전 후 18이 루트 노드가 되며, 15와 20은 1단계 아래에 위치하게 되어 전체 트리의 높이가 줄어들었습니다.

---

4. 왜 20이 Root에서 18이 Root로 바뀌었는가?

• 20이 Root였지만, 삽입 과정에서 발생한 Red-Red Conflict를 해결하기 위해 회전을 했고, 이 회전 결과 18이 새로운 Root로 올라갔습니다.
• Left Rotation 과정에서 20이 18의 자식 노드가 되었고, 그에 따라 18이 Root로 승격되었습니다.

---

5. 30은 어디로 갔는가?

• 30은 여전히 트리에 남아 있습니다. 다만, 30은 18의 오른쪽 자식으로 변경되지 않은 채 그대로 위치합니다. 즉, 30은 회전의 영향을 받지 않으므로 변경되지 않고 그대로 트리의 우측에 남아 있습니다.

📊 [예제] Red-Black Tree의 Black-height 유지 원리

모든 리프(NIL) 노드까지의 검은색 노드 수가 동일해야 합니다.

20(B)        /    \     15(R)   30(R)     /  \    /   \   10(B) 18(B) 25(B) 40(B) 모든 리프까지 Black-height = 2 (일정함)

 

🚀 Red-Black Tree의 장점과 사용 사례

✅ 장점:

• 쓰기(삽입/삭제)가 많은 경우 성능이 뛰어남:
  회전(Rotation)이 AVL Tree보다 적게 발생 → 쓰기(write) 성능 향상
• 탐색 성능 유지:
  최악의 경우에도 **O(log N)**을 보장

📌 사용 사례:

• Java의 TreeMap, TreeSet: Red-Black Tree 기반
• C++ STL의 map, set, multimap, multiset: Red-Black Tree 사용
• Linux 커널의 Completely Fair Scheduler(CFS)
• Database 시스템의 인덱스(B-Tree와 함께 사용됨)

---

💡 6. 요약: AVL Tree vs. Red-Black Tree

• AVL Tree:
  • 탐색 성능 최적화 (O(log N))
  • 삽입/삭제 성능 저하 (회전 많음)
  • 읽기(read)가 많은 환경에 적합
• Red-Black Tree:
  • 균형 조건 완화 → 삽입/삭제 성능 향상
  • 탐색 성능도 O(log N) 유지 (거의 동일)
  • 쓰기(write)가 많은 환경에 적합 (DB, TreeMap, TreeSet)