들어가며
2장 알고리즘이 중요한 까닭에서
이진 검색의 개념을 다루면서
정렬된 이진 검색을 사용하면
O(log N) 시간에 어떤 값이든
찾을 수 있음을 알았다.
결국 정렬된 배열에도 한 가지
문제가 있다.
정렬된 배열은 삽입과 삭제가
느리다.
정렬된 배열에 값을 삽입할
때마다
그 값보다 큰 모든 항목들을 한 셀
오른쪽으로 먼저 시프트 해야 한다.
또한, 정렬된 배열에서 값을
삭제할 때마다
그 값보다 큰 모든 값을 한 셀
왼쪽으로 시프트해야 한다.
최악의 시나리오*일 경우,
* 배열 앞에 값을 삽입하거나, 배열 첫 번째 값을 삭제할 때
시프트에 N단계가 걸리고,
평균적으로 N/2단계가 걸린다.
어쨌든 O(N)이고, O(N)은 꽤 느리다.
7장 해시 테이블로 매우 빠른 룩업에서
해시 테이블의 검색, 삽입, 삭제는
O(1)임을 배웠지만
해시 테이블에도 순서를 유지하지
못한다는 심각한 단점이 있다.
하지만 순서를 유지하면서도
빠른 검색과 삽입, 삭제가 가능한
자료 구조가 필요하면 어떨까.
정렬된 배열도, 해시 테이블도
완벽하지 않다.
이진 트리로 들어가 보자.
12.1. 이진 트리
11장에서는 연결 리스트라는
노드 기반 자료 구조를 소개했다.
단순 연결 리스트는 각 노드마다
그 노드와 다른 한 노드를 연결하는
링크를 포함한다.
트리 역시 노드 기반 자료구조이지만
트리의 각 노드는 여러 노드로의
링크를 포함할 수 있다.
다음은 간단히 트리를 그림으로
표현한 것이다.
예제의 각 노드에는 다른 두 노드로
이어지는 링크가 있다.
실제 링크를 모두 표시하지 않고도
간결하게 트리를 그림으로 표현할
수 있다.
트리에는 3가지 고유한 용어가 있다.
- 가장 상위 노드(예제에서 "a")를 루트(root)라고 한다. 보다시피 위 그림에서 루트는 트리의 꼭대기다.
- 예제에서 "a"를 "b"와 "c"의 부모라고 하고, 반대로 "a"의 자식이라고 한다. 그 하위 노드 관계에서도 마찬가지다.
- 트리에는 레벨(Level)이 있다. 예제의 트리는 세 레벨이다.
각각 첫 번째 레벨, 두 번째 레벨,
세 번째 레벨이다.
트리 기반 자료 구조는 종류가
다양하지만
12장에서는 이진 트리라 알려진
트리에 초점을 맞추겠다.
이진 트리는 다음의 규칙을
따르는 트리다.
- 각 노드의 자식은 0개나 1개 또는 2개이다.
- 한 노드에 자식이 둘이면, 한 자식을 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야 한다.
각 노드마다 그 노드보다
작은 값을 갖는 자식, 즉 왼쪽
화살표로 표시된 자식과
큰 값을 갖는 자식, 즉 오른쪽
화살표로 표시된 자식이 있다.
다음 예제는 트리이지만,
이진 트리는 아니다.
부모 노드의 두 자식 모두
부모보다 작은 값을 가지므로
유효한 이진 트리가 아니다.
하나의 트리 노드를 파이썬으로
구현하면 다음과 같다.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.value = val
self.leftChild = left
self.rightChild = right
이제 다음처럼 간단한 트리를
만들 수 있다.
node1 = TreeNode(1)
node2 = TreeNode(10)
root = TreeNode(5, node1, node2)
다음 절에서는 이진 트리의
고유한 구조 덕분에
어떤 값이든 매우 빠르게 찾을
수 있음을 보이겠다.
12.2. 검색
예제 이진 트리를 다시 보자.
이진 트리를 검색하는 알고리즘은
루트 노드부터 시작한다.
- 노드의 값을 확인한다.
- 현재 노드의 값이 찾고 있는 값이면 해당 노드를 반환한다.
- 찾고 있는 값이 현재 노드보다 작다면 왼쪽 하위 트리를 검색한다.
- 찾고 있는 값이 현재 노드보다 크다면 오른쪽 하위 트리를 검색한다.
위 검색을 파이썬으로 간단하게
재귀적으로 구현하면
다음과 같다.
def search(value, node):
# 기저 조건: 노드가 없거나 or 찾고 있는 값일 경우
if node is None or node.value == value:
return node
# 찾고 있는 값이 현재 노드보다 작다면
# 왼쪽 하위 트리를 검색한다.
elif value < node.value:
return search(value, node.leftChild)
# 찾고 있는 값이 현재 노드보다 크다면
# 오른쪽 하위 트리를 검색한다.
elif node.value < value:
return search(value, node.rightChild)
61을 검색해보자.
이 과정을 그림으로 따라가 보면서
얼마나 많은 단계가 걸리는지 알아보자.
트리 검색은 반드시 루트부터
시작해야 한다.
다음으로 컴퓨터는 판단한다.
검색하고 있는 수(61)와 현재
노드의 값과 대소비교를 한다.
찾고 있는 수가 현재 노드보다
작다면 왼쪽 자식에서 찾는다.
찾고 있는 수가 현재 노드보다
크다면 오른쪽 자식에서 찾는다.
위 예제에서 61은 50보다 크므로
오른쪽 어딘가에 있음을 알 수 있고,
따라서 오른쪽 자식을 검색한다.
현재 노드의 값이 찾고자 하는
수과 일치하는지 판단한다.
75는 찾고자 하는 수가 아니므로
다음 레벨로 내려가야 하며,
61은 75보다 작으므로
왼쪽 자식을 검사한다.
61은 56보다 크므로 56의
오른쪽 자식을 검사한다.
원하는 값을 찾는데 4단계가
걸렸다.
보다 일반적으로 말하면,
이진 트리 검색은 O(log N)이다.
각 단계를 수행할 때마다 값이
들어있을 남은 공간 중
절반을 제거하기 때문이다*.
* 물론 뒤이어 설명할 최선의 시나리오인 포화 균형 이진 트리에서만 그렇다.
또 다른 O(log N) 알고리즘인
이진 검색과 비교해보자.
이진 검색도 마찬가지로 각 수로
가능한 남은 값 중 반을 제거한다.
이러한 면에서 이진 트리 검색은
정렬된 배열의 이진 검색과
효율성이 같다.
하지만 정렬된 배열보다 이진 트리가
정말로 뛰어난 연산은 삽입이다.
12.3. 삽입
새 값을 이진 트리에 삽입하는
알고리즘을 공부하려면
예제로 봐야 한다.
앞서 사용한 트리에 숫자 45를
삽입해 보자.
첫 번째로 해야 할 일은 45를
붙일 올바른 노드를 찾는 것이다.
검색을 시작하려면 루트부터
시작한다.
45는 50보다 작으므로
왼쪽 자식으로 내려간다.
45는 25보다 크므로 25의
오른쪽 자식을 확인한다.
45는 33보다 크므로 33의
오른쪽 자식을 확인한다.
더 이상 자식이 없는 노드이므로
갈 곳이 없다.
즉, 삽입할 준비가 된다.
45는 40보다 크므로 40의 오른쪽
자식 노드로서 45를 삽입한다.
예제는 삽입에 5단계가 걸렸다.
검색 4단계와 삽입 1단계다.
삽입은 항상 검색에 한 단계
더 추가된다.
즉, 삽입은 'log N + 1'단계가
걸리며,
빅 오는 상수를 무시하므로,
O(log N)이다.
이와 대조적으로 정렬된 배열에서는
검색 뿐 아니라
값을 삽입할 공간을 마련하기 위해
많은 데이터를 오른쪽으로
시프트해야 하기 때문에
삽입에 O(N)이 걸린다.
그래서 이진 트리가 매우 효율적이다.
정렬된 배열은 검색에 O(log N),
삽입에 O(N)이 걸리는 반면,
이진 트리는 검색과 삽입 모두
O(log N)이다.
데이터를 많이 변경할 애플리케이션
이라면 특히 중요하다.
다음은 이진 트리에 값을 삽입하는
파이썬 구현이다.
search 함수와 같이, 재귀로 구현했다.
def insert(value, node):
if value < node.value:
# 왼쪽 자식이 없으면 왼쪽 자식으로서 값을 삽입한다.
if node.leftChild is None:
node.leftChild = TreeNode(value)
else:
insert(value, node.leftChild)
elif node.value < value:
# 오른쪽 자식이 없으면 오른쪽 자식으로서 값을 삽입한다.
if node.rightChild is None:
node.rightChild = TreeNode(value)
else:
insert(value, node.rightChild)
한 가지 알아둘 점은
무작위로 정렬된 데이터로
트리를 생성해야
대개 균형잡힌 트리가 생성된다는
점이다.
하지만 정렬된 데이터를 트리에
삽입하면
불균형이 심하고 덜 효율적일
수 있다.
예를 들어 데이터를 순서대로,
즉 1, 2, 3, 4, 5로 삽입하면 다음과
같은 트리가 생성될 것이다.
위 트리에서 5를 검색하는 데
O(N)이 걸린다.
하지만 같은 데이터를 3, 2, 4, 1, 5
순서로 삽입하면
균형잡힌 트리가 된다.
이러한 이유로 정렬된 배열을
이진 트리로 변환하고 싶을 때는
먼저 데이터 순서를 무작위로
만드는 것이 좋다.
살펴봤듯이 최악의 시나리오인
불균형이 심한 트리 검색은
O(N)이었다.
반면 최선의 시나리오인 완전히
균형잡힌 트리 검색은 O(log N)이다.
데이터를 무작위로 삽입한 일반적인
시나리오라면
균형이 꽤 잘 잡힌 트리일 것이고
검색에는 약 O(log N)이 걸릴 것이다.
12.4. 삭제
삭제는 이진 트리에서 가장 어려운
연산이며 주의 깊게 실행해야 한다.
다음 이진 트리에서 4를 제거해 보자.
먼저 4를 찾는 검색을 수행하고
이어서 한 단계로 4를 삭제한다.
여기까지는 간단했지만 10도
삭제하고 싶다고 하자.
다음과 같이 10을 삭제하면,
11이 트리와 연결이 끊긴다.
11을 영원히 잃게 되므로 이렇게
하면 안 된다.
하지만 10이 있던 자리에 11을
넣어 문제를 해결할 수 있다.
지금까지 배운 삭제 알고리즘은
다음과 같은 규칙을 따른다.
- 삭제할 노드에 자식이 없으면 그냥 삭제한다.
- 삭제할 노드에 자식이 하나면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 위치에 넣는다.
가장 복잡한 시나리오는 자식이
둘인 노드를 삭제하는 것이다.
56을 삭제하고 싶다고 가정하자.
52와 61을 어떻게 해야 할까?
둘 다 56이 있던 자리에 놓을
수는 없다.
세 번째 삭제 알고리즘 규칙을
적용할 차례다.
- 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다. 후속자 노드는 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
곧바로 이해하기가 힘든 문장이다.
다시 말하자면 후속자 노드란
삭제된 값 다음으로 큰 값이다.
예제에서 56의 자식들 중
56다음으로 큰 수는 61이다.
따라서 56을 61로 대체한다.
컴퓨터는 후속자 값을 어떻게
찾아낼까?
다음과 같은 알고리즘을 사용한다.
삭제된 값의 오른쪽 자식을 방문해서
그 자식의 왼쪽 자식을 따라
계속해서 방문하며 더 이상 왼쪽
자식이 없을 때까지 내려간다.
바닥 값이 후속자 노드다.
좀 더 복잡한 예로 실제 동작을
살펴보겠다.
루트 노드를 삭제해 보자.
이제 루트 노드에 후속자 값을
넣어야 한다.
후속자 값을 찾아보자.
이렇게 하려면 먼저 오른쪽 자식을
방문한 후*
* 삭제된 노드보다 더 큰 값들 중 가장 작은 값이 후속자이므로, 더 큰 값을 찾기 위해 오른쪽을 탐색한다.
왼쪽 자식이 없는 노드가 나올 때까지
왼쪽 방향으로 계속 내려가야 한다*.
* 삭제된 노드보다 더 큰 값들 중 가장 작은 값이 후속자이므로, 그들 중 최소값을 찾기 위해 계속 왼쪽을 탐색한다.
후속자 노드인 52를 찾았으므로
52를 삭제된 노드에 넣는다.
이제 끝났다.
하지만 아직 고려하지 않은 경우가
하나 있는데,
후속자 노드에 오른쪽 자식이
있을 때다.
예제 트리의 52에 오른쪽 자식을
추가해서 다시 생성해 보자.
이때 후속자 노드인 52를 그냥
루트에 넣으면
자식인 55가 연결이 끊어진다.
따라서 삭제 알고리즘에는
규칙이 하나 더 있다.
- 만약 후속자 노드에 오른쪽 자식이 있으면 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
단계별로 살펴보자
먼저 후속자 노드를 루트에 넣는다.
55가 끝어졌다.
다음으로 55를 후속자 노드의 원래
부모의 왼쪽 자식에 넣는다.
이때 61이 후속자 노드의 부모였으므로
55는 61의 왼쪽 자식이 된다.
이제 진짜 끝났다.
이 모든 단계를 종합하면 이진 트리의
삭제 알고리즘은 다음과 같다.
- 삭제할 노드에 자식이 없으면 그냥 삭제한다.
- 삭제할 노드에 자식이 하나면 노드를 삭제하고 자식을 삭제된 노드가 있던 위치에 넣는다.
- 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다.
후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
만약 후속자 노드에 오른쪽 자식이 있으면 후속자를 삭제된 노드가 있던 자리에 넣은 후,
후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
다음 파이썬 코드는 이진 트리 삭제를
재귀적으로 구현한 것이다.
처음에는 좀 어려우므로 주석을
많이 첨부했다.
def delete(valueToDelete, node):
# 기저 조건: 트리 밑바닥에 도달해서 부모 노드에 자식이 없는 경우
if node is None:
return None
# 삭제하려는 값이 현재 노드보다 작다면(크다면),
# 현재 노드의 왼쪽(오른쪽) 하위 트리에 대한 재귀 호출의 반환 값을
# 왼쪽(오른쪽) 자식에 할당한다.
elif valueToDelete < node.value:
node.leftChild = delete(valueToDelete, node.leftChild)
# 현재 노드(와 존재한다면 그 하위 트리)를 반환해서
# 현재 노드의 부모의 왼쪽(오른쪽) 자식의 새로운 값으로 쓰이게 한다.
return node
elif node.value < valueToDelete:
node.rightChild = delete(valueToDelete,node.rightChild)
return node
# 현재 노드가 삭제하려는 노드인 경우
elif valueToDelete == node.value:
# 현재 노드에 왼쪽 자식이 없으면,
# 오른쪽 자식(과 존재한다면 그 하위 트리)을 반환함으로써 삭제하고,
# 그 부모의 새 하위트리가 될 수 있도록 한다.
if node.leftChild is None:
return node.rightChild
# (현재 노드에 왼쪽 또는 오른쪽 자식이 없으면,
# 이 함수 코드 첫 줄에 따라 None으로 끝날 것이다.)
elif node.rightChild is None:
return node.leftChild
# 현재 노드에 자식이 둘이면,
# 현재 노드의 값을 후속자 노드의 값으로 바꾸는
# 아래 lift 함수를 호출함으로써 삭제한다.
else:
node.rightChild = lift(node.rightChild, node)
return node
def lift(node, nodeToDelete):
# 이 함수의 현재 노드에 왼쪽 자식이 있으면,
# 왼쪽 하위 트리로 계속 내려가도록 함수를 재귀적으로 호출함으로써
# 후속자 노드를 탐색한다.
if node.leftChild:
node.leftChild = lift(node.leftChild, nodeToDelete)
return node
# 현재 노드에 왼쪽 자식이 없으면,
# 이 함수의 현재 노드가 후속자 노드라는 뜻이므로
# 현재 노드의 값을 삭제하려는 노드의 새로운 값으로 할당한다.
else:
nodeToDelete.value = node.value
# 후속자 노드의 오른쪽 지식이 부모의 왼쪽 지식으로 쓰일 수 있도록 반환한다.
return node.rightChild
검색과 삽입처럼 트리 삭제도
일반적으로 O(log N)이다.
삭제에는 검색 한 번과 연결이
끊긴 자식을 처리하는 단계가
추가로 필요하기 때문이다.
O(N)이 걸리는 정렬된 배열 삭제와
대조적이다.
정렬된 배열에서 값을 삭제할
때는 삭제된 값의 빈 공간을
메우기 위해 원소를 왼쪽으로
시프트 해야 한다.
12.5. 이진 트리 다뤄보기
이진 트리는 검색과 삽입, 삭제에서
O(log N)의 효율성을 자랑하므로
정렬된 데이터를 저장하고 조작해야
하는 시나리오에서
효율적인 선택임을 알아봤다.
정렬된 배열을 데이터 검색이
이진 트리만큼 빠르지만
이진 트리는 데이터 삽입과
삭제가 훨씬 빠르므로
데이터를 자주 수정할 경우 특히
효율적이다.
예를 들어 책 제목 리스트를 관리하는
애플리케이션을 만든다고 하자.
애플리케이션에 다음과 같은 기능을
원한다.
- 프로그램은 책 제목을 알파벳순으로 출력할 수 있어야 한다.
- 프로그램은 리스트를 계속해서 바꿀 수 있어야 한다.
- 프로그램은 사용자가 리스트에서 제목을 검색할 수 있게 해야 한다.
책 리스트가 자주 바뀔 일이
없다면
데이터를 저장할 자료구조로서
정렬된 배열이 적절하다.
하지만 현재 만드는 앱은 실제로
많은 변경을 처리할 수 있어야 한다.
리스트에 제목이 수백만 개라면
이진 트리를 사용하는 것이 좋다.
(그림)
이진 트리에서 어떻게 데이터를
검색하고 삽입하고 삭제하는지
얘기한 바 있다. 어떻게 할 수 있는가?
먼저 트리의 노드를 모두 방문할
수 있어야 한다.
자료 구조에서 모든 노드를 방문하는
과정을 자료 구조 순회라 부른다.
둘째, 리스트를 순서대로 출력할
수 있도록
트리를 알파벳 오름차순으로
순회할 수 있어야 한다.
트리를 순회하는 방법은 여러
가지 인데,
이 애플리케이션에서는 각 제목을
알파벳 순으로 출력할 수 있도록
중위 순회라 알려진 방법을 수행하겠다.
재귀는 중위 순회를 수행하는
훌륭한 도구다.
노드에 호출할 traverse라는 재귀
함수를 생성하겠다.
함수는 다음과 같은 단계를 수행한다.
- 노드에 왼쪽 자식이 있으면, 그 자식에 traverse를 호출한다.
- 이제 노드를 방문한다(예제인 책 제목 앱에서는 이 단계에서 노드의 값을 출력한다).
- 노드에 오른쪽 자식이 있으면 그 자식에 traverse를 호출한다.
위 재귀 알고리즘에서 기저 조건은
노드에 자식이 없을 때다.
이때는 단순히 노드의 제목을 출력할
뿐 traverse를 다시 호출하지 않는다.
"Moby Dick" 노드에 traverse를
호출하면
다음 그림에서 보여지는 순서대로
트리의 모든 노드를 방문할 것이다.
(그림)
바로 이렇게 책 제목 리스트를
알파벳 순으로 출력할 수 있다.
정의에 따르면 순회는 트리의
모든 노드를 방문하므로
트리 순회는 O(N)이 걸린다.
다음은 책 제목 리스트를 처리하는
파이썬 traverse_and_print 함수다.
def traverse_and_print(node):
if node is None:
return
traverse_and_print(node.leftChild)
print(node.value)
traverse_and_print(node.rightChild)
12.6. 마무리
이진 트리는 정렬 순서를 유지하는
강력한 노드 기반 자료 구조이자
빠른 검색과 삽입, 삭제도 제공한다.
사촌격인 연결 리스트보다 복잡하지만
가치가 엄청나다.
이진 트리 외에 언급할 만한 다른
종류의 트리 기반 자료 구조도 많다.
힙과 B트리, 레드-블랙 트리, 2-3-4 트리를
비롯한 많은 트리가
각각 특수한 시나리오에서 자신만의
역할을 하고 있다.
13장에서는 소셜 네트워크와 매핑
소프트웨어 같은
복잡한 애플리케이션의 핵심 요소로
쓰이고 있는
또 다른 노드 기반 자료구조를 다룬다.
그래프라 불리는 이 자료 구조는
강력하면서도 빠르다.
참고 및 출처
 |
|
