2025.01.08 +99강화나무

+99강화나무(정식명칭 ㄴㄴ)를 하게 된 목적:

아래와 같은 데이터가 있을 때 우리가 birth_year = 90인 행을 찾는다면?

 

name	birth_year
오리곽곽	00
정지	92
채채	90
현호우	97
욜히졸히	97
양주소주	94
심심혜	93

 

 

컴퓨터는 모든 행을 탐색하면서 해당 값을 찾을거임.

근데 만약에 행이 10만개라면? 아니면 1억개라면?

분명 컴퓨터가 죽여달라고 할 것이다.

 

그래서 우리는 보통 인덱스를 생성한다.

인덱스는 원본 데이터의 위치 정보(포인터)를 저장하고 이를 정렬하면 된다.

이때 정렬은 보통 Array나 Linked List를 사용한다.

이렇게 인덱스를 생성하게 되면 성능이 개선되긴 할 것이다. 

그러나 원본값을 수정하면 인덱스도 수정해야하는 불편함이 있다.

 

인덱스 수정이 왜 불편한지 궁금하면 펼쳐보셈

1. 성능적 측면:

• 원본 데이터 수정 시 → 인덱스 재정렬 필요
• 특히 Array로 구현된 경우, 중간 삽입/삭제 시 많은 데이터 이동 발생

2. 공간적 측면:

• 인덱스는 추가적인 저장 공간 필요
• 데이터가 자주 변경되는 경우 인덱스를 최신 상태로 유지하기 위해 필요한 추가적인 작업과 비용이 증가함
  (인덱스 관리 오버헤드(overhead))
• 너무 많은 인덱스 생성 시 저장 공간 낭비

 

 

 

 

근데 실제 인덱스들은 저런 일자 배열이 아니라 나무 형태로 정렬하고 배열해둔다.

아무렇게나 흩어져 있는 데이터를 화살표로 연결만 해두는 것이다.

 

Q. 그렇다면 어떻게 효율적이고 컴퓨터를 혹사시키지 않고 값을 찾을 수 있을까?

 

반씩 소거하면서 찾으면 된다.

 

아까처럼 흩어진 데이터나 일자 배열의 경우 컴퓨터가 모든 데이터를 뒤적뒤적 해야하지만

이렇게 찾으면 반씩 날리면서 찾기 때문에 질문 세 번만에 값을 찾는다.

이렇게 생긴 트리를 전문 용어로 BST라고 한다~ (곽곽님이 발표해줬던)

 

 

 

Q. 여기서 성능을 더 개선 시킬 수는 없어?
A. 가능

 

 

 

이렇게 하면 2/3씩 화끈하게 날리면서 데이터를 탐색할 수 있다.

대충봐도 값을 찾는게 질문 2개로 앞에 BST의 3개보다 적다

 

 

B-tree에서 4를 찾는 과정

1. 루트 노드 [8, 15] 검사

2. 4 < 8 이므로 가장 왼쪽 자식으로 이동

3. 중간 노드 [3, 5] 검사

4. 3 < 4 < 5 이므로 중간 자식으로 이동

5. 리프 노드 [4] 도달

6. 4를 찾음

 

B-tree의 특징

• 중간 노드에서도 실제 데이터를 가질 수 있음
• 찾는 값을 중간 노드에서 발견할 수 있음
• 반드시 리프 노드까지 내려가지 않을 수 있음

 

 

 

Q. 그럼 여기서 더 좋은 것도 가능해?
A. 가능

 

B+tree에서 4를 찾는 과정

1. 루트 노드 [8, 15] 검사

2. 4 < 8 이므로 가장 왼쪽 자식으로 이동

3. 중간 노드 [4] 검사

4. 4 = 4 이므로 왼쪽 자식으로 이동 (키값보다 작거나 같으면 왼쪽, 크면 오른쪽 )

5. 리프 노드 [1,2,3,4] 도달

6. 리프 노드에서 4를 찾음

 

특징

• 내부 노드들(8,15 와 4)은 단순히 길 안내 역할만 함
• 실제 데이터는 항상 리프 노드에서 찾음
• 모든 검색이 리프 노드까지 내려가므로 검색 시간이 일정함
• 리프 노드에 도달한 후 연결된 다음 값들로 쉽게 접근 가능 (링크드 리스트처럼)
• 항상 왼쪽에서 오른쪽으로 값이 커지는 순서 유지

 

 

B+트리 쉬운비유

도서관의 책 분류 시스템과 비슷허다.

 맨 위층: 대분류 (예: 100번대=철학, 200번대=종교...)

 중간층: 중분류

 맨 아래층: 실제 책들이 순서대로 꽂혀있음

 책들은 옆으로 연결되어 있어 순서대로 찾기 쉬움

 

 

 

