안녕하세요.

오늘은 이진 탐색트리 에 대해 포스팅 합니다.

이진 탐색트리 란

이진 탐색트리 는 이진 탐색(Binary Search)의 아이디어를 채용한 자료구조 입니다.

이진 탐색은 원소가 정렬되어 있다는 조건아래, 정렬된 특징을 이용해 반씩 쪼개가며 검색을 합니다.

그러므로, 검색 횟수가 획기적으로 낮아지는 특징이 있습니다.

이는, 이진 탐색트리도 똑같이 원소가 정렬된 형태로 지니고 있어야 하고 반씩 쪼개가며 검색을 할 수 있는 구조를 갖추고 있어야 함을 의미합니다.

그러면... 이진 탐색 사용하면 되는거 아닌가요?

그렇다면, 이진 탐색트리는 이진 탐색을 사용하는 배열 자료구조보다 나은점이 무엇일까요?

아시다 시피, 배열은 조회에 강점이 있는 자료구조 입니다. 그렇다 보니, 검색만 한다고 가정할 때는 트리 구조가 굳이 필요하지 않습니다.

하지만, 원소가 삽입/삭제 될 수 있다고 가정하면 어떨까요? 배열 자료구조는, 삽입/삭제 될 Index 를 찾은 후, 그 Index 뒤에 위차한 원소들을 한칸씩 전부 뒤로 이동해야 하는 수고가 존재합니다. 또한, 배열공간이 모자라, 배열 크기를 증가시키거나 혹은 공간이 너무 남아, 축소 시키는 작업은 덤으로 발생할 수 있습니다.

그에 반면에, 트리 구조는 참조(포인터)만 변경해주면 되므로, 원소의 대량 이동이 필요 없고, 공간 복잡도를 신경안써도 되는 장점이 있습니다. 그렇다보니, 삽입/삭제 연산이 한번이라도 존재한다면, 이는 삽입이 연속적으로 N번 발생할 수도 있다는 의미이므로 굳이 배열 자료구조를 사용할 필요가 없습니다.

사실 조회 자체도 이진 탐색 구조상 트리 도 특정 노드의 Index 검색이 아닌, 특정 노드로부터 순차대로 검색하는 구조이므로 배열이랑 크게 차이가 없습니다.

예를들어, 연결 리스트는 특정 Index 노드 검색 시간복잡도는 O(n)이지만, 전체 순회를 할 때는 각 노드의 참조값을 순차대로 탐색하므로 각 노드의 검색 시간이 O(1) 입니다.

결론적으론, 이진 탐색트리가 더 보편적으로 사용될 수 있다고 말할 수 있겠습니다.

이진탐색을 위한 트리 구조

이진 탐색트리 는 트리에 어떤식으로 데이터의 구조를 형성하길래, 이진 탐색이 가능한걸까요?

아래와 규칙으로 데이터를 쌓기 때문입니다!

규칙만 봐서는 이해가 어렵습니다. 아래의 예시 이미지와, 삽입과정 설명을 보시는걸 추천합니다!

• 루트 노드가 비었다면, 삽입 노드를 루트 노드로 채웁니다.

• 루트 노드가 존재한다고 가정할 때, 삽입 노드의 값과 비교하여 삽입 노드의 값이 작으면 루트 노드의 오른쪽, 크면 오른쪽으로 이동합니다.

• 이동시, 노드가 비었다면 삽입 노드로 채웁니다.

• 만약 노드가 존재한다면, 2번~3번 과정을 반복합니다.

이진 탐색트리 순회

이진 트리는 대표적인 DFS 순회방법 3가지가 있습니다.

• 전위 순회(pre-order traversal)

• 중위 순회(in-order traversal)

• 후위 순회(post-order traversal)

이때, 중위 순회를 이용하면 정렬된 원소의 목록을 획득 할 수 있습니다.

위 예시를 중위 순회를 해보면 다음과 같은 원소의 목록을 얻을 수 있습니다.

1 > 2 > 3 > 4 > 5 > 7 > 9

따라서, 해당 트리 구조는 트리 정렬 알고리즘 으로도 사용되며,

이진 탐색트리를 제공하는 프로그래밍 API 에서는 정렬을 이용한 기능을 제공하는 경우가 많습니다.

ex) Java Collection API: TreeMap, TreeSet 은 이진 탐색 트리 구조로 트리를 쌓습니다. 따라서 특정 값들이 정렬로 보관되어 있고, 정렬특징을 이용하는 메서드들이 존재합니다.

이진 탐색트리 검색

예시의 이진 탐색트리 에서 4 노드를 검색한다고 가정해봅시다.

• 첫번째로 만나는 노드는 5 입니다. 검색노드가 5 보다 작으므로, 왼쪽으로 이동합니다.

• 두번째로 만나는 노드는 3 입니다. 검색노드가 3 보다 크므로, 오른쪽으로 이동합니다.

