Develop Develop

이진 검색트리(BST) 일반 트리와 달리 BST의 재귀는 자료가 어떻게 접근되는가가 아니라 자료가 어떻게 정렬되는가에서 더 중요 BST의 정렬에서 핵심은 자료를 반으로 나눔으로써 검색 공간을 줄인다. 검색하고자 하는 자료들이 대기열에 들어가 있다고 하자. 대기열에서 첫번째 항목을 뽑아 그것을 트리의 루트로 한다. 대기열에서 다음 항목을 뽑아서 루트와 비교하고 그것보다 작으면 왼쪽자식으로 크면 오른쪽 자식으로 만든다. 나머지 항목들도 동일한 과정반복 현재 노드보다 작으면 왼쪽, 크면 오른쪽 따라가다가 자식이 없는 노드를 만나면 그 노드랑 비교 왼쪽 오른쪽 자식에 추가 자료검색또한 위의 과정과 동일하게 하면된다. 3을 찾는과정이라면 루트가 만약 4라면 3과 4를 비교해서 왼쪽으로 가고 등등... BST검색 ..

트리는 확장성이 좋은 자료구조가 필요하다. 연결된 목록이 필요하지..(list) 트리의 각 노드는 하나의 연결 목록이 되고 목록의 각 노드는 트리의 다른 노드들을 가리키도록 하자. 트리를 탐색할때는 두종류의 반복자가 필요함. 1. 트리의 현재 노드 2. 현재 노드의 현재 자식노드 트리 반복자는 이전에 나왔던 연결 목록 반복자와는 다르다 연결 목록 반복자는 연결 목록에서 뽑아내는 식으로 생성 트리 반복자의 경우 가리키고자 하는 트리 노드를 생성자에 전달 이진트리 일반적 트리에는 없는 몇가지 특성 1. 포화성(새로운 수준을 하나 더 추가하지 않는 한 더 이상 노드들을 추가할 수 없음) 2. 조밀성(최하위 수준바로 전까지는 꽉 차 있으며 최하위 수준의 모든 말단 노드들이 왼쪽부터 채워져 있는 것) * AVL ..

해싱은 검색키에 대한 산술 연산을 이용한 검색 방식임 검색 키 값을 입력값으로 계산을 실시하면 검색하려는 자료의 위치를 알 수 있다는 것이 기본 개념 검색키 -> 해싱함수 -> 검색 자료의 주소를 -> 해시테이블에서 찾음 그런데 계산된 주소에 다른 자료가 저장되어 있다면 충돌이 발생한다. 해싱함수로 사용될 수 있는 방법 1. 나머지 함수 가장 일반적임 검색 키 값 k를 해시 테이블의 크기 m으로 나눈 나머지를 해시 주소로 사용 2. 접기함수 검색 키의 크기가 해시 테이블의 크기보다 큰 정수일 경우 사용 검색 키 값 k가 데이블의 크기 m보다 큰 경우 k를 m의 자릿수와 같은 크기로 분할한 후 분할된 부분들을 이용하여 해시 테이블 주소 만듬 예) 검색 키값 : 1234512345(10자리) 해시 테이블 크..

덱(디큐라고도함)은 두개의 끝을 가지는 큐라는 뜻 양쪽 끝에서 자료의 삽입과 반환이 모두 가능한 선형 자료구조 기존 큐에서는 새로운 자료의 추가는 큐의 제일 뒤 리어에서만 가능하고 자료의 반환은 제일 앞 프런트에서만 가능했다면 덱에서는 끝이 두 개이므로 각각의 끝에서 자료의 추가와 반환이 모두 가능하다. 덱의 이러한 특성 때문에 큐와 스택의 기능을 합친 자료구조로도 설명이 된다. 연산 덱 스택 큐 앞 프런트 추가 inserFront 없음 없음 반환 deleteFront 없음 dequeue 뒤 리어 추가 insertRear push enqueue 반환 deleteRear pop 없음 * a-steal 스케줄링 알고리즘이 덱의 기능을 요구한다는데.. 여기서는 헤더노드가 아닌 헤더포인터로 구현하겠음 (둘 차이..

리스트는 배열 리스트, 포인터 리스트로 구성할 수 있다. 배열리스트 소스 #include #include #include #include using namespace std; class ArrayListNode { public: int data; }; class ArrayList { public: int m_MaxElementCount; //최대원소 개수 int m_CurrentElementCount; //현재 원소 개수 ArrayListNode* pElement; //원소 저장을 위한 배열 포인터 public: ArrayList(){} ~ArrayList(){} //리스트 생성함수 void CreateArrayList(int maxElementCount) { if(maxElementCount>0) { ..

1. 연산의 빈도를 찾거나..(일일이 n에 따른 더하기 대입(n이 직접영향받는것이 아니라 n에 영향을 받아 계산되는것 포함)..등등 계산이 몇번되는가..) 예) test(n) { i=0; 최초 1번 sum=0; 최초 2번 for(;i logn >n >nlogn >n^2 >n^3 >2^n >n! 이런 순서다.. 해당내용은 윤성우의 열혈 자료구조와 열혈강의 자료구조를 참고했습니다.

이진 탐색트리가 자동으로 균형을 잡을 수 있도록 개선된것이 AVL 트리 균형인수 = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이 균형인수의 절댓값이 2이상인 경우에 균형을 잡기위해 트리의 재조정을 진행한다. LL회전 자식 노드 두개가 왼쪽으로 연이어 연결되어 부모의 균형인수가 2가 되는 것 3 2 1 이런경우를 말하고..LL회전을 거치면 2 1 3 이렇게 된다. 2를 중심으로 오른쪽으로 3이 돌면됨.. RR은 그와 반대로.. 3 2 1 RR회전을 거치면 2 3 1 이런식으로 된다. LR과 RL도 있는데 우선 LR의 경우 1 2 3 이런식을 말하고.. 우선 LR상태에서 한번의 회전으로 균형이 잡히는 LL이나 RR로 바꾼다 LR상태에서 RR회전을 하면 LL상태가 된다. 2, 3을 먼저 떼어서 RR회전을 ..

#include #include #define HEAP_LEN 100 using namespace std; typedef char HData; typedef int Priority; typedef int PriorityComp(HData d1, HData d2); typedef struct _help{ int numofData; HData heapArr[HEAP_LEN]; PriorityComp *comp; }Heap; void HeapInit(Heap *ph, PriorityComp pc){ ph->numofData=0; ph->comp=pc; } int HIsEmpty(Heap *ph){ if(ph->numofData==0) return 1; else return 0; } int GetParentID..