트리

트리(Tree)란?

• 트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.
• 서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른다.
• 힙(Heap)을 구현하는 방법 중 하나가 트리이다.

트리(Tree)의 구조

• 루트 노드(root node) : 부모가 없는 노드로 트리는 단 하나의 루트 노드를 가진다. (ex : A- 루트노드)
• 리프 노드(leaf node) : 자식이 없는 노드로 terminal 노드라고도 부른다. (ex : C, D, E - 단말 노드)
• 내부 노드(internal node) : 리프 노드가 아닌 노드(ex : A, B - 내부 노드), non terminal node라고도 부른다.
• 간선(edge) : 노드를 연결하는 선
• 형제(sibling) : 같은 부모 노드를 갖는 노드들 (ex : D-E, B-C : 형제)
• 노드의 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수(ex : D의 depth : 2)
• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 ( ex : level 1- {B, C} )
• 노드의 차수(degree) : 자식 노드의 개수 (  ex : B의 degree - 2, C의 degree - 0)
• 트리의 차수(degree of tree) : 트리의 최대 차수 ( ex : 위 트리의 차수는 2이다)

트리(Tree)의 특징

• 트리 자료구조는 일반적으로 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료구조이다.
• 트리의 구조는 '데이터 저장'의 의미보다는 '저장된 데이터를 더 효과적으로 탐색'하기 위해서 사용된다.
• 리스트와 다르게 데이터가 단순히 나열되는 구조 X --> 트리는 부모(parent)와 자식(child)의 계층적인 관계로 표현된다.
• 트리는 사이클이 없다.
• 트리에서 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다.

이진트리와 이진검색트리

완전이진트리란?

완전이진트리

• 마지막 레벨을 제외한 레벨은 노드를 빠짐없이 가득 채운다
• 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 빠짐없이 채우되 반드시 끝까지 채울 필요는 없다

이진 탐색 트리 탐색(Search)

이진 탐색 트리의 특징

1. 트리 내에 같은 값을 가지는 Node가 없다
2. 왼쪽 Child의 모든 Node는 현재 Node보다 작다
3. 오른쪽 Child의 모든 Node는 현재 Node보다 크다

이진 탐색 트리의 탐색은 다음과 같은 과정을 거친다.

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

위 과정을 찾고자 하는 값을 찾을 때까지 반복해서 진행한다. 만약 값을 찾지 못한다면 그대로 종료한다.

이러한 탐색 과정을 거치면 최대 트리의 높이(h)만큼의 탐색이 진행되게 된다. 예를 들어보자.

 

 

탐색과정

 

위와 같은 트리에서 키가 5인 노드를 찾고자 한다면, 가장 먼저 루트 노드와의 비교가 이루어진다.

5가 7보다 작으므로 왼쪽 서브 트리로의 탐색이 이루어지고, 이후 5가 3보다 크므로 오른쪽 서브트리로 탐색이 이루어진다. 마지막으로 키가 5인 노드를 찾았으므로 탐색이 종료된다. 즉 트리의 높이인 3번 만큼의 탐색이 이루어졌다. 만약 8을 찾는다면 2번의 연산이 진행되었을 것이다. 즉, 트리 안의 값을 찾는다면 무조건 트리의 높이(h) 이하의 탐색이 이루어지게 된다.

 

트리 안에 찾고자 하는 값이 없더라도 최대 h 번 만큼만의 탐색이 진행된다. 예를 들어 위 트리에서 6이라는 값을 찾는다고 하면 위 그림과 같은 과정을 거치고 탐색이 종료된다. (직접 위 그림에서 과정을 생각해보자) 마지막으로 탐색하게 되는 5를 키로 갖는 노드에서 6은 5보다 크므로 오른쪽 서브트리로 탐색을 진행해야 하는데 오른쪽 서브 트리가 없으므로 탐색이 종료되는 것이다. 

 

AVL트리 

모든 Node의 왼쪽과 오른쪽 서브트리 높이 차가 1 을 넘지 않는다

트리의 균형을 재조정하는 추가작업이 필요하다

밸런스가 꺠진시점에서 중간값을 기준으로 재정렬 한다