• 세번째로 만나는 노드는 4 입니다. 검색노드와 일치 하므로 해당 노드를 리턴 합니다.

Q. 4 의 존재유무를 검색 해보는건 의미가 있을거 같은데, 어차피 똑같은 값인 노드를 리턴하는게 의미가 있을까요? A. 노드는 꼭 하나의 값을 가진 자료형이 아닙니다. 예를들어 아래의 노드의 자료형을 구성한다고 생각해봅시다. 이때 4 로 검색하면 아래의 노드가 리턴 되고 리턴된 노드에서 제공하는 정보를 활용할 수 있습니다.

{
  "name": "Mommoo",
  "job": "Developer",
  "value": 4
}

이진 탐색트리 삽입

이진 탐색트리 에 노드를 넣는 순서는 다음과 같다고 가정합니다.

5, 3, 1, 4, 7, 9, 2

위에서 설명한 규칙대로 삽입과정을 거칩니다.

검색과 마찬가지로 이동하며, 자리를 찾아 노드를 저장합니다.

이진 탐색트리 삭제

이진 탐색트리의 검색/삽입 연산과 달리 삭제는 조금 복잡합니다.

고려해야 할 케이스를 3개로 나눌 수 있습니다.

• 삭제할 노드가 말단 노드인 경우(자식노드가 없는 경우)

• 삭제할 노드의 자식 노드가 1개인 경우

• 삭제할 노드의 자식 노드가 2개인 경우

삭제할 노드가 말단 노드인 경우

해당 경우는 간단합니다. 삭제할 노드만 삭제해주면 됩니다.

아래의 예시는 2 노드를 지웁니다.

삭제할 노드의 자식 노드 1개인 경우

이 경우도 어렵지 않습니다. 삭제할 노드의 자식들의 트리 구조 규칙은 삭제할 노드의 조상으로 부모를 바꾸더라도 규칙이 깨지지 않기 때문입니다.

이래의 예시는 7 노드를 지웁니다.

삭제할 노드의 자식 노드가 2개인 경우

이 경우가 살짝 복잡합니다. 삭제할 노드의 자리에 대신 채울 노드를 찾아야 하는 과정이 필요합니다.

대신 채울 노드를 찾는 방법은 2가지 존재합니다.

• 삭제할 노드의 왼쪽 서브 트리에서 최대 값 노드

• 삭제할 노드의 오른쪽 서브 트리에서 최소 값 노드

아래의 예시는 20 노드를 삭제할 때, 서브 트리에서 위 방법으로, 노드를 찾아 대체합니다.

이진 탐색트리 시간 복잡도

검색/삽입 시간복잡도

위에서 검색/삽입 연산을 살펴보시면 아시겠지만, 모든 원소를 탐색하지 않는것이 특징입니다.

최악의 경우는 트리의 높이 만큼 탐색하는 경우라 볼 수 있겠습니다.

따라서 높이가 H 인경우의 검색/삽입의 시간 복잡도는 O(H) 입니다.

하지만, 시간복잡도는 원소의 개수로 표기할 때, 조금 더 좋은 표현이라 할 수 있습니다.

H 를 원소의 개수 N 으로 표현해볼 수 없을까요?

이진 트리는 대개, 원소의 개수가 N 이면 $log_2N$ 으로 치환 가능합니다.

이진 검색트리 구조가 완전 이진 트리라 가정할 때의 경우로 한정적이긴 합니다. 그래서 최악의 경우로 규정짓는 빅오 표기법으로는 애매하긴 합니다.

따라서, 검색/삽입 연산의 시간복잡도는 $O(log_2N)$으로 표기 가능합니다.

삭제 시간복잡도

삭제 시간복잡도는 왜 따로 다룰까요?

검색/삽입과 동일하게 다룰 수 없는 찜찜한 구석이 있지 않았나요?

네 맞습니다. 삭제할 노드의 자식 노드가 2개인 경우 에는 추가 연산이 있기에 시간 복잡도를 다시 따져봐야 할거 같습니다.

검색 시간복잡도는 O(H) 로 삭제할 대상을 검색하는 것도 동일하게 시간이 소모됩니다.

이때, 삭제할 노드가 단말 노드, 삭제할 노드의 자식 노드가 1개 인 경우는 지우거나 참조값만 붙여주면 되므로, O(1) 의 시간이 소모된다고 볼 수 있습니다. 따라서 총 시간 복잡도는 O(H + 1) → O(H) 라 할 수 있겠네요.

그렇다면 우리가 궁금한 삭제할 노드의 자식 노드가 2개 인 경우는 어떨까요?

검색 후, 대체할 노드만 찾는다면 대체 노드의 참조값만 바꿔주면 되므로 O(1) 입니다.

그말은, 대체할 노드를 찾는게 얼마나 걸리는지에 따라 시간 복잡도가 규정 된다는 점입니다.

