2주차 개념 #3. 이진트리와 이진탐색트리

2주차 개념 #3. 이진트리와 이진탐색트리

오늘은 이진트리와 BST 라고 불리는 이진탐색트리까지 얘기를 해보도록 하겠습니다.

일단은 이진트리, BST라고도 불리죠. 이진트리에 대해서 얘기를 해보도록 할텐데, 이진트리는 각각의 자식노드 수가 2개 이하로 구성되어 있는 트리를 의미합니다.

뭐냐면 저희가 앞서서 트리에 대해서 배웠죠.

왼쪽도 트리고 오른쪽도 트리죠. 자 여러분 왼쪽 트리는 각각 몇개의 자식노드를 가지고 있을까요?

이렇죠.

그리고 이 트리는 루트 노트의 자식노드가 4개이죠.

그러니까 모양이 예쁘지 않더라도

이런 것도 트리(Tree)라는 거예요.

그런데 이렇게 제거를 하면, 자식 노드가 2개 이하인 트리가 완성 되죠. 이러한 트리를 이진트리라고 하는 겁니다.

즉, 각각의 노드의 자식노드 수가 2개 이하로 구성되어있는 트리를 의미합니다.

첫번째는 정이진트리, full binary tree라고 해서 자식노드가 0개 또는 2개인 이진트리를 의미합니다.

그리고 완전 이진트리는 왼쪽에서부터 채워져 있는 이진트리를 말합니다. 왼쪽에서부터 다 꽉 차있는데, 이따가 포화 이진트리를 설명할 때 조금 더 이해가 가실 거예요. 이 완전 이진트리는 왼쪽에서부터 채워져 있는 이진트리에요. 그러니까 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.

그리고 변질 이진트리 라고 하는거는 degenerate binary tree라고 해서 자식노드가 하나밖에 없어요.

뭐냐면 자 여러분 제가 질문 하나를 드릴게요.

여러분 이거 트리처럼 안 보이죠. 그런데 이것도 이진트리예요. 왜요?

자식노드가 다 2개 이하니까 이진트리죠.

그런데 이런 식으로 자식노드가 하나밖에 없는 트리를 degenerate binary tree 라고 합니다.

그리고 또 포화 이진트리 라는 건 모든 노드가 꽉 차있는거에요. 자, 앞서서 완전 이진트리는 왼쪽에서부터 채워져 있다. 그러니까 포화 이진트리는 완전히 꽉 차있는데, 완전 이진트리는 포화이진 트리가 되려고 하는 트리인데 왼쪽에서부터 채워지는 트리다 라고 보시면 되는 거예요.

그리고 마지막으로 가장 중요한 거는 균형이진 트리를 배워보도록 할텐데, 솔직히 이 다섯가지가 모두 중요하다 라고는 볼 수가 없어요. 여기 중에서 가장 중요한 트리가 뭐냐라고 했을 때 균형 이진트리 라고 보시면 돼요.

그러니까 사실은 전부 다 외우시면 정말 베스트 베스트이긴 한데, 외울 시간이 부족하다 그러면 이것만큼은 외워두셔야 된다라는 거에요.

균형 이진트리, balanced binary tree 라고 하는건데, 자 이건 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리입니다.

map, set을 구성하는 레드블랙트리는 균형이진트리 중 하나입니다.

이거는 균형잡힌 트리일까요? balanced 할까요?

balanced 합니다. 왜죠?

왼쪽 네모칸의 서브트리와 오른쪽 서브트리의 끝 노드를 기반으로 비교를 했을 때 깊이 차이가 1밖에 안 나죠.

그런데 만약에 이 트리를 보면, balanced 한가요? unbalanced 하죠.

이거랑 이거의 깊이차이가 무려 2개, 2칸이 납니다.

예를 들어서 이런 트리가 있다고 해봅시다. 이 트리는 균형잡혔다고 볼 수 있나요? 균형잡혔죠.

