23.03.15 - Tree, Graph

1. Tree

정의

그래프의 여러 구조 중 단방향 그래프의 한 구조. 

하나의 뿌리로부터 가지가 사방으로 뻗은 형태. 나무를 거꾸로 뒤집어놓은 듯한 모습이다.

 

계층적 자료구조 : 데이터가 바로 아래에 있는 하나 이상의 데이터에 한개의 경로와 하나의 방향으로만 연결

비선형 구조 : 하나의 데이터 아래에 여러개의 데이터가 존재할 수 있음

사이클이 없음 : 계층적으로 표현되고, 아래로만 뻗어나가기 때문에 하나의 연결 그래프라고 할수있음

 

💡 사이클(Cycle)

시작 노드에서 출발해 다른 노드를 거쳐 시작노드로 돌아올 수 있는지. 

그렇다면 => 사이클이 존재한다.

 

용어

 

노드(Node) : 트리 구조를 이루는 모든 개별 데이터

루트(Root) : 트리 구조의 시작점이 되는 노드

부모 노드(Parent Node) : 상하관계로 연결된 두 노드 중 상대적으로 루트에 가까운 노드

자식 노드(Child Node) : 상하관계로 연결된 두 노드 중 상대적으로 루트에 먼 노드

리프(Leaf) : 트리 구조의 끝 지점이며 자식 노드가 없는 노드

깊이(Depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이. 루트 노드는 깊이가 0

레벨(Level) : 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 표현하는것. 

형제 노드(Sibling Node) : 같은 레벨에 나란히 있는 노드

높이(Height) : 리프 노드를 기준으로 루트 까지의 높이

서브 트리(Sub Tree) : 루트에서 뻗어나오는 큰 트리 내부에서 트리 구조를 갖춘 작은 트리

 

 

예시

컴퓨터 디렉토리 구조, 대진표, 가계도, 조직도 등

 

 

1) 이진 트리(Binary Tree)

자식 노드가 최대 두개인 노드로 구성된 트리.

자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉨. 이진 탐색 트리와 이진 힙 구현에 사용되고, 효율적인 검색과 정렬을 할 수 있다. 

 

 

 

정 이진 트리(Full binary tree) : 각 노드가 0개 또는 2개의 자식 노드를 갖는다

완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차있어야 하고, 마지막 레벨의 노드는 전부 차있지 않아도 되지만 왼쪽이 채워져야 한다. 

포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우. 모든 리프노드의 레벨이 동일하며 모든 레벨이 가득 채워져 있음

 

 

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

이진 탐색 알고리즘이 적용된 특별한 형태의 이진 트리. 

 

💡 이진 탐색

정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나. 

오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나누고, 둘 중 탐색이 필요한 부분만 탐색하도록 범위를 제한하여 원하는 값을 찾는다.

 

순서

1. 배열의 중간에 찾는 값이 있는지 확인
2. 중간값이 찾는 값이 아닐 경우, 오름차순으로 정렬된 배열에서 중간값보다 큰값인지/작은 값인지 판단
3. 찾는 값이 중간값보다 작을 경우 => 배열의 맨 앞부터 중간값 전까지의 범위를 탐색범위로 잡고 탐색을 반복 수행
4. 찾는 값이 중간값보다 클 경우 => 배열의 중간값 다음 값부터 맨 마지막까지를 탐색범위로 잡고 탐색을 반복 수행

 

 

이진 탐색 트리의 특징

각 노드에 중복되지 않는 키(Key)가 있음

루트노드의 왼쪽 서브트리 - 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어짐

루트노드의 오른쪽 서브트리 - 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어짐

좌우의 서브트리 모두 이진 탐색 트리

 

=> 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐

 

이진 탐색 트리의 탐색 과정

트리의 높이가 h(height)라면 o(h)의 복잡도를 가진다. 

 

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 만약 찾는 값이라면 탐색 종료.
2. 찾는 값이 루트 노드의 키보다 작다면 왼쪽 서브트리로 탐색을 진행
3. 찾는 값이 루트 노드의 키보다 크다면 오른쪽 서브트리로 탐색 진행

이 과정을 찾고자 하는 값을 찾을때까지 반복해서 진행한다.

찾는 값이 없을경우는 그대로 연산을 종료한다. 

=> 최대 트리의 높이(h)만큼 탐색이 진행됨 

 

주의할 점은 트리 안에 찾고자 하는 값이 없더라도 최대 h번(트리의 높이)만큼의 연산 및 탐색이 이루어진다. 

 

 

3) 트리 순회 (Tree Traversal)

특정 목적을 위해 트리의 모든 노드를 한번씩 방문하는것.

트리의 모든 노드를 순회하는 방법에는 전위 순회, 중위 순회, 후위 순회 세가지가 있다.

이 방식들 모두 왼쪽에서 오른쪽으로 조회한다는 공통점이 있음.

 

전위 순회(Preorder Traverse) : 루트 > 왼쪽 > 오른쪽

루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 탐색이 끝나면 오른쪽 노드를 탐색한다. 

주로 트리를 복사할때 사용된다. 

 

 

중위 순회(Inorder Traverse) : 왼쪽 > 루트 > 오른쪽

제일 왼쪽 끝에 있는 노드부터 순회하기 시작해 루트를 기준으로 왼쪽 노드들의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다. 이진 탐색 트리의 오름차순으로 값을 가져올때 사용된다.

 

후위 순회(Postorder Traverse) : 왼쪽 > 오른쪽 > 루트

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

 

레벨 순회(Levelorder Traverse)

루트를 방문하는 기준으로 순회하는 것이 아닌 트리의 레벨 기준으로 노드들을 방문하는 순회 방법이다. 

루트 노드를 시작으로 아래로 뻗어나가면서 노드들을 방문하고, 루트 노드의 레벨이 1레벨이라고 했을때 아래로 내려갈수록 레벨이 증가한다. 동일한 레벨에 여러개의 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 방문한다. 

 

 

순회방식을 나누는 이유

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

 

 

 

 

 

 

******************************

 

https://hanamon.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC-%EC%9D%B8%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC-bst/

 

https://yeolco.tistory.com/55