tree

tree

 

데이터 구조의 하나로 , 데이터 항목의 한 묶음을 세그먼트라고 하는데, 이 세그먼트 사이의 연결을 나뭇가지처럼 생각한 것이 트리구조이다. 상위 세그먼트(부모) 는 하나 이상의 하위 세그먼트(자식)를 가지고 있으나, 하위 세그먼트는 반드시 한 상위 세그먼트 밖에 가질 수 없다.

용어 정리

레벨 : 트리의 층을 표현하며 가장 높은 레벨 값이 트리의 높이이다 . 가장 위의 레벨은 0이고 내려갈수록 증가한다.

루트노드: 부모가 존재하지 않는 노드

리프노드(단말노드): 자식이 없는 노드

 

이진트리

트리구조중에서도 이진트리라는 개념은 자식노드가 2개 이하인 트리이다.

예를 들면 왼쪽그림의 경우에는 부모가 4개의 자식노드를  가지고 있으므로 이진트리가 아니다

오른쪽 그림의 경우에는 모두 자식 노드가 2개이하이므로 이진트리라고 할 수 있다.

 

완전이진트리

 

이러한 경우에는 완전이진트리를 배열로 구현할 수 있다.

 

이진탐색

탐색 알고리즘중에 한가지 방법으로 O(logN)의 시간복잡도를 가진다.

1. 정렬되어있는 데이터에 적용가능하다.

2.  데이터의 절반 지점을 기준으로 나누면서 탐색하는 방법이다.

 

이진탐색트리

1. 이진탐색을 사용 할 수 있게 고안된 이진트리

2. 데이터 입력시 O(logN) 효율 

3. 탐색 효율 O(lonN) 이다.

4. 트리의 모양이 밸런스가 유지 되지 않으면 제대로 된 효율이 나오지 않는다.

 >> 이러한 문제를 해결하기 위해서 자가균형 기능이 필요한데 대표적으로 AVL, Red/Black 등이 있다.