자료구조 - [Tree]

1. 트리(Tree)

 

  계층적인 자료를 표현하는 대표적인 자료구조.

검색 알고리즘을 위해 주로 사용된다.

가장 위에 하나의 루트(Root)로부터 출발하여 그 밑에 0개 이상의 여러 자식 노드들을 가지는 구조

*** 하나의 자식은 하나의 부모만 가질 수 있다 ***

 

이진 트리 : 

노드의 최대 자식노드(Branch)가 2개인 트리

 

 

이진 검색 트리 : 

노드에서 노드보다 작은 값은 왼쪽,

큰 값은 오른쪽으로 보내는 식의 구조

 

따라서 전체 트리가 소트되어 있는 것과 같은 효과를 같게 되어

검색에 있어 배열이나 이진트리처럼 순차적으로 모든 노드를 검색하는 것(O(n))이 아니라,

매 검색마다 검색영역을 절반으로 줄여 O(log n)으로 검색할 수 있게 된다.

 

하지만 노드들이 한쪽으로 일렬로 기울어진 편향 이진 트리(Skewed Binary Tree)인 경우,

검색영역을 n-1로만 줄이기 때문에 O(n)만큼의 시간이 소요된다.

 

. 아래는 그림이 숫자를 크고 작음을 기준으로 나눈 이진 탐색 트리 예시이다.

 

 

이진 트리의 구조

숫자 탐색 예시