-
KD 트리의 삽입과 삭제
KD 트리는 검색 과정을 통해 리프 노드에 도달한 경우 왼쪽 혹은 오른쪽 자식으로 새로운 노드를 삽입하면 된다.
삭제의 경우 이진 검색 트리와 달리 자식이 하나인 경우에도 자식이 두 개인 경우와 마찬가지로 처리해 줘야 한다.
이는 단순히 상위 레벨로 노드를 올리게 된다면 사용하는 필드가 달라져 속성이 깨지기 때문이다.
삭제 시 노드가 두 개인 경우, 오른쪽 서브 트리에서 삭제할 노드에 사용된 필드의 값이 가장 작은 노드를 찾아 삭제할 노드와 교환하고 찾은 노드를 삭제한 뒤, 말단 노드가 아닌 경우 삭제 과정을 반복하면 된다.