개발자 끄적끄적

- 비선형 구조 가운데 하나인 그래프 - 정점(node)와 간선(edge)으로 이루어진다 - 컴퓨터, 수학, 공학 등의 많은 분야(최단거리 분석, 연구계획/공정분석, 회로 분석 등)에서 객체 사이의 관계를 표현하는 도구로서 사용 - 기판, 컴퓨터 설계 : 수 만개 구멍을 레이저드릴로 천공 - 그래프(Graph)는 정점(vertex)와 간선(edge)의 집합으로 정의 - 정점의 집합 V는 정점들의 유한집합이고 간선의 집합 E는 정점들을 연결하는 선의 집합 - 그래프의 표기 : G=(V,E) - 하나의 간선 E는 (Vi, Vi)로 두 개의 정점으로 표현된다 - 그래프는 간선의 양끝 정점사이의 순서를 고려에 따라 - 방향 그래프(directed graph) - 무방뱡 그래프(undirected graph) -..

- 트리구조는 일종의 색인구조로서 데이터의 검색(인덱스:Index)이 주요 목적 *색인구조 : 문서에서 키워드를 찾아보기 쉽도록 정렬/나열한 목록 일반적으로 책 뒷편에 색인, 인덱스, 찾아보기와 같은 이름으로 정돈된 목록을 의미 - 신속한 데이터의 검색은 시스템의 성능에 결정적 영향 - 검색 속도는 원하는 데이터를 찾을 때까지의 경로 상 노드 숫자에 비례 - 노드의 크기에 따라 검색 속도가 변화 - ex) 실제 상황에서의 AVL 트리의 높이는 아래와 같다(n은 입력된 데이터의 개수) O(log2n) = log2(n+1)+0.25 - 따라서 데이터의 개수가 약 1000개라면 트리의 높이는 10이되고, 데이터를 검색할 때 최악의 경우라도 10개의 노드를 거치면 찾을 수 있음을 의미한다 - 실제로 운영되는 트..