왼쪽 하위트리랑 오른쪽 하위트리랑 비교했을 때 깊이차이가 1밖에 안나죠.

만약에 하나가 더 추가 돼서

이렇게 되면 균형잡혔다고 볼 수 있을까요?

이 두 개의 하위트리만 보면 균형 잡혔다고 볼 수는 있죠. 그런데 다른 큰 하위트리들을 비교해보면,

unbalanced 합니다. 자 아무튼 이렇게 해서 균형 이진트리를 알아봤구요. 이게 제일 중요해요.

트리는 종류별로 다 외우시면 좋은데 균형 이진트리 만큼은 외워주세요.

---

자 이번에는 이진탐색트리 Binary Search Tree 라고 불리는 BST에 대해서 얘기를 해보도록 할게요.

자 이건 이진 트리 일종이에요. 일단 자식 노드의 수가 2개 이하인 거고요. 근데 한 개의 특징을 가지고 있어요. 뭐냐면, 노드의 오른쪽 하위 트리에는 "노드의 값보다 큰 값"이 있는 노드만 포함되고 왼쪽 하위트리에는 "노드의 값보다 작은값"이 들어있는 트리라는 특징이 있어요.

그니까 binary tree에다가 이러한 특징, 왼쪽에는 작은 거 오른쪽에는 큰거라는 특징을 가진 트리가 이진탐색트리 라고요.

자 그런데 왜 이게 Binary Search Tree 일까요? 왜냐면 이거는 이렇게 만들게 되면 검색하기에 굉장히 유리해요.

뭐냐면 봐요. 왼쪽에는 작은 값, 오른쪽에는 큰 값이 이렇게 정해져 있죠?

그니까 예를 들어서 만약에 10을 찾는다라고 해볼게요. 그럼 일단 제가 25까지 왔어요. 10이 25보다 작으니까 오른쪽엔 당연히 없겠죠. 그럼 왼쪽에는 무조건 있을 거 아니에요.

그래서 20으로 들어가요. 10은 20보다 작죠. 그래서 왼쪽으로 들어가면, 10을 찾아냅니다.

다시 한번 예를 들어볼게요. 저희가 Up&Down 하잖아요. Up&Down도 사실은 Binary Search Tree라는 구조가 들어가 있는 겁니다. BST 특징이 들어가 있는 거예요.

저희가 Up&Down 할 때 1부터 8 중에서 내가 생각한 수가 2라고 해볼게요.

처음에 제가 5를 말해요. 그럼 친구가 Down 합니다. 왜죠?

2는 5보다 작잖아요. 그럼 만약에 내가 1이라고 했을 때 Up 이라고 하겠죠. 그러니까 이런 식으로 큰 거는 오른쪽, 작은 거는 왼쪽 이라는 특징을 가지게 되면은 전체 탐색을 할 필요가 없어요.

뭐냐면, 봐요.

3을 7로 정정할게요. 여기서 만약 제가 1을 찾는다라고 하면,

10에서 이런 식으로 들어가면 되겠죠.

여기, 이 area는 찾을 필요가 없는거죠. 즉, 전체 탐색을 할 필요가 없다라는 거예요.

---

그러면 이 이진탐색 트리의 시간복잡도는 얼마일까요? 만약 이렇게 균형잡히게 분포가 되었다면 탐색, 삽입, 삭제, 수정 모두 O(logN) 일 거예요. 왜?

만약에 이런 트리가 있고, 내가 찾으려고 하는 값이 저 초록색 부분에 있다고 칠게요.

이 노드의 개수는 15개죠. 근데 이 트리 높이는 몇 개에요?

트리의 높이는 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리를 의미한다고 했죠.

그래서 높이는 3이에요.

자 우리가 이 초록색을 찾는다라고 했을 때, 전체 탐색을 안 하는 건 앞에서 배웠고,

