데이터베이스 ! 자료구조

(1) 자료구조

1) 선형구조

1. 장점

* 간단한 자료구조

* 저장 효율이 뛰어남

*접근속도 가 빠름

2. 단점

* 삽입 삭제가 어려움

 

2) 연결 리스트

1. 형태

* 링크 정보를 가짐, ( 포인터 ) 

* 삽입  삭제는 쉽지만 , 저장 효율은 좋지 않음

2. 단점

* 엑세스 타임이 느림

* 기억 장소 효율이 나쁨

* 포인터를 위한 추가 공간이 필요

* 중간 노드 연결이 끊어지면, 다음 노드를 찾기 힘듦

3. 종류

* 단순 연결 리스트

* 이중 연결 리스트

* 단순 환형 연결 리스트 (순환형)

 

3) 스택

 PUSH = > TOP +1

 POP = > TOP - 1

1. 용도

* 인터럽트 처리

* 수식의 계산

* 서브루틴의 복귀 용도

4) 큐 ( Queue )

1. 정의

* FIFO, 질서구조

* 작업 스케줄링 등에 응용되기에 가장 적합한 구조

5) 데크 ( Deque)

     1. 양쪽 끝에서 입출력이 가능한 구조

* 입력 제한 데크 =  스크롤

* 출력 제한 데크 = Shelf 셸프

 

---------------------------

(2) 비선형 구조

1) 트리

1. 트리 용어 정리

* 최상위 노드 : 근노드 ( root node )

* 차수 : 제일 새끼 많이 친 것의 속성 개수 구하면 됨

* 깊이 ( level ) = 세대수로 계산

* 단노드 : Terminal 노드 , leaf 노드 , 새끼 못친애들 개수 구하면 됨

 

재정리하자면

* 단노드 : 링크포인트가 없는, 단절된 노드 단말노드(터미널 노드) 리프노드

* 깊이 : 레벨 루트는 1레벨, 몇세대 인지 구하는 것

 

* 노드 : 트리의 기본 구성 요소

 

2. 트리의 운행법

* preOrder : Prefix  = ROOT - > LEFT - > RIGHT

* InOrder : infix = LEFT -> ROOT - > RIGHT

* PostOrder : postfix = LEFT - > RIGHT - > ROOT

 

2) 이진 트리

1. 특성

* 깊이가 K 인 이진 트리의 최대노드의 수 = 2의 k승 -1

* 이진 트리의 레벨 i 에서 최대노드의 수  = 2의 k-1승

2. B 트리

* 한 노드 안에 있는 키 값을 오름차순 유지해서 빠르게 검색하는 방법

3. 신장 트리

* 그래프에서 간선들이 순환되지 않도록 만든 트리

4. 인접행렬

*          A   B  C

   A

   B

   C

그림 그린 후 연결 상태 를 작성 하면 됨