[CS기초] 6주차 개념 정리

6주차 개념 정리

아래의 내용을 코드 블럭 우측 상단의 Copy 버튼을 눌러 복사한 뒤, 퀴즈 로봇(신명훈 학우 제작)의 프롬프트에 붙여넣기하면 핵심 개념들에 대한 퀴즈를 풀어볼 수 있습니다.

 

□ BST와 RB트리
BST와 RB트리, AVL트리는 정렬된 데이터를 빠르게 탐색하기 위한 트리 형태의 자료구조로, 최대 2개의 자식을 가진다.

■ BST (Binary Search Tree)
왼쪽 서브트리의 모든 값이 부모 노드보다 작고, 오른쪽 서브 트리의 모든 값이 부모 노드보다 큰 메모리 기반 이진 트리

▶ 핵심 특징
노드 구조: 각 노드는 최대 2개의 자식을 가짐
균형 보장: 불가 (→ 편향 트리가 되어 성능이 저하될 수 있음.)
적용 환경: 메모리 기반 자료구조 (RAM)
시간 복잡도: 평균 O(logN), 최악 O(N)

▶ 삽입 과정
방식: 크기를 기준으로 왼쪽/오른쪽 자식으로 재귀적으로 탐색해 삽입
균형 처리: 없음

▶ 삭제 과정
삭제 대상: 리프 노드, 한 자식 노드, 두 자식 노드
삭제 방식: 
	• 리프 노드 - 그냥 제거
	• 한 자식 노드 - 자식으로 대체
	• 두 자식 노드 - 중위 후임자(또는 선임자)로 대체
		○ 선임자: 해당 노드보다 작은 값을 가지는 노드들 중 가장 큰 값을 가진 노드
		○ 후임자: 해당 노드보다 큰 값을 가지는 노드들 중 가장 작은 값을 가진 노드
균형 처리: 없음

■ RB Tree (Red-Black Tree)
고유한 색상 규칙을 통해 균형을 자동으로 유지하여,
최악의 경우에도 탐색, 삽입, 삭제 연산을 효율적으로 처리할 수 있도록 설계된 자가 균형 이진 탐색 트리

▶ 핵심 특징
	• RB트리 규칙을 항상 만족시키도록 유지해 삽입/삭제 후에도 트리의 높이 균형을 유지한다.
		○ 규칙1: 각 노드는 Red 또는 Black의 색을 가진다
		○ 규칙2: 루트 노드는 항상 Black이다
		○ 규칙3: 모든 리프 노드(NIL 노드)는 항상 Black이다
		○ 규칙4: Red의 자식은 항상 Black이어야 한다
		○ 규칙5: 임의의 노드에서 그 자손 리프 노드에 도달하는 모든 경로에는 동일한 수의 Black이 포함되어야 한다.
	• 균형 유지 방식: 회전 및 색상 변경
	• 모든 연산의 최악 시간 복잡도 O(logN)

▶ 삽입 과정
	• 항상 Red 노드로 삽입. 삽입 과정은 일반 BST와 동일
	• 삽입 후 규칙 위반 시(Red-Red 충돌), 색상 변경 또는 회전을 통해 트리를 재조정
		○ Case3: Red가 할아버지까지 일직선으로 쏠린 상태
			§ 할아버지-형제 색상 교환 후 할아버지를 축으로 쏠린 반대방향으로 회전
		○ Case2: Red가 할아버지까지 꺾이면서 쏠린 상태
			§ 부모를 축으로 꺾인 반대방향으로 회전 -> Case3로 해결
		○ Case1: 삼촌도 Red인 상태 -> 색상 반전(Color Flip)
			§ 이후 할아버지에 대해 그 부모가 Red라면 할아버지를 대상으로 새로운 재조정 시작

