본문 바로가기

자료구조14

[자료구조] 그래프 그래프 “관계” 를 그래프로 추상화 하여 다룰 수 있음 (자료구조의 정의) 전기회로의 분석, 최단 거리 탐색, 프로젝트 계획, 스케줄링, 운송, 컴퓨터 네트워크 시뮬레이션 등등 그래프의 정의 그래프 G는 하나 이상의 정점(혹은 노드) 을 포함하는 집합 V 와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E의 순서 쌍으로 정의함 그래프 G = (V ,E) 그래프의 정의 - 정점과 간선 V = {a,b,c,d} (정점의 집합) E = {1,2,3,4,5,6,7} (간선의 집합) G = (V,E) = ({a,b,c,d} , {1,2,3,4,5,6,7}) (정점과 간선의 합) 그래프 용어의 정의 간선은 두 정점을 연결하는 선 그래프는 연결(간선)에 방향성이 없는 무방향 그래프와 방향성을 갖는 방향 그래프가 .. 2023. 12. 2.
[자료구조] 멀티웨이 탐색트리(2) 2-3 트리(2-3tree) 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리 2-노드 (2개의 자식 노드; 차수가 2)와 3-노드만(3개의 자식 노드; 차수가 3)으로 구성되는 특수한 형태의 B트리 2-노드 혹은 3-노드라는 제약이 내부 노드에만 해당함 → 모든 잎 노드는 같은 레벨에 있어야 한다는 제약만 존재 2-3트리(2-3tree) 의 조건 각 내부 노드는 2-노드이거나 3-노드이다. 2- 노드는 1개의 키 값을 3-노드는 2개의 키 값을 갖는다. lchild, mchild를 각각 2-노드 의 왼쪽 자식 및 중간 자식 이라 하고, lkey가 이 2-노드의 키 값이라 하자. 그러면 루트가 lchild인 모든 2-3 서브 트리 키 값은 lkey 보다 작고, 루트가 mchild인 모든 2-3 서브 트리.. 2023. 12. 2.
[자료구조] 멀티웨이 탐색 트리(1) m원 탐색 트리 m원 탐색 트리의 정의 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 → 같은 수의 노드를 갖는 이진 트리보다 낮은 높이의 m원 트리 이진 탐색 트리의 확장된 형태임 탐색 트리의 제한을 따르면서, 2개 이상 ~ m 개 이하의 자식 노드를 가질 수 있음 노드 구조는 다음과 같다. 여기서 P0 ~ Pn 은 서브 트리에 대한 포인터 이고 K0 ~ Kn-1 은 키값이다. 또한 n ≤ m - 1 이 성립한다. i = 0, …, n - 2 인 i 에 대해 Ki < Ki+1 을 만족한다. i = 0, …, n - 1 인 i 에 대해 Pi 가 가리키는 서브 트리의 모든 키 값은 Ki 의 키 값 보다 작다. Pn 이 가리키는 서브 트리의 모든 키 값은 Kn-1 의 키 값 보다 크다. i = .. 2023. 12. 2.
[자료구조] BS,Splay,AVL,BB 이진 탐색 트리(BS트리 : binary search tree) 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진 트리 특정 데이터의 검색과 노드의 삽입 삭제 처리 에 효과적인 이진트리 트리를 구성할 때, 데이터의 탐색을 고려하여 구성하므로 탐색에 최적화된 이진트리 키 : 탐색 삽입 삭제 연산에서 비교의 대상이 되는 값, 이진트리 노드의 데이터를 대표하는 값, 혹은 노드를 특정할 수 있는 값 root 기준 왼쪽 서브트리에 모든 노드의 키 값은 루트 보다 작다 root 기준 오른쪽 서브트리에 모든 노드의 키 값은 루트 보다 크다 → 중위순회를 통해 같은 순서 데이터(A-B-C-D) 를 만들어 낼 수 있다. BS트리순회 BS트리를 위한 노드 정의 typedef struct BSTnode{ struct.. 2023. 12. 2.
[자료구조] 선택트리 , 숲 , 이진트리 개수 선택트리 합병 정렬 차례로 정렬된 k개의 데이터 목록을 순서를 유지하는 하나의 데이터 리스트로 만드는 과정 일반적으로 데이터 목록이 k개인 경우, k-1 번 비교를 통해 데이터 목록에서 가장 작은 값이나 가장 큰 값을 결정 할 수 있음 선택 트리를 이용해서 비교 횟수를 줄일 수 있음 승자트리 각 노드가 두 자식 노드의 작은 값을 갖는 완전 이진트리 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함 결과적으로 루트의 값이 트리에서 가장 작은 값 → 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교부터는 횟수가 감소 됨 → 재구성 과정에서 빈 리스트가 생기면 큰 값을 넣어줌 패자트리 각 노드가 두 자식 노드 중에서 더 작은 값을 .. 2023. 11. 29.
[자료구조] 힙 우선순위 큐 대기 리스트에서 우선순위가 높은 사람이 먼저 서비스를 받는 구조 우선순위 큐의 작동방식 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값) 이 삭제 된다. 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다. 힙 추상 자료형 힙의 정의 피라미드 모양으로 쌓아올린 더미 무엇인가 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조 부모- 자식 노드 사이에서 (부분적) 정렬된 완전 이진트리로 부모 노드는 자식 노드보다 우선 순위가 높음 힙 객체의 정의 부분적으로 정렬된 완전 이진 트리로 부모노드는 자식노드보다 우선순위가 높다 연산 연산 내용 insert(element) 힙에 데이터 삽입 delete() 힙(루트) 에서 데이터 삭제 peek() 힙(루트) 에서 .. 2023. 11. 29.
[자료구조] 스레드 트리 스레드트리 이진트리의 노드 순회 : 전위, 중위, 후위 순회 이진트리의 노드를 순환 함수를 사용하지 않고, 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리 해야 하는 번거로움이 발생. → 스레드라는 포인터를 추가하여 트리 순회를 편리하게 한 것 스레드 순회 방법에 따라 방문 순서를 유지하는 포인터 스레드 트리 구현 스레드의 구현 방법 : 포인트 필드의 추가 포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가 하는 것 → 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의 함 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킨다. 왼쪽 스레드 : 그 노드의 선행 노드를 가리킨다. 스택을 운영하지 .. 2023. 11. 29.
[자료구조] 트리 트리의 개념 트리의 정의 검색의 편리함 논리적 계층 계급적 특성 트리의 표현방법 트리의 구성 노드 : 트리의 항목/트리 에 저장되는 데이터의 묶음 부모노드 - 자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드들로서 상위계층의 부모노드와 하위계층의 자식노드를 의미함 루트노드 트리의 최상위 노드 (부모가 없는 노드) 서브트리 부모노드를 삭제하면 생기는 트리들 잎 노드 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드 진입 / 진출 차수 루트노드 : 진입차수 = 0 루트를 제외한 모든 노드의 진입차수 = 1 잎노드 : 진출차수 = 0 내부 노드와 형제 내부 노드 : 루트, 잎 노드가 아닌 나머지 노드 형제 : 같은 부모를 갖는 노드들 트리의 레벨 노드의 레벨 : 루트로부터 그 노드까지.. 2023. 11. 29.
[자료구조] 연결 리스트의 응용 연결 리스트의 변형 단순 연결 리스트 단순 연결 리스트의 문제점 하나의 링크 만 있고, 각각의 노드의 링크는 후행 노드만을 가리키는 구조. → 특정 노드의 후행 노드는 쉽게 접근 가능 하지만 , 선행 노드를 찾으려면 헤드 노드 부터 다시 검색 해야 함. (비 효율적) 이중 연결 리스트 선행과 후행을 가리키는 두개의 링크를 가진다. → 특정 노드에서 선행 노드와 후행 노드에 직접적으로(간단한 코드를 통해) 접근이 가능 원형 연결 리스트 연결 리스트를 살펴보면, 가장 마지막 노드의 링크 필드는 언제나 NULL → 리스트의 마지막 원소 뒤에는 아무 원소도 없기 때문에 연결 리스트의 마지막 노드의 링크 필드는 언제나 null → 마지막 노드의 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해 원형 연.. 2023. 11. 28.
728x90

티스토리툴바