[자료구조] 이진탐색트리 (Binary Search Tree)

■ 이진 탐색 (Binary Search)

우리가 보통 벡터나 연결리스트를 활용하여 원하는 요소가 있는지 찾기 위해 순회를 할 경우 O(n)의 시간 복잡도를 갖고 전체를 둘러봐야한다. 하지만 정렬이 되어있는 상태라면 이렇게 할 필요 없이 이진 탐색을 해주면 된다.

 

이진 탐색이란 중간 요소를 기점으로 탐색할 값이 해당 요소보다 클 경우 우측을, 작을 경우 좌측을 탐색해주는 것인데 이를 찾을 때까지 [or 탐색 대상이 하나로 줄어들 때까지] 무한 반복 해주는 것이다. 

 

반씩 쪼개서 탐색하므로 O(logN)의 시간 복잡도를 갖고 있으며 이는 일반적으로 전체를 순회하는 O(n)보다 좋은 성능을 의미한다.

 

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

[이론]

이진탐색트리는 이진트리의 구조를 띄고 있다. 

* 이진트리 (Binary Tree) : 각 노드당 최대 2개의 자식을 갖는 트리.

 

이를 기반으로 이진탐색트리의 부모 노드들은 자신을 기준으로 좌측은 본인보다 작은 노드를, 우측에는 큰 노드를 갖도록 되어있다. 이와 같이 처음부터 정렬 되어있다면 이진탐색을 할 때 어느 곳으로 가야할지 방향이 정해져있게 된다. 

 

여기서 아래와 같이 궁금한 점이 생겼다.

[왜 벡터와 같은 선형구조가 아니라 트리 구조를 갖는가?]

이와 같은 상황에서 트리의 특성이 가져다 주는 여러 가지 장점이 있어서이다.

 

(1) 삽입 및 삭제 효율성

 벡터나 배열과 달리 이진 탐색 트리는 데이터를 삽입하거나 삭제할 때도 정렬된 상태를 유지하며 그 과정에서 '이사 비용'이 발생하지 않는다. 삽입 및 삭제는 일반적으로 O(logN)의 시간 복잡도를 가진다. 그 이유는 내부적으로 삽입 및 삭제 후 정렬을 하게 되어있는데 트리의 높이(logN)만큼 실행되기 때문이다.

 

(2) 메모리

 벡터나 배열과 달리 공간을 연속적으로 할당하지 않으며, 필요에 따라 동적으로 노드를 할당하므로 메모리의 낭비가 적다.

 

※ 물론 이러한 구조로 인하여 연결리스트(List, C#의 LinkedList)와 같이 임의 접근이 불가능하다는 단점이 있다.

그러므로 적재적소에 맞게 합리적인 컨테이너 타입을 골라 사용하는 능력을 배양하도록 노력해야겠다.

 

[Schema]

BST를 구성하는 클래스 및 요소는 아래와 같다.

코드 습관이 위와 같이 최대한 동일한 여백을 주도록 바뀌고 있다.

 

[삽입]

(1) 루트 노드가 비어있을 경우 루트 노드로 삽입한다.

(2) 추가할 위치를 찾을 때 까지 루트 노드의 자식들과 대소 관계를 반복 비교한다

[삭제]

(1) 자식이 한 개이거나 없을 경우 자식[or nullptr]과 자리를 변경해준 뒤 노드를 삭제해준다.

(2) 자식이 양쪽에 다 있을 경우 본인보다 바로 큰 숫자를 찾아 복사 및 현재 노드 위치에 대입해준 뒤 복사 대상의 노드를 제거해준다. 

이에 사용되는 Next, Replace 함수는 아래와 같다.

Next

Replace

 

 

[Next 함수]

(1) 삭제 대상 노드의 오른쪽 자식이 있을 경우 본인보다 가장 바로 큰 값이 현재 위치에 와야하므로 우측 자식의 맨 좌측 하단 자식을 가져와 복사 및 대입한다.

위에선 6이 제거 대상

복사 및 대입

제거 후 트리의 모습

 

(2) 삭제 외에 일반적으로 Next함수만 사용했을 때를 생각해보자. 그 다음 반환 요소를 가져와야 하는데 Next 대상의 노드가 부모가 있고 부모의 오른쪽 자손이라면?

 

부모가 존재하고 노드가 그 부모의 오른쪽 자손일 경우 무한 반복으로 

노드에 부모를 대입하고 부모를 부모의 부모를 대입해준다.

그러다가 노드가 부모의 좌측 노드인 상태가 되어버리면 그때 while반복문을 break한 뒤 부모를 반환해주면 된다.

[Search, Min, Max 함수]

 

[치명적인 단점]

하지만 늘 그렇듯 새로운 자료구조가 나오는 것은 해당 자료구조의 단점이 있다는 것이다.

이진탐색트리의 치명적 단점은 '비균형성(Off Balance)'이다. 위와 같이 삽입 및 삭제를 반복하다보면 아래와 같이 선형적으로 한쪽으로 쏠리는 경우가 생길 수 있는데 이렇게 된다면 우리가 힘들게 만든 BST가 연결리스트(List)와 다를 바가 없어진다.

[보완]

BST의 장점인 빠른 이진탐색을 이용 못하게 되는 것이므로 이를 보완하고자 여기서 더 나아가 트리의 균형을 맞춰주며 정렬을 수행하는 레드 블랙 트리 (Red-Black Tree)가 생겨났다.