[c++] 알고리즘 개념공부 :: 탐색 - BST

BST

BST(Binary Search Tree)는 트리의 한 종류이자 이진탐색을 위한 방법 중 하나이다.

 

과정

BST를 이용한 탐색에서는 다음과 같은 과정을 거친다.

1. 이진 탐색 트리 만들기 (생성)
2. 루트 노드에서 내려가면서 원하는 요소 찾기 (탐색)
3. 삭제 및 삽입 하기 (삭제 / 삽입)

 

예시

먼저 이진 탐색 트리를 만들어보자.

 

 이진 탐색 트리는 부모 노드를 기준으로 왼쪽 서브트리에는 더 작은 값의 노드가 오른쪽 서브트리에는 더 큰 값의 노드가 있어야한다. 따라서 요소를 하나씩 삽입하면서 알맞은 위치를 찾아주면 된다.

결과적으로 나온 이진 탐색 트리를 중위 순회하면 정렬된 리스트가 된다.

 

 그 다음에는 루트 노드에서 내려가면서 원하는 요소를 찾고 삭제해보자. 원하는 요소는 6이다.

 

왼쪽 그림에서 오른쪽 그림으로의 과정을 거치면서 6을 찾아낸다.

 

그리고 6을 삭제한다.

 

연산

위에서 예시로 살펴봤듯 BST에는 탐색, 삽입, 삭제라는 3가지 주요한 연산이 존재한다.

주어진 리스트에서 9를 삽입하고 4, 2, 5를 삭제하는 과정을 보면서 각 상황에 따른 연산을 살펴보자.

 

탐색

(9 위치 탐색)

탐색 연산은 원하는 요소가 트리에 존재하는지, 존재한다면 어떤 위치에 있는지를 확인하는 연산이다. 루트 노드부터 시작하여 대소 관계에 따라 값을 확정짓거나 왼쪽이나 오른쪽 서브트리로 이동한다.

9는 확인한 위치(8 노드)의 오른쪽 자식으로 삽입되면 된다.

 

삽입

(9 삽입)

탐색 연산으로 확인한 위치에 요소를 삽입하는 연산이다. 해당 위치의 노드를 부모노드로 간주하고 포인터를 삽입하고자하는 노드의 주소로 할당해준다.

 

삭제

삭제 연산은 트리의 어떤 노드를 삭제할 것인지에 따라 복잡해질 수도 있다.

1. 삭제하려는 노드가 리프 노드일 경우

(4 삭제)

삭제하려는 노드가 리프 노드이면 자식 노드가 없으므로 단순 삭제해주면 된다. 삭제하고싶은 노드의 부모 노드를 찾아서 해당 노드의 주소가 저장되어있는 포인터 값을 초기화 시켜주면 된다.

2. 삭제하려는 노드가 하나의 서브 트리를 가진 경우

(2 삭제)

삭제하려는 노드가 한쪽에만 서브 트리가 있는 경우에는 해당 노드를 삭제하고 서브트리를 해당 노드의 부모 노드에 붙이면 된다. 부모 노드의 포인터에 저장된 해당 노드의 주소 값 대신 서브트리 루트 노드의 주소 값을 저장하면 되는 것이다.

3. 삭제하려는 노드가 2개의 서브 트리를 가진 경우

(5 삭제)

삭제하려는 노드가 두쪽 모두 서브 트리가 있는 경우에는 해당 노드의 선행자 또는 후계자 중 하나를 삭제할 노드의 위치로 가져온다.

선행자 / 후계자는 중위 탐색의 시점에서 해당 노드 바로 이전, 바로 이후에 있는 노드이다.

 

분석

그렇다면 처음에 말했듯 BST는 그냥 리스트를 이진 탐색하는 것과 비교해서 왜 삽입 / 삭제가 쉬울까?

 BST에서는 노드의 갯수(요소의 갯수)가 n이라고 할 때, 트리의 높이 h는 최소 lgn, 최대 n이다. 완전 이진 트리의 형태를 띄고 있을 때 lgn이 되고, 한 쪽으로 치우친 형태의 트리는 n의 높이까지 가질 수 있다.

 따라서 균형적으로 잘 생성된 BST의 탐색, 삽입, 삭제 연산은 최대 리프노드까지 내려가면서 진행되므로 모두 O(lgn)이다.

	BST	이진 탐색 (배열)
탐색	O(lgn)	O(lgn)
삽입	O(lgn)	O(n)
삭제	O(lgn)	O(n)

 

AVL 트리

 BST는 한쪽으로 치우친 트리로 만들어질 경우, 순차 탐색과 같은 효율을 내므로 트리를 잘 생성해야한다. 효율적인 BST를 생성하기 위한 방법들이 있다. 그 중 하나는 AVL 트리이다.

 

 AVL 트리는 Adelson-Velskii와 Landis가 1962년에 제안한 트리로, 모든 노드의 왼쪽 오른쪽 서브트리 높이 차(균형 인수)의 절댓값이 1이하인 이진 탐색 트리이다. 따라서 BST가 치우침 없이 만들어지므로 평균, 최선, 최악의 시간복잡도가 모두 O(lgn)다.

 

 AVL 트리는 삽입 삭제 연산 시 조건이 깨질 수도 있다. 따라서 기존 BST와 똑같이 연산을 수행하지만 조건을 회복하기 위해 회전을 사용한다. LL, RR, LR, RL 등의 회전을 사용하여 조건을 회복한다.

 

---

참고 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/