Graph
Graph의 개념
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이며, n:n의 구조를 가지고 있다. 하나 이상의 정점 V(vertex)와 두 정점간의 관계인 간선 E(edge)로 구성되어 있다. 또한 인접 행렬이나 인접 리스트로 메모리에 표현되고 처리될 수 있다.
Graph와 관련된 용어
- 정점(vertex) : 위치라는 개념 (node)
- 간선(edge) : 각 정점들을 연결하는 선, 위치 간의 관계
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
- 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
Graph의 종류
- 무방향 그래프
- 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
- 정점 A와 정점 B를 연결하는 간선은 (A,B)와 같이 정점의 쌍으로 표현한다.
- ex) 양방향 통행
- 방향 그래프
- 간선에 방향성이 존재하는 그래프 (트리)
- A → B 로만 갈 수 있는 간선은 <A, B>라고 표시한다.
- ex) 일방 통행
구현 방법
- 인접 리스트
Tree
트리(Tree)의 개념
Tree는 자료 구조의 꽃이라고 부른다. 선형 자료 구조의 알고리즘 보다 더 빠른 속도를 자랑한다. Tree는 계층적 관계에 있는 원소들을 나타낸다. 마치 디렉토리와 비슷한? 같은? 개념이라고 생각하면 된다. 혹은 회사 조직도를 떠올리면 좋을 것이다. 기본적으로 부모와 자식이라는 계층적인 개념을 기본으로 한다. Tree의 특징은 다음과 같다.
- Tree는 하나의 루트 노드를 가진다.
- 루트 노드는 0개 이상의 자식 노드를 가진다.
- 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 마치 나무의 뿌리(루트)부터 가지가 생기고 잎이 생기는 모양으로 반복적으로 정의 된다. 물론 Tree를 그림으로 표현할 때는 뿌리가 위에 오도록 표현한다.
- 노드와 노드를 연결하는 간선들로 구성되어 있다.
트리(Tree)와 관련된 용어
- 노드(node) : 트리의 구성 요소로, 각 원소들이 노드이다. ex) A,B,C,D ...
- 부모 노드(parent node) : 어떤 원소의 바로 위에 있는 원소 ex) B는 D의 부모 노드
- 자식 노드(Child Node) : 어떤 원소의 바로 아래에 있는 원소 ex) H는 D의 자식 노드
- 형제 노드(sibling) : 같은 부모를 가지고 있는 자식 노드 ex) D, E는 형제 노드
- 루트 노드(root node) : 부모가 없는 노드, 반드시 한 개가 존재한다. ex) A는 루트 노드
- 리프 노드(leaf node) : 더 이상 자식이 없는 노드. 외부 노드 라고도 한다. ex) H,I,J
- 간선(edge) : 노드를 연결하는 선
- 노드의 크기(size) : 자신을 포함한 자식 노드의 개수 ex) B의 크기는 3
- 노드의 깊이(depth) : 루트에서 특정 노드에 도달하기 위해 거치는 간선의 수 ex) D → 2
- 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 ex) level1 → B, C
- 노드의 차수(degree) : 각 노드가 가지고 있는 가지의 수(하위 자식 노드의 개수 ex) D → 2
- 트리의 차수(degree of tree) : 트리에 있는 차수 중 가장 큰 차수 ex) 최대 차수는 2
- 서브 트리(sub tree) : 기존 트리 내에서 만들어진 작은 트리
- 높이(height) : 리프 레벨의 최댓값, 루트 노드부터 가장 멀리 떨어진 리프 노드까지의 거리
트리(Tree)의 종류
- 일반 트리 : 각 노드의 자식 노드 개수를 제한하지 않은 트리를 말한다.
- 이진 트리 : 각 노드의 자식 노드 개수를 최대 2개로 제한한 트리를 말한다.
- 이진 탐색 트리 : 모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들(모든 노드 n에 대해서 반드시 참)
Binary Tree(B-Tree)
이진 트리(Binary Tree)의 개념
Binary Tree는 Tree의 한 종류로 각 노드의 자식 노드 개수를 최대 2개로 제한한 트리이다. 트리는 선형 자료 구조 알고리즘에 비해서 원하는 데이터를 찾는 속도가 빠르다. 선형 리스트에서 1부터 10까지 데이터를 넣었다고 가정 했을 때, 9번째 노드를 찾는다고 해보자. 일반적으로는 0번지 부터 8번지까지 검사하고 나서야 비로소 찾고자 하는 데이터를 찾았다. 트리는 같은 상황에서 같은 데이터를 찾는다고 해보자.
먼저 최상위 노드인 1번 노드에서 왼쪽 → 오른쪽 으로 검사한다고 했을 때, 트리의 검사법은 자식 노드가 비어있을 때 까지 아래로 파고 내려가는 방식이다. 트리에서 9번 노드를 검사하고자 할 때, 먼저 1번 노드를 만날 것이다. 그리고 왼쪽 노드인 2번 노드, 다시 왼쪽인 8번 노드까지 탐색한다. 리프 노드까지 탐색했지만 찾지 못한다면, 부모 노드로 올라와서(4번 노드) 오른쪽을 검사한다. 마침 9번 노드를 만났다. 순서를 살펴보면 다음과 같다.
1번 → 2번 → 4번 → 8번 → 9번
위의 선형 리스트의 방식에 비해서 4회 만큼이나 검사 횟수가 줄었다. 하지만, 만약 9번 노드가 7번 노드의 오른쪽에 있었다고 한다면, 이야기는 조금 달라진다. 오히려 검사 횟수가 늘기 때문이다. 이때 나온 방법이 이진 탐색 트리 이다.
이진 트리(Binary Tree)의 종류
- 완전 이진 트리(Complete Binary Tree)
- 트리의 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있어야한다.
- 단 마지막 레벨은 완전히 채워져 있지는 않지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
- 전 이진 트리(Full Binary Tree)
- 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리를 말한다.
- 포화 이진 트리(Perfect Binary Tree)
- 트리의 모든 레벨까지 완전히 꽉 채워진 트리를 말한다.
- 루트를 1번으로 2^h-1까지 정해진 위치 번호를 가진다.(h는 높이)
- 번호는 왼쪽에서 오른쪽으로 매긴다.
이진 탐색 트리?
일반 이진 트리는 찾고자 하는 데이터가 왼쪽에 가까울 수록 빠르지만, 오른쪽으로 갈수록 비교적 느리다. 이를 해결하기 위해 선형 리스트의 이진 탐색과 비슷한 개념을 도입했다.
임의의 데이터를 가진 새로운 노드를 입력 받았을 때, 이 데이터를 기존의 노드와 비교해서(부모 노드가 될 녀석) 작다면 왼쪽, 크다면 오른쪽에 넣는다. 이렇게 트리가 구성이 된다면, 찾고자 하는 데이터와 루트를 비교하고 루트보다 작다면 왼쪽만 탐색하면 되고, 루트보다 크다면 오른쪽을 기준으로 찾으면 될 것이다.
