자료구조 Tree

1. Tree란?

Tree의 정의

트리는 정점(Node)와 선분(Branch)을 이용하여 사이클이 이루어지지 않게 구성된 자료구조이다.
데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.
트리구조는 계층적으로 표현이 되고, 사이클이 없다.
따라서 사이클이 없는 하나의 연결 그래프라고 할 수 있다.

1-1) Tree의 용어

• 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가진다.
• 단말 노드(leaf node) : 자식이 없는 노드
• 간선(edge) : 노드를 연결하는 선
• 형제(sibling) : 같은 부모를 가지는 노드
• 조상 노드(ancestors node) : 임의의 노드에서 루트 노드에 이르는 경로상에 있는 노드들
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야하는 간선 수
• 노드의 차수(degree) : 각 노드에서 뻗어나온 가지의 수
• 트리의 차수(degree of tree) : 트리에서 가장 큰 차수
• 트리의 높이(height) : 가장 깊숙히 있는 노드의 깊이

1-3) Tree의 특징

• 부모-자식 관계가 존재해 레벨이 존재한다.(최상위 노드=Root)

• 노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k개

• 방향성이 존재하고 사이클은 존재하시 않는다.(비순환)

• 트리의 순회는 전위순회, 중위순회, 후위순회 3가지가 존재한다.

2. Tree 순회

2-1) Tree 순회 방법

• 전위 순회 (preorder traverse) : 가장 먼저 루트를 방문하고, 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤,왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
  즉, 부모 노드가 제일 먼저 방문되는 순회 방식이다.

• 중위 순회 (inorder traverse) : 루트를 가운데에 두고 순회한다.루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 루트로 이동하여 마저 탐색한다. 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식이다.
  중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.

• 후위 순회 (postorder traverse) : 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하여 루트를 거치지 않고 오른쪽 노드로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
  후위 순회는 트리를 삭제할 때 사용한다. 자식의 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문이다.

2-2) 순회 방식을 나누는 이유

일정 조건에 의해 설계된 트리 구조는 자식 노드에 대한 조건이 명확하다면 원하는 값을 쉽게 찾아 낼 수 있지만, 트리 구조 전체를 탐색할 때는 이야기가 다르다.
모든 노드를 방문하기 위해서는 일정한 조건이 필요하고, 트리 구조를 유지보수하거나 특정 목적을 위해 순회 방법에 대한 정의는 필수적으로 필요하다.

3. 이진 트리(Binary tree)

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용한다.
이진트리는 자식 노드가 최대 두개인 노드들로 구성된 트리이다.
이 두개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.

3-1) 이진 트리의 종류

이진 트리는 자료의 삽입, 삭제 방법에 따라 구분 된다.

• 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.
• 포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
• 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
  

이러한 이진 트리는 이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다.

3-2) 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란, 이진 탐색과 연결 리스트를 결합한 이진트리를 말한다.
이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.

3-3) 이진 탐색 트리의 특징

• 각 노드에 중복되지 않는 키(Key)가 있습니다.
• 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있습니다.
• 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있습니다.
• 좌우 서브트리도 모두 이진 탐색 트리여야 합니다.

Graph이란?

Graph의 정의

그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다.
이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다.

Graph의 용어

• 정점(vertext) : 위치라는 개념
• 간선(edge) : 정점을 연결하는 선
• 인접 정점(adjacent vertex) : 간선에 직접 연결된 정점
• 차수(degree) : 한 정점에 연결된 간선의 수 (주로 무방향 그래프에서 사용)
• 입력 차수(in-degree) : 한 정점으로 들어오는 간선의 수 (주로 방향그래프에서 사용)
• 출력 차수(out-degree) : 한 정점에서 나가는 간선의 수(주로 방향그래프에서 사용)
• 사이클(cycle) : 한 정점에서 출발하여 시작했던 정점으로 돌아오는 경로
• 가중치 그래프 : 간선마다 가중치 값이 매겨져있는 그래프

Graph의 특징

• 그래프는 순환 혹은 비순환 구조를 이룬다

• 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있다.

• 루트 노드의 개념이 없다 / 부모-자식 관계라는 개념이 없다.

• 2개 이상의 경로가 가능하다.(무방향, 방향, 양방향 가능)

• 그래프는 네트워크 모델이다.

Graph의 종류

1. 무방향 그래프(Undirected Graph)
   : 간선을 통해 양방향으로 갈 수 있다.
   정점 A와 정점 B를 연결하는 간선은 (A,B), (B,A) 이다.
   
2. 방향 그래프(Directed Graph)
   : 간선에 방향성이 존재하는 그래프
   A -> B로 갈 수 있는 간선은 (A, B)로 표시한다.
   
3. 가중치 그래프(Weighted Graph)
   : 간선을 이동하는데 비용이나 가중치가 할당된 그래프
   네트워크라고도 한다.