Computers/Data Structure 13

Addition. 2-3-4 Trees

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

Addition. 2-3 Trees

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. 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 * 왼쪽 서브 ..

Chapter 11. Multiway Search Trees

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. 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 트리는 노드 크기가 몇 바이트 정도로..

Chapter 10. Efficient Binary Search Trees (효율적 이원탐색 트리)

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

Chapter 9. Priority Queue (우선순위 큐)

(참고자료 기반) 우선순위 큐 : 우선순위를 가진 항목들을 저장하는 큐 - FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나감 - 가장 일반적인 큐 : 스택이나 FIFO 큐를 우선 순위 큐로 구현응용 분야 - 시물레이션 시스템 / 네트워크 트래픽 제어 / 운영체제에서의 작업 스케줄링 - ADT : create() / init() / is_empty() / is_full() / insert() / delete() / find() - 최소 우선 순위 큐 - 최대 우선 순위 큐우선순위 큐 구현 방법 - 배열을 이용한 우선순위 큐 - 연결 리스트를 이용한 우선순위 큐 - Heap을 이용한 우선순위 큐 Single-and double- ended priority queuesLeftist TreesBinom..

Chapter 8. Hashing

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

Chapter 6. Graphs

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요. 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 ㄴ. 같은 간..

Chapter 5. Trees

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.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)..

Chapter 4. Linked Lists

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..