dongdorodongdong
자료구조 본문
정의
- 자료를 기억장치 내에 저장하는 방법
분류
- 선형 구조
- 순차리스트 (스택, 큐, 데크, 배열)
- 연결리스트 - 비선형 구조
- 트리
- 그래프
순차 리스트(Sequential List)
- 연속적인 저장
- 구조가 간단하다.
- 기억장소 이용 효율이 높다.
- 순서가 있기 때문에 원하는 데이터를 삽입, 삭제가 어렵다.
- 검색이 빠르다.
연결 리스트(Linked List)
- 비연속적인 저장(자료들을 임의의 기억공간에 저장)
- 노드의 포인터 부분을 이용
- 기억장소 이용 효율이 낮다. (연결을 위한 포인터 부분이 필요하기 때문)
- 순서가 없기 때문에 원하는 데이터를 삽입, 삭제가 가능하다.
- 검색이 느리다.
스택(Stack)
삽입, 삭제가 한 쪽에서 이루어지는 데이터 구조
Top : 가장 최근에 삽입된 자료, 가장 먼저 삭제될 자료를 가리키는 Stack pointer
서브루틴 호출, 인터럽트 처리, 수식 계산 및 수식 표기법에 응용
큐(Queue)
- 한 쪽에서는 삽입, 다른 한 쪽에서는 삭제
- CPU 스케줄링에서 FIFO 방식과 같다.
- F,Front 포인터, R,Rear 포인터가 있음
데크(Deque)
- 삽입과 삭제가 양쪽 모두에서 가능
- 스택과 큐의 장점으로 구성
- Double Ended Queue
- 입력 제한 데크(Scroll)
- 입력은 한쪽에서만, 출력은 양쪽 - 출력 제한 데크(Shelf)
- 출력은 한쪽에서만, 입력은 양쪽
트리(Tree)
Root Node : 최상위 노드
노드의 차수(degree) : 어떤 노드의 서브트리 수(가지 수)
트리의 차수(degree) : 노드의 차수 중 최대값
단말노드(Leaf / 터미널노드) : 차수가 0인 노드
형제노드 : 같은 부모 노드를 가지는 노드
레벨(Level) : 노드의 깊이
사이클이 없다.
이진트리
- 차수(drgree)가 2 이하로 구성된 트리
- 운행법
- Preorder(전위) : Root -> Left -> Right
- Inorder(중위) : Left -> Root -> Right
- Postorder(후위) : Left -> Right -> Root
B - 트리
- 인덱스를 구성하는 방법
- 한 노드 안에 있는 키 값은 오름차순
- 모든 단말노드는 같은 레벨
- Root Node의 차수(degree)는 2 이상
- 노드의 탐색, 추가, 삭제는 Root Node부터 시작한다.
그래프(Graph)
- 노드와 간선으로 구성된점은 트리와 같지만 그래프는 사이클이 있다.
- 인접행렬로 표시 가능
- n개의 노드로 구성된 무방향 그래프의 최대 간 선수는 n(n-1)/2
* DFS (Depth First Search)
- 정의
- 하나의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 넓게 탐색하기 전에 깊게 탐색하는 것 - 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태
- 트리 순회 모두 DFS - 과정
- 시작 노드에서 인접한 노드들을 차례로 순회함 (방문한 노드는 방문했다고 표시)
- 시작 노드의 인접 노드(b)를 방문했다면 a와 인접한 다른 노드를 방문하기 전에 b의 이웃 노드들(분기:branch)은 전부 방문해야 한다.
- 이용
- 순환 호출에 이용
- 명시적인 스택 사용
'Database' 카테고리의 다른 글
관계 대수 / 관계 해석 (0) | 2019.03.25 |
---|---|
Hashing (0) | 2019.03.25 |
SQL(DDL/DML/DCL) (0) | 2019.03.25 |
데이터베이스 설계 (0) | 2019.03.25 |
시스템 카탈로그(데이터 사전) (0) | 2019.03.24 |