데이터를 특정 순서대로 정렬하고 싶을 때 '퀵 정렬'을 사용할 수 있다. 하지만 정렬 알고리즘은 아무리 빨라도 O(NlogN) 시간이 걸린다. 따라서 데이터를 자주 정렬해야 한다면 다시 정렬하는 일이 없게 처음부터 데이터를 항상 정렬된 순서로 유지하는 편이 낫다.
정렬된 배열은 순서대로 데이터를 유지하는 효과적인 도구다. 또 특정 연산에 매우 빨라서 읽기에는 O(1), 검색(이진 검색을 사용할 때)에는 O(logN)이 걸린다.
그러나 정렬된 배열도 한계는 있다.
정렬된 배열은 삽입과 삭제가 상대적으로 느리다. 삽입과 삭제 시 값들을 전부 한 셀씩 오른쪽, 왼쪽으로 시프트 해야 하기 때문이다. 최악의 시나리오일 경우 N단계 걸리고, 평균적으로 N / 2단계가 걸린다.
전반적으로 빠른 속도를 내는 자료구조를 원하면 '해시 테이블'이 좋다. 해시 테이블은 검색, 삽입, 삭제가 O(1)이다. 하지만 순서를 유지하지 못하므로 정렬하는 프로그램에는 적절치 않다.
정렬된 배열도, 해시 테이블도 모두 문제가 있다.
그렇다면, 순서를 유지하고 빠른 검색, 삽입, 삭제가 가능한 자료구조는 어떻게 구현할 수 있을까?
'이진 탐색 트리'를 알아보자.
14. 1 트리
전형적인 '연결 리스트'는 각 노드마다 그 노드와 다른 한 노드를 연결하는 링크를 포함한다.
'트리(tree)' 역시 노드 기반 자료구조이다. 하자만 트리의 각 노드는 "여러" 노드로의 링크를 포함할 수 있다.
각 노드에는 다른 두 노드로 이어지는 링크가 있다. 메모리 주소를 표시하지 않고도 간결하게 트리를 표현할 수 있다.
- 가장 상위 노드를 '루트(root)'라고 한다. 루트는 트리의 꼭대기다. (위 예제에선 "j"다)
- "j"는 "m"과 "b"의 '부모(parent)'다. 반대로 "m"과 "b"는 "j"의 자식이다.
- 패밀리 트리에는 노드에 '자손(descendant)'와 '조상(ancestor)'이 있을 수 있다. 한 노드의 자손은 그 노드에서 생겨난 모든 노드이며, 한 노드의 조상은 그 노드를 생겨나게 한 모든 노드다. "j"는 트리 내 나머지 노드의 조상이고, 나머지 모든 노드는 "j"의 자손이 된다.
- 트리에는 '레벨(level)'이 있다. 각 레벨은 트리에서 같은 줄(row)이다. 예제는 세 레벨이다.
- 트리의 '프로퍼티(property)'는 균형 잡힌 정도이다. 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 '균형 트리'다.
14. 2 이진 탐색 트리
'이진 탐색 트리(binary search tree)'는 다양한 트리 기반 자료 구조 중 하나이다.
이진 탐색 트리의 각 노드엔 자식이 0, 1, 2개 있다.
추가된 규칙이 있다.
- 각 노드의 자식은 최대 "왼쪽"에 하나, "오른쪽"에 하나다.
- 한 노드의 "왼쪽" 자손은 그 노드보다 작은 값만 포함할 수 있다. 마찬가지로 "오른쪽" 자손은 그 노드보다 큰 값만 포함할 수 있다.
각 노드마다 그 노드보다 작은 값, 큰 값을 가지는 자식을 하나씩 가진다. (왼쪽은 작은 값, 오른쪽은 큰 값)
50의 왼쪽 자손은 전부 50보다 작다. 50의 오른쪽 자손 역시 모두 50보다 크다. 모든 노드에서 같은 패턴이 반복된다.
위 트리는 노드에 자식이 0, 1, 2개니 '이진 트리'다. 하지만 루트 노드 왼쪽에 자식만 둘이니 '이진 탐색 트리'가 아니다.
이진 탐색 트리로서 유효하려면 최대 왼쪽 자신 하나(더 작은), 오른쪽 자식 하나(더 큰)만 있어야 한다.
14. 3 검색
이진 탐색 트리에서 검색하는 알고리즘은 다음과 같다.
(1) 노드를 "현재 노드"로 지정한다. (알고리즘을 시작할 때는 루트 노드가 첫 번째 "현재 노드"다)
(2) 현재 노드의 값을 확인한다. (찾고 있는 값이면 좋다!!)
(3) 찾고 있는 값이 현재 노드보다 작으면, 왼쪽 하위 트리를 검색한다.
(4) 찾고 있는 값이 현재 노드보다 크면, 오른쪽 하위 트리를 검색한다.
(5) 찾고 있는 값을 찾았거나 트리 바닥에 닿을 때까지(찾고 있는 값이 트리에 없는 경우) 1단계부터 5단계를 반복한다.
만약 61을 검색한다면 어떻게 될까?
처음엔 루트부터 시작한다. 다음으로 컴퓨터는 스스로에게 묻는다. 검색하고 있는 수(61)가 이 노드의 값보다 큰가 작은가? 위 예제에서 61은 50보다 크므로 오른쪽 어딘가에 있음을 알 수 있고, 따라서 오른쪽 자식을 검색한다.
75는 찾고 있는 61이 아니므로 다음 레벨로 내려간다. 61은 75보다 작으므로 왼쪽 자식을 검사한다.
그렇게 한 단계씩 내려다가 원하는 값을 찾는 데 4단계가 걸렸다.
해당 검색 단계를 보면, 각 단계마다 검색할 대상이 남은 노드의 반으로 줄어든다. 루트의 오른쪽, 왼쪽을 정하는 순간 그 자식의 모든 자손은 검색에서 제외된다.
따라서 이진 탐색 트리의 '검색'은 각 단계마다 남은 값 중 반을 제거하는 모든 알고리즘을 나타내는 O(logN)이다.
이처럼 '이진 트리 검색'은 '정렬된 배열'의 이진 검색과 동일하다. 선택한 각 수가 가능한 남은 값 중 반을 제거한다. 이러한 면에서 두 검색의 효율성은 같다.
하지만 '삽입'에 있어서는 정렬된 배열보다 이진 트리가 훨씬 뛰어나다.
14. 4 삽입
앞서 사용한 트리에 숫자 45를 삽입해보자.
가장 먼저 해야 할 일은 45를 붙일 올바른 노드를 찾는 것이다. 검색은 항상 루트부터 시작한다.
45는 50보다 작으므로 왼쪽 자식으로 내려간다.
45는 25보다 크므로 오른쪽 자식을 검사해야 한다.
45는 33보다 크므로 오른쪽 자식을 확인한다.
더 이상 자식이 없는 노드이므로 갈 곳이 없다. 이제야 삽입할 준비가 됐다.
45는 40보다 크므로 40의 오른쪽 자식 노드로서 45를 삽입한다.
삽입에 총 5단계가 걸렸다. 검색 4단계와 삽입 1단계다. 삽입은 항상 검색에 한 단계 더 추가된다.
즉, 삽입은 (logN) + 1단계가 걸리며 빅 오는 상수를 무시하므로 O(logN)이다.
반면 정렬된 배열에서는 검색뿐만 아니라 값을 삽입할 공간을 마련하기 위해 많은 데이터를 오른쪽으로 시프트 해야 하기 때문에 삽입에 O(N)이 걸린다.
정렬된 배열은 검색에 O(logN), 삽입에 O(N)이 걸리지만, 이진 트리는 검색과 삽입 모드 O(logN)이다. 따라서 이진 탐색 트리가 더 효율적이다.
14. 5 삭제
이진 탐색 트리에서 '삭제'는 가장 어려운 연산이다.
4를 삭제해보자.
먼저 4를 찾는 검색을 수행한다. 4를 찾았으면 한 단계로 4를 삭제한다.
간단하게 삭제했다.
그리고 10을 삭제하면 11이 10의 자리를 대체한다.
중요한 삭제 알고리즘 규칙이 나왔다.
- 삭제할 노드에 자식이 없으면 그냥 삭제한다.
- 삭제할 노드에 자식이 '하나'면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 위치에 넣는다.
그렇다면 자식이 둘인 노드를 삭제해보자.
다음 트리에서 56을 삭제하고 싶다.
56을 삭제하면 52와 61을 어떻게 처리해야 할까? 여기서 세 번째 삭제 알고리즘 규칙이 적용될 차례다.
- 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 '후속자(successor)' 노드로 대체한다. 후속자 노드란, 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
즉, 삭제된 노드의 자식들 중 해당 노드보다 크면서 가장 가까운 값을 가진 노드가 후속자가 되는 것이다.
컴퓨터는 삭제된 값의 오른쪽 자식을 방문해서 그 자식의 왼쪽 자식을 따라 계속해서 방문하며 더 이상 왼쪽 자식이 없을 때까지 내려간다. 그리고 그 바닥(bottom) 값을 후속자 노드로 판단한다.
예시로 루트 노드를 삭제해 보자.
이제 50이 있던 위치에 후속자 노드를 넣어야 한다.
후속자 노드를 찾기 위해선, 먼저 삭제한 노드의 오른쪽 자식을 방문한 후, 왼쪽 자식이 없는 노드가 나올 때까지 왼쪽 방향으로 계속 내려가야 한다.
후속자 노드는 52였다. 이제 52를 삭제된 노드에 넣으면 삭제는 완료된다.
만약에 후속자 노드의 오른쪽 자식이 있다면 바로 위 부모 노드의 왼쪽 자식에 넣는다.
모든 단계를 종합하면 이진 탐색 트리의 삭제 알고리즘은 다음과 같다.
-- 삭제할 노드에 자식이 없으면 그냥 삭제한다.
-- 삭제할 노드에 자식이 "하나"면 노드를 삭제하고 자식을 삭제된 노드가 있던 위치에 넣는다.
-- 삭제할 노드에 자식이 "둘"이면 삭제된 노드를 '후속자 노드'로 대체한다. 후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
-- 만약 후속자 노드에 오른쪽 자식이 있으면 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
이진 탐색 트리의 삭제도 일반적으로 O(logN)이다.
14. 6 이진 탐색 트리 다뤄보기
이진 탐색 트리는 검색, 삽입, 삭제에서 O(logN)의 효율성을 자랑하므로 정렬된 데이터를 저장하고 조작해야 하는 시나리오에서 효율적이다.
예를 들어 책 제목 리스트를 관리하는 도서관 애플리케이션을 만든다고 생각해 보자. 리스트에 제목이 수백만 개라면 이진 탐색 트리를 사용하는 게 좋다.
알파벳 순으로 제목이 놓여 있어 알파벳 순서상 앞에 나오는 제목은 "더 작은" 값, 뒤에 나오는 제목은 "더 큰" 값으로 간주한다.
14. 7 이진 탐색 트리 순회
이진 탐색 트리에서 전체 값을 출력하고 싶다면 어떻게 해야 할까?
먼저, 트리의 노드를 모두 빠짐없이 접근해야 한다. 자료 구조에서 모든 노드를 방문하는 과정을 자료 구조 '순회(traversal)'라고 한다.
만약 리스트를 순서대로 출력하려면 '중위 순회(inorder traversal)'을 이용할 수 있다. 중위 순회는 재귀를 사용한다. 먼저 왼쪽 자식의 끝에 도달할 때까지 재귀적으로 함수를 호출하고, 값을 읽은 다음 오른쪽 자식도 마찬가지로 쓴다.
14. 8 마무리
이진 탐색 트리는 정렬 순서를 유지하는 강력한 노드 기반 자료 구조이자, 빠른 검색과 삽입, 삭제도 제공한다.
하지만 이진 탐색 트리는 트리 종류 중 하나일 뿐이다. 다양한 트리가 많이 있다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| Ch.16 트라이(trie)해 보는 것도 나쁘지 않다 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.13 |
|---|---|
| Ch.15 힙으로 우선순위 유지하기 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.11 |
| Ch.13 노드 기반 자료 구조 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
| Ch.12 속도를 높이는 재귀 알고리즘 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
| Ch.11 재귀적으로 작성하는 법 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.07 |