BST, B-tree, B+tree의 노드값은 내가 정해? 아니면 정해진 값이 있어?

B-tree, B+tree, BST 모두 첫 노드값(루트)을 중간값으로 선택하는 것이 좋음

임의로 선택할 수 있긴함

 

BST로 예를 들어 보면,

1~20까지의 값이 있다면:

중간값인 10을 루트로 선택하는 것이 가장 이상적

그러면 1~9는 왼쪽 서브트리로

11~20은 오른쪽 서브트리로 들어가게 된다

 

이렇게 하면:

트리의 높이를 최소화할 수 있고 검색 성능이 O(log n)에 가깝게 유지됨.

한쪽으로 치우친 트리가 되는 것을 방지할 수 있다

🔷 단어설명
O(n): 입력값 n에 비례해서 실행 시간이 증가(빅오 엔)
O(log n): 입력값 n이 2배가 될 때마다 실행 시간이 1씩만 증가(빅오 로그 엔)

🔷 O(log n)에 가깝게 유지된다는 것이란?
BST에서 1부터 20까지의 노드를 찾는다고 가정했을 때

🔹 중간값 10을 루트로 했을 경우
높이가 거의 균형잡혀서 대부분 4~5번의 비교로 원하는 값을 찾을 수 있음
최악의 경우도 5번 이내의 비교로 찾을 수 있음
이것이 O(log n)에 가까운 성능

🔹 1을 루트로 했을 경우:
오른쪽으로만 쭉 늘어선 형태가 됨
20을 찾으려면 1부터 시작해서 20번까지 모두 비교해야 함
이는 O(n)에 가까운 성능

🔹 8을 루트로 했을 경우:
오른쪽이 더 깊어져서 일부 값들은 찾는데 더 많은 비교가 필요
균형잡힌 경우보다는 비효율적이지만
극단적인 불균형보다는 훨씬 나은 성능

"O(log n)에 가깝다"는 어떤 값을 찾더라도 전체 노드 수의 로그값에 비례하는 시간이 걸린다는 의미
데이터가 2배로 증가해도 비교 횟수는 1회만 증가하는 효율적인 상태를 의미

 

 

결론 : 아무튼 중간값으로 하는 것이 좋다~~

 

균형 잡힌 트리 구조를 만들 수 있음

리프 노드까지의 경로 길이를 최소화할 수 있음

범위 검색이 효율적임

 

 

 

 

 

 

 

 

B-tree와 B+tree의 차이점

• B+tree는 항상 리프 노드까지 가야하지만 B-tree는 중간에서 찾을 수 있음
• B+tree는 모든 데이터가 리프 노드에만 있지만, B-tree는 내부 노드에도 데이터가 있음
• B+tree는 리프 노드들이 연결되어 있어 범위 검색이 쉽지만, B-tree는 그렇지 않음

 

에? 데이터를 중간에서 찾을 수 있는 B-tree가 더 좋은거 아냐?

 

 

 

얼핏 보면 B-tree가 더 효율적으로 보일 수 있지만, B+tree가 더 좋은 이유가 있다.

 

1. 캐시 효율성

B+tree는 모든 데이터가 리프 노드에만 있어서 내부 노드들은 더 작게 유지 가능

반면 B-tree는 내부 노드에도 데이터를 저장해야 해서 같은 메모리에 더 적은 노드들만 캐시 가능

예를 들어 100MB 메모리가 있다고 가정할 때

• B+tree: 포인터만 있어서 약 1000개의 내부 노드 캐시 가능
• B-tree: 실제 데이터도 있어서 약 500개의 내부 노드만 캐시 가능

 

2. 순차 접근 성능

B+tree는 모든 데이터가 리프 노드에 연결 리스트로 연결

범위 검색이나 순차 검색 시 매우 효율적

B-tree는 트리를 위아래로 탐색해야 해서 범위 검색이 비효율적

 

3. 일관된 검색 시간

B+tree는 항상 리프까지 가야하므로 검색 시간이 일정해서 데이터베이스 시스템에서 쿼리 최적화에 유리

B-tree는 검색 시간이 불규칙할 수 있음

 

4. 구조 변경 용이성

B+tree는 데이터가 리프에만 있어 노드 분할이나 병합이 더 단순

B-tree는 내부 노드의 데이터도 고려해야 해서 더 복잡

 

예시:

데이터베이스에서 "급여가 3000에서 5000 사이인 직원 검색" 같은 쿼리

  B+tree: 3000을 찾고 연결된 리프들을 따라가면 됨

  B-tree: 여러 번 트리를 오르내려야 함

이러한 이유로 대부분의 데이터베이스 시스템은 B+tree를 선호함

 

 

---

 

 

