Notice
Recent Posts
Recent Comments
Link
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Archives
Today
Total
관리 메뉴

dongdorodongdong

자료구조 본문

Database

자료구조

d5ngs 2019. 3. 25. 18:04

정의

- 자료를 기억장치 내에 저장하는 방법



분류

  1. 선형 구조
    - 순차리스트 (스택, 큐, 데크, 배열)
    - 연결리스트
  2. 비선형 구조
    - 트리
    - 그래프

순차 리스트(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