▶ 삭제 과정
	• 일반 BST처럼 삭제하되, 삭제 후 Black-height가 달라질 경우, Doubly Black 문제 발생
	• 이를 해결하기 위해 형제 노드 확인, 색상 교환, 회전 등을 수행
		○ Case4: 형제가 Black이고, 형제의 자식 Red가 할아버지까지 일자로 쭉 뻗은 상태
			§ 형제에게 할아버지 색 복사 -> 할아버지와 형제의 자식 Red를 Black으로 변경
			§ 이후 할아버지를 축으로 Doubly Black 방향으로 회전
		○ Case3: 형제가 Black이고, 형제의 자식 Red가 할아버지까지 꺾인 모양인 상태
			§ 형제와 자식 Red 색 교환 -> 형제를 축으로 꺾인 반대방향으로 회전 -> Case4로 해결
		○ Case2: 형제가 Black이고, 형제의 자식이 모두 Black일 때
			§ 형제를 Red로 변경
				□ 부모가 Red면 Black으로 바꾸고 종료
				□ 부모가 Black이면 부모를 대상으로 새로운 재조정 시작
		○ Case1: 형제가 Red일 때
			§ 부모-형제 색 교환 -> 부모를 축으로 Doubly Black 방향으로 회전 -> Case2~4로 해결

■ RB트리 vs AVL트리
	• AVL 트리: 각 노드에 대해 좌우 서브트리 높이 차이가 1이하가 되도록 유지함으로써
    			균형을 유지하는 자가 균형 이진 탐색 트리이다.
		○ balance factor(균형 인수): 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이

▶ RB트리와 AVL트리 비교 정리
	• Binary Search Tree: 둘 모두 해당
	• 삽입/삭제/검색 시간복잡도: 둘 모두 최악의 경우에도 O(logN)
	• 삽입/삭제 성능:
		○ Red-Black 트리: AVL트리에 비해 빠름
		○ AVL 트리: Red-Black 트리에 비해 느림
	• 검색 성능:
		○ Red-Black 트리: AVL트리에 비해 느림
		○ AVL 트리: Red-Black 트리에 비해 빠름
	• 균형 잡는 방식:
		○ Red-Black 트리: 고유 색상 규칙을 만족시키도록 색상 교환 및 회전
		○ AVL 트리: 모든 노드의 balance factor가 {-1, 0, 1} 중 하나가 되도록 회전
	• 응용 사례:
		○ Red-Black 트리: linux kernel 내부, JAVA TreeMAP 구현, C++ std::map 구현 등
		○ AVL 트리: dictionary, 한번 만들어 놓으면 삽입/삭제가 거의 없고 검색이 대부분인 상황에서 사용
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 포인터 (Pointer)
메모리 주소를 저장하는 변수. 다른 변수나 배열, 함수 등의 주소를 가리킬 수 있다.
이를 통해 간접적인 접근과 조작이 가능하며, 동적 메모리 할당이나 함수 인자 전달 등에 널리 활용된다.

■ 포인터의 연산 (포인터 변수 ptr 기준)
	• *ptr: 포인터가 가리키는 값에 접근 (역참조)
	• ptr + n: 포인터를 n개의 요소만큼 앞으로 이동
	• ptr - n: 포인터를 n개의 요소만큼 뒤로 이동
	• ptr1 == ptr2: 두 포인터가 같은 주소를 가리키는지 비교
	• ptr++ / ptr--: 포인터를 다음/이전 요소로 이동
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 동적 메모리 할당
런타임 환경에서 필요한 만큼의 메모리를 힙 영역에 할당하여 사용하는 기법.
정적 메모리 할당보다 유연하게 데이터를 다룰 수 있으며, 할당된 메모리는 직접 해제해야 메모리 누수를 막을 수 있다.

■ 관련 함수 malloc, calloc, realloc
	• malloc: 초기화 없이 메모리를 할당하는 함수
	• calloc: 0으로 초기화된 메모리를 할당하는 함수
	• realloc: 할당된 메모리를 새 크기로 조정하는 함수
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 가상화 (Virtualization)
하나의 물리적 자원을 분할해 여러 개의 논리적 자원처럼 나눠서 사용할 수 있게 하는 기법.
서버, 스토리지, 네트워크, 운영체제 등을 가상화하여 자원 활용도를 높이고, 유연한 시스템 운영이 가능하게 함.
────────────────────────────────────────────────────────────────────────────────────────────────────
□ GCC (GNU Compiler Collection)
누구나 마음껏 사용, 수정할 수 있고 다양한 프로그래밍 언어를 지원하는 오픈소스 컴파일러 도구 모음.
코드를 기계어로 번역해 실행 가능한 프로그램으로 만드는 도구로, 크로스 플랫폼과 최적화 기능이 뛰어나다.