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

이진트리 (Binary Tree) 란?

모든 노드들이 둘 이하 ( 0, 1, 2 )의 자식을 가진 트리이다.

 

이진 탐색 트리 (Binary Search Tree) 란?

왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리이다.

 

이진 탐색 트리는 기본적으로 이진 트리에 데이터의 대소를 비교해 왼쪽이나 오른쪽 노드에 저장한다. 탐색을 목적으로 한 자료구조이기 때문에 데이터의 중복을 허용하지 않는다.

 

포화 이진 트리 : 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리.

왼쪽은 편향 이진트리, 오른쪽은 포화 이진 트리

트리에 데이터가 한쪽 방향으로만 저장되는 경우 탐색 속도는 O(N), 포화 이진 트리의 경우 탐색 속도는 O(logN)이다.

 

따라서 편향 이진 트리의 경우 탐색속도 저하와 공간 낭비를 불러올 수 있다.