[책] 누구나 자료구조와 알고리즘 - 15장 이진 탐색 트리로 속도 향상 (2/2) 삭제, 순회
누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고
누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거
product.kyobobook.co.kr
삭제
삭제는 이진 탐색 트리에서 가장 어려운 연산이기 때문에 주의 깊게 실행해야한다.
리프 노드(트리의 가장 끝 노드)를 삭제하게 되면 아무런 문제가 없다.
하지만 중간 노드를 삭제하게 되면 해당 서브트리의 노드의 재배치가 필요하다.
삭제 알고리즘의 규칙
- 삭제 할 노드에 자식이 없으면 그냥 삭제한다
- 삭제 할 노드에 자식이 하나면 노드를 삭제하고, 그 자식을 삭제된 노드가 있던 위치에 넣는다.
자식이 둘인 노드 삭제
- 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자(successor)노드로 대체한다.
- 후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
- 후속자 노드를 찾기 위해서는 삭제된 값의 오른쪽 자식을 방문해서 그 자식의 왼쪽 자식을 따라 계속해서 방문하며 더 이상 왼쪽 자식이 없을 때까지 내려간다. 바닥(bottom)값이 후속자 노드다.
- 삭제된 노드의 오른쪽 서브트리의 왼쪽 맨 아래 노드 (=리프노드)
오른쪽 자식이 있는 후속자 노드
- 만약, 후속자 노드에 오른쪽 자식이 있으면 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
- 삭제된 노드의 위치 -> 후속자 노드가 대체
- 후속자 노드의 위치 -> 후속자 노드의 오른쪽 자식이 대체
완전한 삭제 알고리즘
모든 단계를 종합해보면 이진 탐색 트리의 삭제 알고리즘은 다음과 같다.
- 삭제할 노드에 자식이 없으면 그냥 삭제한다.
- 삭제할 노드에 자식이 하나면 노드를 삭제하고 자식을 삭제된 노드가 있던 위치에 넣는다.
- 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다. 후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
- 후속자 노드를 찾으려면 삭제된 값의 오른쪽 자식을 방문해서 그 자식의 왼쪽 자식을 따라 계속해서 방문하며 더 이상 왼쪽 자식이 없을 때까지 내려간다. 바닥(bottom) 값이 후속자 노드다.
- 만약 후속자 노드에 오른쪽 자식이 있으면 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
코드 구현 - 삭제
# 파이썬
def delete(valueToDelete, node):
# 트리 바닥에 도달해서 부모 노드에 자식이 없으면 기저 조건이다.
if node is None:
return None
# 삭제하려는 값이 현재 노드보다 작거나 크면
# 현재 노드의 왼쪽 혹은 오른쪽 하위 트리에 대한 재귀 호출의 반환값을
# 각각 왼쪽 혹은 오른쪽 자식에 할당한다.
elif valueToeDelete < node.value:
node.leftChild = delete(valueToDelete, node.leftChild)
# 현재 노드(와 존재한다면 그 하위 트리)를 반환해서
# 현재 노드의 부모의 왼쪽 혹은 오른쪽 자식의 새로운 값으로 쓰이게 한다.
return node
elif valueToDelete > node.value:
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.rightChilddelete 함수가 하는 일
- 삭제 할 node를 찾는다.
lift 함수가 하는 일
- 삭제 할 node의 위치를 대체 할 후속자 node를 찾고, 대체한다.
- 후속자 node의 오른쪽 node가 후속자 node의 위치를 대체한다.
- 후속자 노드를 찾는다.
- nodeToDelete의 값을 후속자 노드의 값으로 덮어쓴다. 이렇게 후속자 노드를 올바른 위치에 넣는다. 실제 루속자 노드 객체를 어디론가 옮기는 것이 아니라 그 값을 "삭제 중인" 노드에 복사할 뿐이다.
- 실제 후속자 노드 객체를 삭제하기 위해 함수는 원래 후속자 노드의 오른쪽 자식을 후속자 노드 부모의 왼쪽 자식으로 넣는다.
- 재귀가 모두 끝나면 처음에 전달받은 원래 rightChild를 반환하거나 혹은 (원래 rightChild에 왼쪽 자식이 없어) 원래 rightChild가 후속자 노드가 됐으면 None을 반환한다.
이진 탐색 트리 삭제의 효율성
O(logN)이 걸린다.
배열에서의 삭제는 O(N)이 걸리는 것과는 대조적이다.
이진 탐색 트리 순회
이진 탐색 트리는 데이터 삽입과 삭제가 정렬된 배열보다 훨씬 빠르므로 데이터를 자주 수정할 경우 특히 효율적이다.
데이터를 순서대로 출력하고 싶을 때, 트리의 노드를 모두 빠짐없이 방문할 수 있어야 한다.
자료 구조에서 모든 노드를 방문하는 과정을 자료 구조 순회(traversal)라 부른다.
예시로, 전체 책 제목 리스트를 알파벳 순, 오름차순으로 출력하는데에 중위 순회(inorder traversal) 방법을 수행하겠다.
- 노드의 왼쪽 자식에 함수(traverse)를 재귀적으로 호출한다. 왼쪽 자식이 없는 노드에 닿을 때까지 함수를 계속 호출한다.
- 노드를 "방문"한다.(예제인 책 제목 앱에서는 이 단계에서 노드의 값을 출력한다.)
- 노드의 오른쪽 자식에 함수(traverse)를 재귀적으로 호출한다. 오른쪽 자식이 없는 노드에 닿을 때까지 함수를 계속 호출한다.
이 재귀 알고리즘의 기저 조건은 자식이 없는 노드에 tracerse를 호출할 때이며 단순히 return만 수행한다.
def traverse_and_print(node):
if node is None:
return
traverse_and_print(node.leftChild)
print(node.value)
traverse_and_print(node.rightChild)
마무리
이진 탐색 트리는 정렬 순서를 유지하는 강력한 노드 기반 자료 구조이다 빠른 검색과 삽입, 삭제도 제공한다. 사촌 격인 연결 리스트보다 복잡하지만 가치가 엄청나다.
하지만 이진 탐색 트리는 트리 종류 중 하나일 뿐이다. 다른 종류의 트리가 많고, 각각 특수한 상황에서 특유의 이점이 있다.
16장에서는 구체적이면서도 일반적인 시나리오에 속도상의 이점이 있는 또다른 트리를 알아본다.