그림 10-8에서 키 6이 있는 노드는 리프 노드가 아니므로 대체 키를 찾아야 합니다. 대체 키는 왼쪽 서브 트리에서 가장 큰 키인 5가 됩니다. 키 5보다 큰 키가 있다면 그 키가 대체 키가 됩니다.

그러면 다음 그림과 같이 대체 키 5와 키 6을 바꾸어 주게 됩니다.

▲ 그림 10-9 donate 1

이런 교환은 BST에서 자식 노드가 둘이 있을 때 하는 삭제와 비슷한 점이 많지요. BST에서도 대체 노드를 찾기 위해 왼쪽 서브 트리에서 가장 큰 노드를 찾았습니다. 이제 키 6이 있는 리프 노드에서 키 6을 삭제하면 됩니다. 이 노드에 다른 키가 있었다면 여기서 알고리즘은 종료될 것입니다. 그런데 이번 예제에서는 문제가 생겼습니다. 키가 하나밖에 없어서 키 6을 지우면 노드가 사라집니다. m=3인 2-3 트리의 서브 트리는 최소한 두 개 있어야 합니다. 리프 노드가 사라지면서 키 5를 가진 노드의 서브 트리가 한 개가 되었습니다. B 트리의 특성이 깨진 것이지요.