이진 트리와 이진 탐색 트리

이진트리(BT, Binary Tree)

 

이진트리 BinaryTree라고도 부릅니다.

이지트리란 각각의 노드의 자식노드 수가 2개 이하로 구성되어 있는 트리를 의미하며

아래와 같이 구분합니다.

왼쪽부터 시작해서 정이진트리, 완전 이진트리, 변질 이진트리, 포화 이진트리, 균형 이진트리라고 합니다.

 

정이진 트리(Full Binary Tree)

 

자식 노드가 0 또는 2개인 이진트리를 말합니다.

 

완전 이진트리(Complete Binary Tree)

 

왼쪽에서부터 채워져있는 이진 트리를 의미합니다.
마지막 레벨(위 사진은 레벨3 or 2)을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있는 것을 의미합니다.

 

 

변질 이진 트리(Degenerate Binary Tree)

 

자식 노드가 하나밖에 없는 이진트리를 의미합니다.

 

 

포화 이진 트리(Perfect Binary Tree)

 

모든 노드가 꽉 차있는 이진트리를 의미합니다.

 

 

균형 이진 트리(Balanced Binary Tree)

 

모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리입니다.
map이나 set을 구성하는 레드 블랙트리는 균형 이진트리 중 하나입니다.

와 균형 이진트리 이해하는데 좀 걸렸다..

위의 사진을 봅시다.

깊이차이가 2개나 차이나면 균형 이진트리가 아닙니다.

 

하지만 이거는 균형 이진트리가 될 수 있죠.

깊이차이가 1이하이기 때문입니다.

그렇대요.

 

 

이진 탐색 트리(BST, Binary Search Tree)

 

이진 탐색 트리란 이진트리의 일종으로 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 값이 있는 노드만 포함이됩니다.

왼쪽 하위트리에는 노드의 값보다 작은 값이 있는 노드만 포함되는 트리를 말합니다.

이렇 듯 이진 탐색트리는 왼쪽은 작은 값 오른쪽은 큰 값

 

이러한 이진 탐색트리가 구성된 이유는 검색(Search)하기에 용이하기 때문입니다.

왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있기에 6을 찾으려 한다면 루트에서 시작해서 8보다 작으니 왼쪽에 가게 되고 3보다 크니 오른쪽을 가게되어 단 2번만에 찾게 됩니다.

한마디로 루트노드에서 일단 왼쪽 노드들만 보면 된다라는 뜻입니다.

오른쪽 노드들은 볼 필요가 없어지게 되는 거죠.

이렇게 하면 전체탐색을 하지 않아 시간이 단축되게 됩니다.

 

그렇다면 이렇게 빨라 보이는 이진탐색트리의 시간복잡도는 몇일까요?

탐색, 삽입, 삭제, 수정 모두 O(logN)이라는 시간이 걸립니다.

 

하지만 이는 삽입 순서에 따라 시간복잡도가 달라지는데요.

만약 1~4까지 삽입을 한다라고 치고 1을 찾는다고 치면

이러한 선형자료구조가 됩니다.

1을 찾는다면 logN이 아닌 O(N)이 되어버리게 됩니다.

 

그래서 삽입순서가 어떻게 되든간에 트리의 노드를 회전시키는 등 방법을 구해서 균형잡히게 만든 이진 탐색트리에서 발전된 트리로 AVL 트리, 레드 블랙 트리가 있습니다.

예를 들어 map이라는 자료구조는 삽입, 탐색, 삭제, 수정의 시간 복잡도가 모두 O(logN)임을 보장합니다.

그 이유는 레드블랙트리 기반으로 구현되어있기 때문인데요.

 

AVL 트리와 레드 블랙트리는 나중에 또 배우도록 하겠습니다.

 

안녀어어엉