observe_db

그래프의 추상 타입(The Graph Abstract Data Type)시초는 오일러의 쾨인스버그 다리 문제래프의 추상 타입(The Graph Abstract Data Type) 시초는 오일러의 쾨인스버그 다리 문제임의의 지역에서 출발하여 모든 다리를 단 한번씩만 지나 처음 출발한 지역으로 되돌아 올 수 있는가?- 각 정점(vertex)의 차수가 짝수이면 가능.차수(degree): 정점에 연결된 간선 수오일러 행로(Eulerian walk) 정의(definition)그래프 G: 2개의 집합 V와 E로 구성- V: 공집합이 아닌 정점(vertex)의 유한집합- E: 간선(Edges), E ⊆{{x, y} | (x, y) ∈ V^2 ∧ x!=y}- 표기: G=(V,E) 무방향 그래프(undirected gr..

if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. 우선순위 큐(Priority Queue)- 우선 순위가 가장 높은/낮은 원소를 먼저 삭제- 임의의 우선순위를 가진 원소 삽입 가능- 추상 데이터 타입 MaxPriorityQueue 무순서(unordered): 선형 리스트로 구현(가장 간단)- IsEmpty() : O(1) // linked list가 null인지 검사- push(): O(1) //임의의 위치에 노드 삽입- top(): Θ(n) //list 전체 검사..

트리: 정보의 항목들이 가지(branch)로 연결되는 데이터 구조: 하나 이상의 노드로 이루어진 유한 집합.루트(root) 노드 1개나머지는 n개의 분리 집합 T1,T2,...Tn으로 분할.(Ti는 서브트리) - 노드: 데이터(정보) 아이템+ 다른 노드로 뻗은 가지(branch)- 차수(degree): 노드의 서브트리 수(= link 수 = branch 수)- 단말(leaf) 노드: 차수 = 0 => 자식(child) 비존재- 비단말 노드: 차수 !=0  => 자식(child) 존재- 자식: 노드 X의 서브트리의 루트(부모)- 형제(sibling): 부모가 같은 자식들- 트리의 차수 = max{노드의 차수}- 조상: 루트까지의 경로상에 있는 모든 노드- 노드 레벨: 루트=레벨1, 자식레벨 = 부모레벨+1..

단순 연결 리스트(Singly Linked Lists and Chains)순차리스트의 특성- 데이터 객체의 연속된 원소들이 일정 거리만큼 떨어져 저장-(배열) a_i,j가 L_ij에 저장된다면, a_i,j+1은 L_ij+1에 저장-(스택) 제일 위의 원소가 -(큐) 큐의 i번째 요소가 L_i에 위치하면 i+1 ->(L_i+1)%n 임의의 원소에 대한 삽입(Insertion)과 삭제(Deletion)에 많은 비용- 중간에 하나의 삽입/삭제에 대해 다른 원소들의 이동이 필요하기 때문. 연결(linked) 표현- 순차 표현에서 제기된 데이터 이동 문제점 해결- 각 원소들이 메모리 내의 어떤 곳에나 위치 가능- 원소에 정확한 순서로 접근하기 위한 정보가 필요(주소 정보) 노드(node)- 0개 이상의 데이터 필..