루트노드에서부터 시작했을 때 최대 한 번, 두 번, 세 번, 네 번까지 가겠죠. 못 찾으면요. 최악의 경우를 고려했을 때 맨 끝에 있다면 4번이겠죠.

사실 이 4번은 log2(N + 1)이고, 즉 이 트리의 높이는 log2(15 + 1) - 1가 돼서 3이 됩니다.

근데 이것은 균형잡힌 트리인 경우를 본 겁니다.

만약에 수가 여기있다면 어떻게 될까요? 한 번만에 찾겠죠.

근데 이걸 최악으로 고려했을 때, 수가 초록색 부분에 있을 때 고려를 해보면 전체 탐색을 안 하니까 이 높이 + 1만큼 들어가게 된다는 겁니다. 그리고 그 높이는 log2(N + 1) - 1 이라는 거죠.

근데 여러분 이게 삽입순서가 되게 중요해요. 이진탐색트리를 만든다 라고 해볼게요. 1, 2, 3 삽입이 되면 이렇게 돼버려요.

이진탐색트리인 건 당연하죠. 왼쪽이 작은 거, 오른쪽이 큰 거니까. 그런데 아주 단순하게 이진탐색트리를 만들었지만 이거는 선형적이에요.

직선적인 모양이 라는 게 선형적이고 비선형적이다 라는 건 직선이 아닌,

이런 꼴이 비선형적이라고 합니다. 여러분 이렇게 선형적이게 되어버리면 어떻게 돼요?

만약 이렇게 1, 2, 3, 4, 5 넣었을 때 내가 1을 찾고 싶어서 5부터 탐색을 시작하게 되면, O(logN)이 아니라, O(N)의 시간 복잡도가 걸려버리는 거예요.

그래서 이런 모양을 피해야 되겠죠. 그래서 이진 탐색트리를 생각할 때

보통은 이러한 균형적인 트리를 생각하지만 최악의 경우를 고렸을 때,

이런 트리가 완성될 수가 있어요.

그래서 이진탐색 트리라는 특징을 가지면서 삽입 순서에 따라서 linear 하게 되어버리면, 시간 복잡도가 커지는 걸 확인했기 때문에 삽입순서가 어떻게 되든 트리의 노드들을 회전시키는 등의 방법을 통해서 "균형잡히게 만듭니다."

linear 한 거는 균형잡히지 않았으니까 무조건 삽입 순서가 뭐가 어떻게 됐든, 무조건 이진탐색 트리인데 이거를 균형 잡게 만들어 버리는 게 바로 AVL 트리와 레드블랙 트리가 있습니다.

그리고 참고로 map이라는 자료구조는 삽입, 탐색, 삭제, 수정의 시간 복잡도가 모두 O(logN)임을 보장받아요. 그 이유가 균형 잡힌 트리인 레드 블랙 트리를 기반으로 구현이 되어있기 때문이에요.

지금 보시는 것처럼 AVL 트리가 이런 식으로 서브 트리를 rotate 해가지고 이렇게 삽입 순서에 영향을 받지 않게끔 하면서, 균형 잡히게 높이 차이가 1인 거를 유지하는 걸 볼 수가 있죠.

다시 정리하자면 다음과 같습니다.

이진트리는 뭐다? 자식 노드의 수가 2개 이하인 트리이다. 균형이진트리 만큼은 꼭 외워주시는 게 좋구요.

BST(이진탐색트리)는 왼쪽은 작은 거, 오른쪽은 큰 거. 근데 이제 이게 삽입 순서에 따라서 linear 하게 될 수가 있는데 이거를 균형 잡히게 만든 게 AVL 트리와 레드블랙 트리가 있다.

그리고 map이라는 자료구조가 보통 시간 복잡도가 O(logN)임을 보장받는데, 그 이유는 균형 잡힌 트리인 레드블랙 트리를 기반으로 하기 때문이다 라는 겁니다.