지침
이진 트리에 숫자를 삽입하고 검색해요.
정렬된 데이터를 표현해야 할 때, 배열은 좋은 자료 구조가 아니에요.
배열 [1, 3, 4, 5]가 있다고 해봐요. 여기에 2를 추가하면 [1, 3, 4, 5, 2]가 돼요.
그러면 배열 전체를 처음부터 다시 정렬해야 해요!
새 항목을 넣을 자리만 마련한 뒤 [1, nil, 3, 4, 5]처럼 그 자리에 항목을 추가하면 조금 더 나아질 수 있어요.
하지만 이 방법도 많은 원소를 한 칸씩 뒤로 옮겨야 해요.
반면 이진 탐색 트리는 정렬된 데이터를 훨씬 효율적으로 다룰 수 있어요.
이진 탐색 트리는 서로 연결된 노드들로 이루어져 있어요.
각 노드는 데이터 조각(예를 들어 숫자 3), left라는 변수, right라는 변수를 담고 있어요.
left와 right 변수는 nil이나 다른 노드를 가리켜요.
이 다른 노드들도 그 아래에 또 다른 노드들을 가지고 있기 때문에, left와 right 변수가 서브트리를 가리킨다고 해요.
왼쪽 서브트리에 있는 모든 데이터는 현재 노드의 데이터보다 작거나 같고, 오른쪽 서브트리에 있는 모든 데이터는 현재 노드의 데이터보다 커요.
예를 들어, 데이터 4를 담은 노드가 있고 여기에 데이터 2를 추가하면 트리는 이렇게 돼요:
4
/
2
여기에 6을 추가하면 이렇게 돼요:
4
/ \
2 6
여기에 3을 추가하면 이렇게 돼요
4
/ \
2 6
\
3
그리고 여기에 1, 5, 7을 추가하면 이렇게 돼요
4
/ \
/ \
2 6
/ \ / \
1 3 5 7
출처
이미지는 habere-et-dispertire가 Till Tantau의 PGF/TikZ를 사용해 만들었어요.
구현
Cairo(또는 불변 메모리를 사용하는 모든 순수 함수형 언어)에서 효율적이고 수정 가능한 트리 구조를 구현하는 것은 어려워요. 이런 언어들은 데이터가 한 번 만들어지면 바뀌지 않도록 설계되어 있기 때문이에요.
이러한 불변성 때문에 트리 노드를 직접 갱신하는 대신, 수정할 때마다 트리의 새로운 버전을 만들어야 해요.
왜 그런지 보여드리기 위해, 각 노드가 왼쪽 자식과 오른쪽 자식을 가지는 간단한 이진 트리 구조를 상상해 봐요.
다음과 같은 작은 트리에서 시작한다고 해봐요:
1
/ \
2 3
이제 노드 2의 왼쪽 자식으로 새 노드 4를 추가하고 싶다고 해봐요.
Cairo나 Haskell 같은 순수 함수형 언어에서는 메모리가 불변이기 때문에, 노드 4를 2에 그냥 붙일 수는 없어요.
대신 루트에서 수정된 노드까지의 경로에 있는 각 노드의 새 버전을 만들어야 해요. 이 경로에 있는 모든 노드가 이제 새롭거나 수정된 서브트리를 가리키게 되기 때문이에요.
그 과정은 다음과 같아요:
-
노드 2에 노드 4 추가하기:
- 이제
4를 왼쪽 자식으로 가지는 노드 2의 새 버전을 만들어요.
2'
/
4
-
루트 노드 갱신하기:
- 노드
1은 원래 예전 2를 가리켰으므로, 왼쪽에는 갱신된 노드 2'를 가리키고 오른쪽에는 노드 3을 그대로 두는 루트 노드 1'의 새 버전을 만들어요.
1'
/ \
2' 3
그래서 결과 트리는 다음과 같아요:
1'
/ \
2' 3
/
4
이 새 트리(1')는 갱신된 경로를 가진다는 점만 빼면 원래 트리와 비슷해요.
핵심은 불변성을 유지하기 위해 경로(1에서 2까지)에 있는 각 노드를 다시 만들어야 한다는 점이에요. 기존 노드는 제자리에서 수정할 수 없기 때문이에요.
원래 트리는 여전히 존재하고(예를 들어 원래 루트 1을 가리키는 모든 참조에서), 이 새 트리는 수정된 상태를 나타내요.
큰 트리에서는 이 방식의 비용이 커질 수 있어요. 트리에서 실제로 바뀌는 부분이 아주 작더라도, 수정할 때마다 루트에서 갱신된 노드까지의 노드 경로를 다시 만들어야 하기 때문이에요.
출처
Josh Cheek
