[자료구조] 이진탐색트리 구현 - 삭제

이진탐색트리에서 삭제를 할 때에는 경우의 수를 3가지를 생각해야 한다. 경우 1) 리프노드(자식이 없는 노드)일 경우 * 이 경우 단순히 해당 노드를 null로 처리하고 그 노드를 return하기만 하면 된다. 경우 2) 왼쪽/오른쪽 중에서 한쪽에만 자식이 있는 경우 * 오른쪽에만 자식이 있다면, 왼쪽 자식을 해당 노드로 바꾸고 그 노드를 return한다 (한마디로 할아버지가 손자 손을 잡도록 하는 격) 경우 3) 왼쪽/오른쪽 양쪽 모두 자식이 있는 경우 * 삭제하려고 하는 노드를 [왼쪽 서브트리 중 가장 큰 노드]또는 [오른쪽 서브트리 중 가장 작은 노드]로 교체하고, 이 후 서브트리에서 그 노드는 삭제를 해준다. * 나는 [오른쪽 서브트리 중 가장 작은 노드]로 대체하는 방법을 선택하여 자바스크립트 ..

2021.03.17