업글인간 업글인간

완전이진트리 부모의 우선 순위 > 자식의 우선 순위 종류 –최소힙(Minimum Heap) : 키 값이 작을수록 높은 우선순위 –최대힙(Maximum Heap) : 키 값이 클수록 높은 우선순위 이진 탐색 트리 왼쪽 서브 트리 key ) return search(node->left, key); (2) else return sear ch(node->right, key); (3) } 삽입 – 먼저 탐색하다가 – 탐색에 실패한 위치에 새로운 노드를 삽입 void insert_node(TreeNode **root, int key) { TreeNode *p, *t; // p는 부모노드, t는 현재노드 TreeNode *n; // n은 새로운 노드 t = *root; p = NULL; // 탐색을 먼저 수행 whi..

순회(traverse) : 트리의 노드들을 차례로 방문하는 것 –전위 순회(preorder) •자손보다 루트 노드를 먼저 방문. VLR –중위 순회(inorder) •왼쪽 자손, 루트, 오른쪽 자손의 순으로 방문. LVR –후위 순회(postorder) •자손을 먼저 방문한 후 루트 노드 방문 - 레벨 순회 : 각 노드를 레벨 순으로 순회 --> 큐 이용 수식 트리 계산 1. 후위 순회를 사용 (자손 먼저) 2. 서브트리의 값을 순환 호출로 계산 3. 비단말노드를 방문할 때 양쪽 서브트리의 값을 노드에 저장된 연산자를 이용하여 계산한다. int evaluate(TreeNode *root) { if( root == NULL) //빈 트리 return 0; if( root->left == NULL && ro..

- 계층 구조 (부모 & 자식 관계) - n개의 노드를 갖는 이진 트리의 높이 최대 n 최소⌈log_2⁡(n+1)⌉ - 완전 이진 트리(complete b-tree) 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리 - 이진 트리 구현 --> 배열 : 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법 –노드 i의 부모 노드 인텍스 = i/2 –노드 i의 왼쪽 자식 노드 인텍스 = 2i –노드 i의 오른쪽 자식 노드 인텍스 = 2i+1 --> 링크 : –연결 리스트처럼 포인터를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법 더보기 typedef struct TreeNode { ..

데이터 + 다음 노드 가리키는 포인터 --> 연결리스트 구조체 삽입 더보기 // phead: 리스트의 헤드 포인터의 포인터 // p : 선행 노드 // new_node : 삽입될 노드 void insert_node(ListNode **phead, ListNode *p, ListNode *new_node) { if( *phead == NULL ){ // 공백리스트인 경우 new_node->link = NULL; *phead = new_node; } else if( p == NULL ){ // p가 NULL이면 첫번째 노드로 삽입 new_node->link = *phead; *phead = new_node; } else { // p 다음에 삽입 new_node->link = p->link; p->link =..

퀵 정렬 2개로 비균등 분할 -> 각 부분 리스트 퀵 정렬 (재귀 호출) : 각 리스트에서 피벗 선택 왼쪽 - 피벗보다 작은 수/ 오른쪽 - 피벗보다 큰 수 s-->

오른차순 / 내리차순 정렬 알고리즘 평가 --> 비교 횟수 --> 이동 횟수 단순 & easy, but 비효율적 : 삽입 정렬, 버블 정렬, 선택 정렬 복잡 & difficult, but 효율적 : 퀵 정렬, 힙 정렬, 합병 정렬 삽입 정렬 정렬된 부분에 새로운 데이터 삽입 정렬 안된 부분에서 작은 수 가져오기 // 삽입정렬 void insertion_sort(int list[], int n) { int i, j, key; for(i=1; i=0 && list[j]>key; j--) //key 값이 previous(j)보다 작으면 list[j+1] = list[j]; // 레코드의 오른쪽 이동 list[j+1] = key; } } 복잡도 : O(n^2) 최선의 경우 O(n) : 이미 정렬되어 있는 경우 ..

관의 모양의 자료 구조 - 들어오는 구멍 != 나오는 구멍 (선입선출; FIFO) 큐의 ADT Objects : 0개 이상 n개의 원소를 가진 유한 순서 리스트 Functions : Queue CreateQueue( Queuesize ) : Queuesize 크기의 배열 만들기. Bool is_emptyQ( queue ) : queue 가 빈 상태인가 Bool is_fullQ( queue ) : queue 가 Full 상태인가 Queue AddQ( queue, item ) : queue 에 item 추가하기 Element DeleteQ( queue ) : queue 에서 item 하나 가져오기(제거됨) Enqueue( n ) – 큐에 데이터 n을 추가(뒤쪽, rear 다음 위치, rear++) , 가득 ..