2025.04.21

TIL(TODAY I LEARN)

---

• 오늘한 내용 : 고급 자료 구조 : AVL 트리, 개념 : 지정자, 한정자

• WEEK06: 메모리 누수, 균형 이진 탐색 트리(AVL Tree, Red-Black Tree)

---

AVL 트리 (Adelson-Velsky and Landis Tree)

1. 정의

• 자기 균형 이진 탐색 트리 (Self-Balancing Binary Search Tree)의 일종.
• 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이(= 균형 인수)가 1, 0, 1 중 하나여야 함.

---

2. 균형 인수 (Balance Factor)

• 정의: BF(node) = height(left subtree) - height(right subtree)
• 허용 범위: -1, 0, 1 → 이 범위를 벗어나면 회전(Rotation)을 통해 균형을 맞춰야 함
  

---

3. 회전 종류

유형	조건	해결 방법
LL (Left-Left)	삽입 노드가 왼쪽 자식의 왼쪽에 추가됨	오른쪽 회전 (Right Rotation)
RR (Right-Right)	삽입 노드가 오른쪽 자식의 오른쪽에 추가됨	왼쪽 회전 (Left Rotation)
LR (Left-Right)	왼쪽 자식의 오른쪽에 추가됨	왼쪽 회전 후 오른쪽 회전
RL (Right-Left)	오른쪽 자식의 왼쪽에 추가됨	오른쪽 회전 후 왼쪽 회전

---

4. 연산 시간 복잡도

연산	시간 복잡도
탐색	O(log n)
삽입	O(log n)
삭제	O(log n)

---

5. AVL vs 일반 BST

항목	BST	AVL
균형 유지	보장 안 됨	항상 유지
최악 시간복잡도	O(n)	O(log n)
삽입/삭제 복잡도	간단	회전 필요
사용처	삽입/삭제 적은 경우	검색 속도 중요한 경우

---

6. 삽입 시 처리 과정 요약

1. BST 삽입 방식으로 노드 추가
2. 부모 노드로 올라가며 균형 인수(BF) 계산
3. BF가 ±2 이상이면 회전 수행
4. 회전 후 트리 재구성 및 높이 갱신

---

7. 삭제 시 처리 과정 요약

1. 일반 BST 삭제 방식으로 노드 삭제 수행

   → 단말 노드, 하나만 자식 가지는 노드, 두 자식 가지는 노드(후계자/선행자) 처리

2. 부모 노드로 올라가며 균형 인수(Balance Factor, BF) 확인

3. BF가 ±2로 벗어난 경우, 회전 수행해 균형 회복

4. 높이 갱신은 삭제된 노드의 부모부터 루트까지 순차적으로 진행

---

Red-Black Tree와의 비교

항목	AVL Tree	Red-Black Tree
균형 유지 정도	더 엄격하게 유지	느슨하게 유지
삽입/삭제 후 회전 수	많을 수 있음	평균적으로 더 적음
검색 성능	더 좋음	조금 떨어짐
삭제 성능	느릴 수 있음 (회전 많음)	더 빠를 수 있음 (회전 적음)

• 검색 속도 중요하면 AVL
• 삽입/삭제 잦은 시스템이면 Red-Black Tree를 많이 씀 (예: STL의 map, set)

---

지정자(specifier)와 한정자(qualifier)는 C 언어에서 변수나 함수의 “속성”을 정의하기 위해 붙이는 키워드

지정자(specifier)

• 무엇을 제어하나?
  • 링크성(linkage): 해당 심볼(변수·함수)을 다른 번역 단위에서 참조할 수 있는지
  • 저장 기간(storage duration): 언제 메모리에 생성되고 소멸되는지
  • (함수 지정자의 경우) 함수 인라이닝이나 반환 행동 등

한정자(qualifier)

• 무엇을 제어하나?
  • 변수나 포인터가 값을 변경할 수 있는지,
  • 컴파일러 최적화 시 제약을 둘 것인지,
  • 원자성이나 별칭(aliasing) 여부 등을 명시

1. 저장 클래스 지정자 (Storage‑class specifiers)

키워드	의미
auto	(C99 이후엔 거의 쓰이지 않음) 지역 변수의 자동 저장 기간 (함수 진입 시 생성/종료 시 소멸).
register	(힌트) 변수 접근을 레지스터에 최적화하도록 요청. 현대 컴파일러에겐 무시되기도 함.
static	전역(파일) 범위에선 내부 연결성(internal linkage).• 지역에선 정적 저장 기간.
extern	전역 심볼에 대한 외부 연결성(external linkage): 다른 번역 단위에서 선언 가능.
thread_local (C11/C++11)	쓰레드별 정적 저장 기간: 각 스레드마다 별도 인스턴스 유지.

// 전역 변수
extern int  g_value;             // 다른 파일(번역 단위)에서 정의된 g_value를 참조
static  int  s_value = 10;       // 이 파일 내에서만 보이는 g_value

void foo(void) {
    auto    int x = 0;           // (묵시적) 지역 변수
    register int y = 1;          // (힌트) y를 레지스터에 둬 보란 의미
    thread_local static int z;   // 쓰레드마다 한 번 초기화되는 정적 변수
}

---

2. 타입 한정자 (Type qualifiers)

키워드	의미
const	읽기 전용(불변)
volatile	컴파일러 최적화 방지: 매번 메모리에서 읽고 써야 함
restrict (C99)	포인터 별칭(aliasing) 정보 제공: 최적화에 도움
_Atomic (C11)	원자적 연산 보장 (멀티스레드 환경)

const int *p1;    // *p1 읽기 전용
int * const p2;   // p2 값(포인터 주소) 변경 불가
volatile int flag;   // 하드웨어 레지스터나 인터럽트 변수

---

3. 함수 지정자(Function specifiers) 및 C++ 한정자

키워드	의미
inline	인라이닝 요청: 호출 오버헤드 제거(함수 본문을 호출 부에 삽입)

inline int add(int a, int b) { return a + b; }

---

요약

1. 저장 클래스: auto, register, static, extern, thread_local
2. 타입 한정자: const, volatile, restrict(C), _Atomic(C11)
3. 함수·언어 확장: inline