매일을 설렘으로

Red-Black Tree 개요 Self-balancing binary search tree ( tree의 height를 h = log2(N)으로 유지) 이 외에도 AVL Tree, B-tree 등이 있다. BST (Binary Search Tree)와 동일한 원리 (key 대소 관계로 구성) Red-Black tree의 경우, Node color / BH (black height)로 균형 유지 시간복잡도상 항상 O(logN)을 유지한다. (탐색/삽입/삭제) Tree의 특징 아래의 특징은 그냥 균형을 맞추기 위해 필요한 조건이라고 보면 좋을 듯 하다. (그냥 받아들이면 된다.) Red/Black Property: Every node is colored, either red or black. Root Pr..

typedef 함수 (형 재정의) 특정 element에 대해 미리 type (int, long, double, pointer 등) 지정해서 사용하는 함수이다. 문법은 다음과 같다. typedef type element 장점 : 이식성과 수정 효율성이 좋다. 예를 들어, 프로그래밍 컨셉이 바껴 특정 element의 type을 int형 -> double형으로 변경할때 // typedef 사용 예시 typedef int key_t; // 포인터형도 typedef를 사용해서 *없이 선언할 수 있다. typedef int* intPtr; intPtr p, q; 열거형(enum) 변수가 갖는 값에 의미를 부여해 프로그램 가독성을 높임 컴파일러는 열거형 멤버들을 정수형 상수로 인식 (문자도 indexing으로 사용 ..

C를 활용한 stack 자료 구조 구현 전체 구조 #include #include #define SIZE 100 // stack struct 구성 typedef struct stack { // arr[SIZE], top int arr[SIZE]; int top; } stack; // init 함수 void init(stack *s) { s -> top = -1; // stack에 초기상태 -1, Push해서 data 들어오면 0부터 index시작 } // is_empty 함수 구성 int is_empty(stack *s) { if (s->top == -1) return 1; return 0; } // is_full 함수 구성 int is_full(stack *s){ if (s->top == SIZE - ..

이진 트리 (Bianary Tree) 배열, 링크드리스트, 스택, 큐와 같이 일직선 개념의 자료구조가 아니라 비선형 자료구조인 부모-자식 개념을 가지는 자료구조이다. 데이터를 트리 구조로 배열 할 때 트리 맨 위에있는 노드를 루트 노드라고합니다. 전체 트리에 대해 하나의 루트 만있을 수 있습니다. 루트 노드를 제외한 모든 노드에는 노드 위쪽에 하나의 가장자리가 있습니다. 이를 부모 노드라고합니다. 부모 코드 아래의 노드를 자식 노드라고합니다. 각 상위 노드에는 최대 2 개의 하위 노드가있을 수 있습니다. 왼쪽 자식 노드와 오른쪽 자식 노드라고합니다. 자식 노드가없는 노드를 리프 노드. 이진 검색 트리 (binary search tree)란, 이진 탐색 트리는 기본적인 특징은 이진 트리와 같지만 하나 다른..