비선형구조에 대해 알아 보도록 하겠습니다.
5-1. Tree구조
Tree구조는 삽입, 추가가 용이하여 데이터 베이스, Search, Sort 등에 사용된다. 츄리는 정점과 선분으로 형성된 그래프(Graph)의 특수한 경우이며 그래프를 형성하는 정점가운데서 어떠한 두 정점 사이에도 사이클(Cycle)이 형성되지 않고 근노드(Root node)라고 하는 한개의 정점을 갖는 연속 그래프를 말한다. 가계 족보, 연산 수식, 회사의 직제편성등과 같은 구조를 갖는다.
5-2. 기본용어
【예】2진 Tree
(1) 디그리(Degrree) : 주어진 Pointer에서 퍼지는 Node의 수(3)
(2) 근노드(Root node) : 전승자가 없는 노드(a)
(3) 단노드(Terminal node)
디그리(Degree)가 0인 노드( ⓔ ⓕ ⓖ ⓗ ⓘ ⓙ :6개)
(4) 레벨(Level) : 계층(3)
(5) 간노드(Nonterminal Node)
자노드(son node)를 갖는 노드(ⓐⓑⓒⓓ: 4개)
(6) 디그리(Degree)의 합 :간선의 합(9개)
【예】레벨 L인 노드의 자노드(son node)의 레벨은 L+1이다.
5-3. Tree의 종류
5-3-1. 이진츄리(Binary Tree)
Outdegree가 2를 넘지않는 Tree로서 대형 File의 Record를 Random하게 또는 순차적으로 Access하기가 쉽고 Record의 수정이 용이해서 많이 활용된다.
(1) 정이진 츄리(Full Binary Tree)
Level이 i일때 Node의 수가 정확히 2i-1인 Binary Tree
【예】 Binary Tree에서 깊이(Depth)가 4이면 이 Tree에서는 최대
2i-1=15개의 Node를 가질 수 있다.
(2) 전이진 츄리(Complete Binary Tree)
Node의 수가 N이고 깊이가 K인 정이진 형태로 Node가 배열된 Binary Tree
⑶ 사향 이진 츄리(Skwed Binary Tree)
한쪽으로만 치우친 Binary Tree로 가장 효율이 나쁘다.
— 정이진 츄리– — 전이진 츄리 — — 사향 이진 츄리 —
【예】3개의 Node(노드)로 표현되는 5개의 Binary Tree
5-4. 이진츄리의 운행법
어떤정보를 Binary Tree로 표시한 후 정보를 검색하는 방법은 다음과 같다.
5-4-1. Order법
⑴ Inorder 운행법: Left-Root-Right
⑵ Preorder운행법 : Root-Left-Right
⑶ Postorder운행법 : Left-Right-Root
【예】2진 Tree의 운행
5-4-2. FIX표기
산술식의 표기시 연산기호의 위치에 따른 운행법으로, Infix, Prefix, Postfix등이 있다.
(1) Tree의 운행
Infix는 Inorder, Prefix는 Preorder, Postfix는 Postfix 방식으로 운행한다.
【예】A*B+C/D를 Infix, Postfix, Prefix로 변환
(2) Infix를 Prefix, Postfix로 변환
【예】Infix ( ( A * B ) + ( C / D ) )를 Prefix로 변환
주어진 식을 괄호로 완전히 묶은다음 ①②③순서대로 연산자를 좌측의 위치로 옮기면 다음과 같이 Prefix결과를 얻을 수 있다.
결과 : +*AB/CD
【예】Infix ( ( A * B ) + ( C / D ) )를 Postfix로 변환
결과 : AB*CD/+
5-4-3. Path
트리의 패스길이는 근노드로부터 각 노드에 이르는 거리의 합계를 의미한다.
(1) 내부 패스 길이(Internal Path Length)
근노드부터 각 노드에 이르는 길이의 합.
(2) 외부 패스 길이(External Path Length)
외부패스=내부패스+2n(n은 노드의 수)
【예】2진 Tree의 내부Path의 길이와 외부 Path길이
5-5. 그래프(Graph)
5-5-1. 그래프 용어
【보기】Graph
(1) 정점 (Vertex) : ABCDE
(2) 간선(Edge) : 8개의 선
(3) 차수(Degree) :정점에 접한 간선의 합(16)
A : 3개, B : 4개, C : 2개, D : 4개, E : 3개
5-5-2. 그래프의 종류
(1) 단순 그래프 : 단순한 V(G), E(G)로 구성된 그래프
(2) 일반그래프 : Loop와 다중간선을 포함하고 있는 그래프
(3) 무방향성 그래프 : 간선 E(G)의 순서가 없는 그래프
(4) 방향성 그래프 : 간선 E(G)의 순서를 갖는 그래프
(5) 완전 그래프
무방향성 그래프에서 정점이 N개일 때 간선의 수가
【예】아래의 그래프에서 정점수가 4이므로
개의 간선을 갖는 완전 그래프가 된다.
【예】아래의 그래프에서 정점수가 3이므로
개의 간선을 갖는완전 그래프가 된다.
【예】 방향성 그래프에서 3개의 정점(Vertex)을 갖는 경우 완전 그래프가 3*2=6의 간선(edge)을 갖는다.
(6) 정규그래프(Regular Graph) : 정점의 차수가 동일한 그래프
(7) 평면그래프
연결선들이 평면상에서 서로 교차하지않는 단순 그래프를 의미한다.
5-5-3. 그래프 운행법(Traversable)
(1) DFS : 깊이우선, (2) BFS : 넓이우선
【예】그래프의 운행(Traversable)
정점을 한 번만 거치면서 출발 정점으로 되돌아 오는 Cycle이 존재하는 그래프
【예】운행 가능한 그래프
이상 “비선형구조”에 대해 알아 보았습니다.
답글 남기기