[자료구조] 트리(Tree)

트리(Tree)

- 비선형 자료구조 

- 계층적 자료구조

- 노드 들이 링크로 연결되어 있다

- 목적 : 탐색(의사결정, 파일 시스템, 검색엔진, 라우터 알고리즘 등에서 사용)

용어

루트노드 : 레벨 = 1 

잎노드(단말노드) : 자식 노드가 0인 노드

서브트리(sub tree) : 트리 내부의 작은 트리

포레스트(Forest) : 트리가 여러 개 모인 것

레벨(level) : 루트에서 그 노드 까지의 거리를 말함

높이(depth) : 트리의 최대 레벨

차수(degree) : 자식 노드의 개수

Binary tree 종류

완전 이진트리 (Complete Binary tree)

- 노드가 위에서 아래로 왼쪽에서 오른쪽으로 채워진다

- 잎노드 두개의 레벨 차가 1 이하이다

- heap구현시 완전 이진트리를 기본으로 하며 , 전통적으로 배열을 이용해 구현한다

- 노드 수 : 2의 h 제곱 ~ 2의 (h+1)제곱 -1 사이의 값을 가진다

사향 이진트리(Skewed Binary tree) 

- 한쪽 방향으로 지속적으로 내려가는 트리

- 트리의 장점을 살리기 어렵다

포화 이진트리(Full Binary tree)

- 모든 레벨이 꽉찬 이진 트리

- 잎노드를 제외한 모든 노드들이 2개의 자식을 갖는 트리

- 노드 수 : 2의 (h+1)제곱 -1 

순회(Traversal)

트리를 탐색하는 순서

(아래 알파벳은 맨위의 그림을 순회기법 순서대로 나열)

전위순회(Preorder Traversal) 

- 순서 : 루트 > 좌 > 우

- F B A D C E G I H

중위순회(Inorder Traversal)

- 순서 : 좌 > 루트 > 우

- A B C D E F F G H I

후위순회(Postorder Traversal)

- 순서 : 좌 > 우 > 루트

- A C E D B H I G F

이진탐색트리(Binary Search Tree)

- 이진 탐색 트리는 탐색작업을 효울적으로 하기 위한 자료구조

- 모든 원소는 서로 다른 유일한 키를 가짐

- 왼쪽 서브트리에 잇는 원소들의 값은 그 루트의 값 보다 작음

- 오른쪽 서브트리에 있는 원소의 값들은 그 루트의 값보다 큼

- 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리

- 왼쪽 서브트리 값 < 루트 노드값 < 오른쪽 서브트리 값 관계 형성 

- preorder를 수행하면 오름차순으로 정렬된 값을 얻을 수 있다

 

탐색

- 루트에서 탐색 시작

- x=루트 노드의 키 값인 경우 : 원하는 원소를 찾았으므로 탐색 연산 성공

- x<루트노드의 키 값인 경우 : 루트 노드의 왼쪽 서브 트리에 대해서 탐색

- x>루트노드의 키 값인 경우 : 루트 노드의 오른쪽 서브 트리에 대해서 탐색

X = 11인 값을 찾는 탐색 연산

1. 11을 루트 노드의 키값 8 과 비교 X>루트 이므로 오른쪽으로 이동

2. 오른쪽으로 내려온 노드 10과 X값 비교 X>10 이므로 오른쪽 이동

3. 오른쪽으로 내려온 노드 14와 X값 비교 X<14 이므로 왼쪽 이동

4. 왼쪽으로 내려온 노드의 값이 X값과 같으므로 종료

삽입

1. 삽입전 같은 값의 원소가 있는지 확인해야 하므로 탐색연산 실행

2. 탐색연산 실패한 위치에 원소 삽입

삭제

삭제할 노드가 단말노드인 경우

- 탐색을 통해서 위치를 찾은 후 삭제

삭제할 노드가 1개의 자식노드를 가진 경우

- 탐색을 통해서 지우려는 대상노드의 자식노드를 대상노드의 자리에 넣어주고 대상노드는 삭제

삭제할 노드가 2개의 자식노드를 가진 경우

방법1. 왼쪽 서브트리의 가장 큰 값을 가져와서 대상노드에 넣어주고 대상노드 삭제

방법2. 오른쪽 서브트리의 가장 큰 값을 가져와서 대상노드에 넣어주고 대상노드 삭제

Java 로 구현한 Binary Search Tree

 TreeNode. 

BinarySearchTree.