생각해보자면, 대체할 노드를 찾는것도 결국 탐색이 필요합니다. 다만 Full-Tree 가 아닌 Sub-Tree 에서의 검색이지요. 시간복잡도를 간단하게 정의해본다면 O(H-K) 정도가 될것입니다.

K 는 탐색을 시작할 높이 값입니다.

시간복잡도는 최악의 경우를 생각해야 하므로, 최악의 경우의 K는 0 이 되는 경우가 있겠네요.

이 경우는 루트를 지운다는 의미입니다.

결국 서브트리를 탐색하는 시간복잡도도 O(H) 라 생각할 수 있겠습니다.

정리해보자면, 아래의 작업이 필요합니다.

• 삭제 노드를 탐색 O(H)

• 대체 노드를 찾기 위한 서브 트리를 탐색 O(H)

• 참조값 변경 O(1)

따라서 삭제 연산의 시간 복잡도는 O(H + H + 1) → O(2H) → O(H) 라 볼 수 있습니다. 위에서 N으로 치환한것과 마찬가지로 $O(log_2N)$ 으로 표기 가능하겠습니다.

결론적으로 탐색/삽입/삭제 시간복잡도는 전부 동일하게 $O(log_2N)$ 라고 정의할 수 있습니다.

이진 탐색트리 사용시 고려할 점

중복값 처리 (주관적 의견. 뇌피셜 주의보!)

지금까지 보여드린 예시는 중복값이 없는 예시입니다. 이진 탐색트리 는 중복값을 허용하면 안된다는 자료가 많이 보이는거 같습니다.

현실적으로 중복값이 충분히 나올 수 있는지라, 중복값 비허용 규칙은 너무 잔인하다고 느꼈습니다.

제가 짧게 연구 해봤을때, 중복값을 노드의 왼쪽에 배치할 것인지, 오른쪽에 배치할 것인지만 정하고 배치하면 무리없이 동작합니다.

다만, 중요한것은 중복의 개수만큼 끝까지 내려간 후, 연결되어야 한다는 점입니다.

아래의 예시에서 왼쪽의 경우는 안됩니다. 트리 규칙이 깨지게 됩니다.

다만 중복의 개수가 많아지면, 트리의 높이가 너무 커지게 되고 시간복잡도가 비약적으로 올라가게 될것입니다.

그렇다보니, 다음과 같은 아이디어도 좋을거 같습니다.

• 단순히 값만 정의된 노드라면, 노드에 카운팅을 추가.

• 특정 자료형으로 정의된 노드라면, 해당 노드를 여러개 저장할 수 있는 자료구조를 감싼 wrapper 노드로 트리를 구성.

다만 추가 공간을 쓰게 되는 단점은 있는거 같습니다.

한쪽으로 쏠린 트리

이진 검색트리 의 시간복잡도는 $O(log_2N)$ 이라 소개드렸는데, 사실 최악의 경우는 O(N)이 나오게 됩니다.

Q. 빅오 표기법은 최악의 시간인 경우로 표기해야 하므로, 이진 탐색트리 의 연산 시간복잡도는 O(N) 아닐까요? A. 엄밀히 따지자면 O(N)이 맞습니다. 빅오표기법의 약점은 빈번도를 체크 하지 못합니다. 100번에 1번 나오는 경우의 수 때문에 최악의 경우로 시간을 규정하는게 제대로 된 측정값 일까요? 그렇기에 퀵소트도 $O(n^2)$ 이라 하지 않고, 대체적으로 측정되는 $O(Nlog_2N)$ 이라고 표기합니다.

간단한 예로, 정렬된 순서로 요소가 들어가게 된다면 아래와 같은 트리 구조로 구성되게 됩니다.

1, 2, 3, 4, 5

해당 구조는 트리 라기보다, 연결 리스트 의 구조로 잡혀있습니다.

높이가 낮을 수록 성능에 유리한 이진 검색트리가 이렇게 개수만큼 높이가 쌓이게 되면, 검색/삽입/삭제는 선형 연산이 되버립니다. 선형 연산이기 때문에 시간 복잡도는 O(N) 이 됩니다.

5를 찾으려면 5번 탐색 이 필요하네요.

균형 이진 탐색트리

이진 탐색트리 는 완전 이진트리 구조로 쌓여야, 요소 개수 N개의 대비 최소 높이가 됩니다.

그렇다면, 요소를 어떤 순서로 삽입 하더라도, 강제적으로 완전 이진트리 구조로 되게끔 규칙을 만들면 어떨까요!?

그러한 알고리즘을 추가한 이진 탐색트리 를 균형 이진 탐색트리 라 부르며, 대표적은 구현체는 AVL 트리 , 레드 블랙 트리 등이 있습니다.

오늘 포스팅은 여기까지 입니다.

뇌피셜인 부분도 있으니, 주의해서 읽어주셨으면 합니다.

읽어주셔서 감사합니다.