emzei

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. Add2. 2-3-4 Trees - 추가로 4-노드 정의 - 자식 노드로 가는 링크가 4개이고, 키가 3개인 노드 - 2-3-4 트리를 쓰는 이유??? ⇒ 단일 패스 삽입 ⇒ 레드-블랙 트리와의 연관성 ( 조금 더 간단, 공간이 많아서 쉬움 (내가 필기 한건데 왜인지 아직 이해 못함)) * 2-3 트리는 리프노드가 꽉 차면 중간 자식을 부모노드로 올리고, 만약 부모노드가 꽉 차면 다시 부모노드의 중간 자식이 그 위로 올려짐. * 2-3-4 트리는 이러한 사태를 배제하기위해, 루트로 부터 삽입위치를 찾아서 내려가는 도중에 4-노드를 만나면 무조건 제거하면서 내려감 * 스택이 필요없음 ( 위에서부터 check) * 하나의 삽입 ..

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. Add1. 2-3 Trees - 차수가 2 또는 3인 노드를 가지는 트리 (자식이 2 or 3) > AVL은 균형 트리를 지향 > 2-3 트리는 완전 균형 트리를 지향 > AVL 트리에 비해 상대적으로 단순한 논리 - 2-노드 > 자식 노드가 2개이고 키가 1개인 노드 > 이진 탐색트리처럼 하나의 데이터 k1와 두 개의 자식노드를 가짐 - 3-노드 > 자식노드가 3개이고 키가 2개인 노드 > 2개의 데이터 k1, k2와 3개의 자식 노드를 가짐 > 왼쪽 자식(Left Child), 중간 자식(Middle Child), 오른쪽 자식(Right Child) > 키 크기는 12 < 50 < 65 < 90 < 100 * 왼쪽 서브 ..

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. M-way Search Trees - 다원 탐색 트리 - 메모리 접근 시간이 산술/논리 연산을 수행하는 것보다 훨씬 더 많은 시간을 소비함. ⇒ 프로세서 속도와 메모리 접근 시간 간의 큰 차이 때문에 메인메모리에서 캐시로 캐시 라인 크기 단위로 옮겨지고, 디스크에서 메인메모리로는 블록 단위로 옮겨짐. - 참고 url : http://www.intelligence.tuc.gr/~petrakis/courses/datastructures/btrees.pdf http://webdocs.cs.ualberta.ca/~holte/T26/m-way-trees.html - AVL 트리, Red-Black 트리는 노드 크기가 몇 바이트 정도로..

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. Optimal Binary Search Trees (최적 이원 탐색 트리) AVL TreesAVL - Adelson-Velskii와 Landis가 서브트리들의 높이가 균형을 이루는 이진트리구조를 제안 - 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리 - 평균, 최선, 최악 시간 복잡도 : ⇒ 동적 검색, 삽입/삭제 : O(log(n)) 시간 안에 가능. - 균형 인수 (balance factor) : (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이) ...음수 가능 → 양수 : 왼 > 오 , 음수 : 왼 < 오 : 노드 하나 짜리 트리는 높이 0 : 빈 트리의 높이 -1 : 모든 노드의 균형 ..

Introduction개념 - 자료를 입력할 때부터 검색시간을 고려하여 작성하는 자료구조 - 빠른 검색을 위한 자료관리 기법해시 함수 (hash funciton) - 탐색 키(key) 를 입력받아 해시 주소(hash addr)를 생성 - 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 됨 (예) 영어사전에서는 단어가 탐색 키가 되고 이 단어를 해싱 함수를 이용하여 적절한 정수 i로 반환한 다음, 배열 요소 ht[i]에 단어의 정의를 저장해시 테이블 구조 - 해시테이블 ht는 M개의 버킷(bucket)으로 이루어져있는 테이블 ht[0].... ht[M-1] 의 원소를 갖는다. - 하나의 버킷은 s개의 슬롯(slot)을 가짐 - 충돌(collision) : 서로 다른 두개의 탐색키..

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. Graph Abstract Data Type ( 그래프 추상 데이터 타입 ) (1) 개요 - 차수(degree) : 정점에 연결된 간선의 수 - 오일러 행로(walk) : 각 정점의 차수가 짝수인 경우에 한해 각 간선을 한번씩 거쳐 출발한 정점으로 되돌아 올 수 있음 (2) 정의 ✦ 그래프 G=(V,E) V: 정점 (set of vertices), 공집합이 아닌 V의 유한집합 E : 간선 (set of edges), 정점을 연결하는 선, 선 V*V의 부분집합 (+) 그래프의 제약 사항 ㄱ. 임의의 정점 v에서 자기 자신으로 이어지는 간선을 가질 수 없음 (u,u) , , self-edge, self-loop X ㄴ. 같은 간..

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.Introduction Terminology (용어) - 트리 구조 : 계층구조로 데이터가 구성된 것 ** 트리 tree : finite set of one or more nodes such that (1) There is a specially designated node called the root (2) The remaining nodes are partitioned into n>=0 disjoint sets T1,... Tn, where each of these sets is a tree. T1,...,Tn are called the subtrees of the root. (하나 이상의 노드로 이루어진 유한 집합, (1)..

Single Linked List and Chains - single linked list = chain Representing chains in c++ Template class chain Circular List - 단순 리스트보다 좋음 - 특정 노드 앞에 새 노드 삽입 시, 탐색하기가 더 나을 수 있음 Available Space Lists (가용 공간 리스트) - 자유 노드 리스트를 두고, 새로운 노드가 필요할 때 자유 노드 체인을 검사. (삭제한다해도 삭제가 아니라 자유 노드 리스트로 넘기는 메커니즘) Linked Stacks and Queues Polynomials Equivalence classes - reflexive, symmetric, transitive → 동치관계 Sparse Mat..