- 균형 이진검색 트리는 말단 노드가 모두 같은 레벨에 존재하는 형태 - 이진 트리에 대한 연산이 가장 효율적으로 이루어진다 - 불균형이 가장 심화된 상태(사향트리(skewed tree)의 경우 - 사향트리의 경우는 데이터값이 크기 순서대로 오름차순 또는 내림차순으로 입력될 때 나타난다 - 검색 트리가 불균형 상태 : 검색 성능의 저하 - 이러한 문제점을 해결한 구조로서 AVL 트리가 있다 이 이진 검색트리는 모든 노드에서 왼쪽과 오른쪽 부트리의 깊이의 차이가 1이하인 상태를 유지하도록 데이터의 삽입/삭제 시에 균형을 이루도록 노드를 재배치하는 구조를 가지고있다 - AVL트리는 이진 검색트리로서 트리의 균형을 유지한다 - 균형트리의 조건 - 트리의 균형을 유지하기 용이 - 트리의 깊이가 O(log2n)을..

- 이진 트리는 노드에 저장된 데이터의 크기와 무관히 데이터가 노드에 위치되었다 - 그러나 이진트리의 응용에서는 이진트리를 사용하여 데이터를 트리 내에 저장하고 검색, 삭제하는 연산이 많이 사용 - 이진 검색 트리 - 데이터의 크기에 따라 트리 내부에 저장되는 위치가 결정되고 검색이나 삭제 시에도 데이터의 크기에 따라서 검색의 경로가 결정되는 구조 - 이진 검색트리에서 데이터를 크기에 따라 저장될 위치를 결정하기 위한 조건이 먼저 지정되어야 한다 - 조건 1. 루트 노드의 데이터값은 왼쪽 부트리의 모든 노드보다 크거나 같다 2. 로트 노드의 데이터값은 오른쪽 부트리의 모든 노드의 데이터 값보다 작다 3. 모든 부트리에서 위의 두 조건을 만족한다 struct list{ strunct list*left; i..

- 이진트리를 순회하는 방법은 이진트리를 크게 루트 노드, 왼쪽 부트리, 오른쪽 부트리의 세 부분으로 나누고 이 세 부분을 방문하는 순서는 3의 조합의 개수인 모두 6가지가 된다 1. 루트노드 -> 왼쪽 부트리 -> 오른쪽 부트리(D->L->R) //전순위 2. 루트노드 -> 오른쪽 부트리 -> 왼쪽 부트리(D->R->L) //전순위 3. 왼쪽 부트리 -> 루트노드 -> 오른쪽 부트리(L->D->R) //중순위 4. 오른쪽 부트리 -> 루트노드 -> 왼쪽 부트리(R->D->L) //중순위 5. 왼쪽 부트리 -> 오른쪽 부트리 -> 루트노드(L->R->D) //후순위 6. 오른쪽 부트리 -> 왼쪽 부트리 -> 루트노드(R->L->D) //후순위 이 중에서 2,4,6번은 1,3,5번과 중복되므로 제외 - 1..

- 연결리스트에 의한 방법 - 배열에 의한 트리의 표현은 상당히 제한적인 기능을 갖는다 - 특히 트리 구조는 데이터 양의 가변적인 경우에 주로 많이 사용하므로 데이터의 양을 미리 예측하기 힘들다 - 트리가 포화이진 또는 완전 이진의 구조가 아니라 중간에 노드가 비어있는 경우가 발생할 때 메모리의 낭비가 일어난다 - 따라사 실제의 응용분야에서는 포인터를 사용한 연결리스트 방법이 주로 사용되며, 연결리스트 역시 메모리 기반이 아닌 파일기반으로 구현된다 - 이진트리는 하나의 데이터 필드에 두 개의 자식노드를 연결하는 연결필드가 필요하다 : 이중 연결리스트 - 구조체는 사용자가 혼합하기에 따라서 무한대에 가까운 조합(정수형, 실수형, 문자형 등)을 갖는다 즉, 사용자가 구조체를 직접 만들어야한다 ex) stru..

- 이진트리는 많은 응용프로그램에서 사용되며 트리의 대표적인 구조로서 트리의 기본을 이룬다 - 이진트리의 특성 - 모든 노드의 자식 노드의 개수가 2개 이하 - 엄격한 이진트리(Strictly binary tree) - 말단 노드를 제외한 모든 노드의 차수가 2인 트리 - Knuth binary tree - 노드의 차수가 0, 1, 2인 tree로 일반적인 binary tree - 포화 이진트리(Full binary tree) - 깊이가 k인 이진트리에서 노드의 수가 (2^k)-1(k>0)로서 모든 말단 노드는 k번째 레벨이 존재 - 완전 이진트리(Complete binary tree) - 깊이가 k인 이진 트리에서 k-1 레벨까지는 포화 이진트리(Full binary tree)이고, 각 노드들이 깊이 ..

- 만일 노드 A의 자식 노드가 B와 C인 경우 A(B, C)로 표현한다면 -> A(B(D(G, H), E(I, J)), C(F(K, L, M, N))) - 트리 내의 모든 Node를 한 번씩 정해진 순서로 방문하는 것을 말한다 - 트리의 순회에는 모두 5가지 방식이 있다 1. Level Order - 위에서 아래로, 왼쪽에서 오른쪽으로 2. Family Order - 부모노드에서 시작 자식노드를 왼쪽부터 모두 방문하고 가장 오른쪽 노드에 대해 동일한 과정을 반복 3. 전위순회(Preorder) - 부모노드가 우선 방문하고, 왼쪽 부 트리가 오른쪽 부 트리에 우선하는 방식 4. 중위순회(Inorder) - 왼쪽 부 트리를 모두 방문한 뒤 부모노드를 방문하고 오른쪽 부 트리를 방문하는 방식(Binary T..

- 대량의 데이터를 관리하는 역할 - 비선형 구조 -> 모든 데이터가 하나의 선상에 존재하지 않는 구조, 하나의 노드에 연결된 노드들이 여러개이면서 대칭구조를 이룬다 *선형 구조-> 모든 데이터가 하나의 선상에 존재하는 구조 - 트리는 정점(node)과 간선(edge)으로 이루어진 그래프의 변형 *트리(Tree)와 그래프(Graph)의 차이 1) 트리 : 그래프의 부분집합, 트리는 오직 하나의 부모노드(Parent Node)를 가질 수 있다 2) 그래프 : 하나 이상의 부모노드(Parent Node)를 가질 수 있다 - 비 선형구조(Non-linear structure)란 하나의 노드에 연결된 노드가 복수 개이면서 계층구조 - 트리에서는 루트노드(가장 상위에 위치한 노드)를 제외한 모든 노드가 하나의 상..