Data Structure
-
[정글 WEEK06_RB-Tree] 기본 개념 - 회전Data Structure 2025. 4. 17. 21:14
자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)의 일종인 RB Tree(Red-Black Tree)의 '회전'에 대해서 알아보자.회전회전이란, 삽입/삭제로 인해 레드블랙 트리의 특성이 위반된 상태를 복구해주기 위해 일부 노드들의 색깔과 포인터를 변경하는 과정이다. 아래 그림은 우회전과 좌회전의 도식이다.회전은 x와 y를 연결하는 링크를 중심축으로 적용되며, α, β, γ는 서브트리이다. ↪️ 우회전목적: 왼쪽 서브트리의 쏠림현상 해결1. NIL이 아닌 x를 설정한다.2. x의 오른쪽 서브트리(β)를 y의 왼쪽 서브트리로 옮긴다.3. y의 부모를 x로 설정한다.4. y를 x의 오른쪽 자식으로 만든다.🧚🏻 x는 서브트리의 새로운 루트가 되고, y는 x의 오른쪽 ..
-
[정글 WEEK06_RB-Tree] 기본 개념 - 특성Data Structure 2025. 4. 17. 17:31
자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)의 일종인 RB Tree(Red-Black Tree)를 알아보자.특성레드블랙 트리는 노드 삽입, 삭제 시 색깔 규칙과 회전 연산을 통해루트 노드에서 NIL 노드까지의 경로에 있는 블랙 노드의 개수를 제한함으로써 균형을 유지한다.어떤 경로도 다른 경로보다 두배 이상 길지 않음을 보장하며, 모든 동적 집합 연산을 트리의 높이에 비례해서 O(log n) 시간에 수행한다. "어떤 트리에서 루트 노드부터 NIL 노드까지 가는 경로 중 가장 짧은 경로는 블랙 노드로만 N개(bh(x))로 구성된 경로이며, 가장 긴 경로는 N개의 블랙 노드와 N개의 레드 노드가 번갈아 나오는 경로로 2N(2*bh(x))개의 노드로 구성된다. 따라서..
-
[정글 WEEK05_C언어, 자료구조] Binary Tree 5번_mirrorTreeData Structure 2025. 4. 15. 16:31
TODO1. 이진 트리를 좌우 반전시키기(mirrorTree) 제약사항1. 중위순회(in-order traversal) 사용📦 구조체 분석1. BTNode: 이진 트리를 구성하는 노드 - item: 노드가 가지고 있는 int 타입 데이터 - left: 왼쪽 자식 노드를 가리키는 포인터(자기 참조 구조) - right: 오른쪽 자식 노드를 가리키는 포인터(자기 참조 구조)typedef struct _btnode { int item; struct _btnode *left; struct _btnode *right;} BTNode; 2. StackNode: 트리의 노드를 임시 저장하는 스택의 요소. BTNode가 스택에 들어간 순서를 표현하기 위해 필요 - btnode: 이진트리..
-
[정글 WEEK05_C언어, 자료구조] Linked List 4번_moveEvenItemsToBackData Structure 2025. 4. 14. 15:15
TODO짝수값을 가진 노드를 뒤로 보내기(moveEvenItemsToBack) 연결리스트 3번 - 홀수값을 가진 노드를 뒤로 보내기와 뒤로 보낼 노드가 짝수냐, 홀수냐를 제외하고는 동일한 문제이다.3번 문제는 인덱스 기반으로 기존 함수를 호출해서 푼 관계로 성능 이슈가 있어서 이번 문제에서는 포인터 기반으로 구현했다. 📦 구조체 분석1. ListNode: 연결리스트를 구성하는 노드 - item: 해당 노드가 가지고 있는 int 타입 데이터 - next: 다음 노드의 주소typedef struct _listnode { int item; struct _listnode *next;} ListNode; 2. LinkedList: 연결 리스트 - size: 연결 리스트가 가지고 있는 노드의..
-
[정글 WEEK05_C언어, 자료구조] Linked List 3번_moveOddItemsToBackData Structure 2025. 4. 14. 15:14
TODO홀수값을 가진 노드를 뒤로 보내기(moveOddItemsToBack) 📦 구조체 분석1. ListNode: 연결리스트를 구성하는 노드 - item: 해당 노드가 가지고 있는 int 타입 데이터 - next: 다음 노드의 주소typedef struct _listnode { int item; struct _listnode *next;} ListNode; 2. LinkedList: 연결 리스트 - size: 연결 리스트가 가지고 있는 노드의 개수 - head: 연결 리스트의 첫 번째 노드의 주소typedef struct )_linkedlist { int size; ListNode *head;} LinkedList; 🪄 기존 함수 분석printList(Linked..
-
[정글 WEEK05_C언어, 자료구조] 구조체, 포인터, 구조체 포인터, 성공적Data Structure 2025. 4. 12. 21:09
⚡️ 구조체란여러 개의 서로 다른 타입의 변수들을 하나로 묶어주는 '사용자 정의 자료형'이다. 구조체를 구성하는 변수는 '멤버' 또는 '멤버 변수'라고 한다. 🔗 자바의 클래스가 하나의 객체를 구성하는 여러 속성(필드)을 포함하듯이, 구조체도 하나의 의미있는 개체를 표현하기 위해서 여러 멤버를 묶는다는 측면에서 클래스의 개념과 비슷하게 느껴졌다. 🪄 구조체는 다음 두 가지 형태로 정의할 수 있다. 1️⃣ 일반적인 형태struct 구조체이름{ 멤버1의타입 멤버1의이름; 멤버2의타입 멤버2의이름; ...}e.g. 일반적인 형태의 구조체 사용 예제1) 구조체 정의 & 선언구조체의 정의와 선언을 따로 할 수도 있고, 구조체를 정의할 때 선언까지 한 번에 할 수도 있다.구조체 이름은 주로 P..