솔직히 여기까지 하고 싶은데 재귀함수 얘기하다 하게된거라 쪼끔만 더 설명하겠음

트리 구조와 재귀함수가 밀접한 연관이 있다고 말하다가 비트리 비플트리에 대해 알려달라고 해서

이렇게 정리하게 됐잖아유? 

아무튼 트리 연산의 대부분이 재귀적으로 구현된다.<<이게 포인트

 

BST에서의 재귀:

class Node:
    def __init__(self, value):
        self.value = value    # 노드의 값
        self.left = None      # 왼쪽 자식 노드
        self.right = None     # 오른쪽 자식 노드

class BST:
    def search(self, node, value):
        # Base case: 노드가 없거나 찾는 값을 발견했을 때
        if node is None or node.value == value:
            return node
        
        # Recursive case: 값의 크기에 따라 왼쪽/오른쪽으로 이동
        if value < node.value:
            return self.search(node.left, value)  # 왼쪽 서브트리 검색
        return self.search(node.right, value)     # 오른쪽 서브트리 검색
    
    def insert(self, node, value):
        # Base case: 새로운 노드를 삽입할 위치를 찾았을 때
        if node is None:
            return Node(value)
        
        # Recursive case: 값의 크기에 따라 왼쪽/오른쪽에 삽입
        if value < node.value:
            node.left = self.insert(node.left, value)   # 왼쪽에 삽입
        else:
            node.right = self.insert(node.right, value) # 오른쪽에 삽입
        return node

 

B-tree와 B+tree에서의 재귀:

class BTreeNode:
    def search(self, key):
        # Base case: 리프 노드에 도달했을 때
        if self.is_leaf:
            return self.search_in_node(key)  # 현재 노드에서 키 검색
        
        # Recursive case: 내부 노드에서 검색
        i = self.find_index(key)           # 어느 자식으로 가야할지 인덱스 찾기
        return self.children[i].search(key) # 해당 자식으로 재귀 호출

 

재귀의 핵심 포인트:

 

1. Base case (종료 조건):

• 노드가 None일 때
• 찾는 값을 발견했을 때
• 리프 노드에 도달했을 때

2. Recursive case (재귀 호출):

• 더 작은 문제로 나누어 해결
• BST: 왼쪽/오른쪽 중 하나의 서브트리로 이동
• B-tree: 적절한 자식 노드로 이동

"이동"이라고 표현한 것이 실제로는 해당 노드를 파라미터로 하는 재귀 호출이라 할 수 있다.

재귀는 "현재 노드에서 할 일을 하고, 그 다음 노드로 넘어가서 같은 일을 반복한다"는 트리의 특성을 잘 반영함

 

3. 재귀 호출마다:

• 문제의 크기가 줄어듦 (트리의 레벨이 하나씩 내려감)
• 최종적으로 base case에 도달

 

---

 

 

찐막 카드 뭉치 문제 코드가 재귀적이냐 궁금증이 들어서 찾아봄(볼사람만 보기)

https://school.programmers.co.kr/learn/courses/30/lessons/159994

프로그래머스

def solution(cards1, cards2, goal):
    i1 = 0  
    i2 = 0  
    
    for word in goal:
        if i1 < len(cards1) and word == cards1[i1]:
            i1 += 1
        elif i2 < len(cards2) and word == cards2[i2]:
            i2 += 1
        else:
            return "No"
    
    return "Yes"

정답으로 이렇게 했는데 내가 너무 멍청하게 재귀적이지 않나 해버렸다.

이 코드는 재귀적이지 않다. 고냥 반복문을 사용한 코드다.

 

재귀의 특징과 비교해보면

 

재귀 함수의 특징:

• 함수가 자기 자신을 호출
• Base case(종료 조건)가 존재
• 매번 문제의 크기가 줄어듦
• 함수 호출 스택이 쌓임

현재 코드의 특징:

• for 루프를 사용한 단순 반복
• 인덱스(i1, i2)를 증가시키며 순차적으로 진행
• 함수가 자기 자신을 호출하지 않음
• 스택이 쌓이지 않음

아무튼 아래 4가지 조건을 달성하면 재귀 함수라 칭할 수 있다고 한다.

1. 자기 자신을 호출 (Self-referential)
2. 종료 조건 존재 (Base case)
3. 문제의 크기가 점점 줄어듬
4. 함수 호출마다 스택 프레임이 쌓임

 후기 :  for문이랑 뭔차인가 싶었는데 생각해보니까 포문은 단순 반복작업이고 재귀함수는 트리처럼 계층적 구조가 있다. 글고 재귀는 애초에 함수 호출이 n번 있으니까 n개의 스택이 쌓일 것이고, 반복문은 함수 호출도 한번이고 스택도 한번... 

 

 아무튼 재밋따.