이진 탐색 트리의 문제점 : 이진 탐색 트리의 연산은 O(log2 n)의 시간 복잡도를 가진다. 그런데 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다. 이러한 이진 탐색 트리의 단점을 해결한 트리를 가리켜 균형 잡힌 이진 트리라 하며, 그 종류 중 AVL 트리를 선택한다. 균형인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 LL회전 : LL상태 : 균형 인수 +2가 연출된 상태. RR회전 : RR상태 : 균형 인수 -2가 연출된 상태. LR회전 : LR상태 : 자식 노드가 왼쪽으로 하나, 그리고 이어서 오른쪽으로 하나 달린 상태. RR회전을 통해 LL상태로 RL회전 : RL상태 : 자식 노드가 오른족으로 하나, 그리고 이어서 왼족으로 하나 달린 상태. LL회전을 통해 RR상태로
탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 왜냐하면 효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안 되고 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야되기 때문이다. 보간탐색 이론적으로 보간 탐색과 이진 탐색의 유일한 차이점은 탐색의 대상을 선정하는 방법이다. InterpolSearch.c #include int ISearch(int ar[], int first, int last, int target) { int mid; //if(first > last) //return -1; // -1의 반환은 탐색의 실패를 의미 if(ar[first]>target || ar[last]
우선순위 큐 : 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐의 구현 방법 1. 배열 기반 2. 연결 리스트 기반 3. 힙(heap) 이용 힙이라는 자료구조를 이용해서 구현하는 것이 일반적 힙 : 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉, 루트 노드에 저장된 값이 가장 커야 한다.(값은 말 그대로 값이 될수도 있고 우선순위가 될 수도 있다.) heap : 무엇인가를 차곡차곡 쌓아올린 더미 최대 힙(max healp) : 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리 최소 힙(min heap) : 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리 힙은 우선순위 큐의 구현에 어울리는, 완전 이..
트리(Tree)
트리는 계층적 관계를 표현하는 자료구조이다. 노드(node) : 트리의 구성요소에 해당하는 요소(A, B, C, D) 간선(edge) : 노드와 노드를 연결하는 연결선 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드(terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드(E, F) 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 서브 트리 : 큰 트리에 속하는 작은 트리 이진 트리(Binary Tree) 1. 루트 노드를 중심으로 두 개의 서브트리로 나뉘어야 한다. 2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다. (노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주..
큐 : 선입선출 배열에서 할 때 dequeue를 하면 f를 뒤로 이동시킨다. => 배열 크기 10인데 앞에꺼가 비어있으면 넣을 수가 없어 => 원형 큐 => F, R의 위치만으로는 꽉 찬 경우와 빈 경우를 구분X => 배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉 찬 것으로 간주 ex) 원형 큐 CircularQueue.h #ifndef __C_QUEUE_H__ #define __C_QUEUE_H__ #define TRUE1 #define FALSE0 #define QUE_LEN100 typedef int Data; typedef struct _cQueue { int front; int rear; Data queArr[QUE_LEN]; } CQueue; typedef CQueue Que..
스택 : 먼저 들어간 것이 나중에 나온다. 후입선출. LIFO(Last-In, First-Out) ex) 배열기반 스택 ArrayBaseStack.h #ifndef __AB_STACK_H__ #define __AB_STACK_H__ #define TRUE1 #define FALSE0 #define STACK_LEN100 typedef int Data; typedef struct _arrayStack { Data stackArr[STACK_LEN]; int topIndex; } ArrayStack; typedef ArrayStack Stack; void StackInit(Stack * pstack); int SIsEmpty(Stack * pstack); void SPush(Stack * pstack, Da..
앞에 우리가 구현한 연결 리스트의 마지막 노드는 NULL을 가리켰다. 이 마지막 노드가 첫 번째 노드를 가리키게 하면 '원형 연결 리스트'가 된다. 머리에 추가할려면 머리 하나만 필요. 꼬리에 추가할려면 꼬리도 필요. 장점이 반감 원형 연결 리스트의 장점 : 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다. 변형된 원형 연결 리스트 하나의 포인터 변수가 머리가 아닌 꼬리를 가리키게 하자. => 꼬리를 가리키는 포인터 변수 : tail 머리를 가리키는 포인터 변수 : tail->next 어렵지 않게 머리와 꼬리에 노드 추가 가능 ex) CLinkedList.h #ifndef __C_LINKED_LIST_H__ #define __C_LINKED_LIST_H__ #define TR..