Binary Search Tree - 삭제 자료구조&알고리즘2016. 12. 3. 23:47
학창시절 BST를 구현할 때 삭제가 어려웠던 적이 있다.
자료구조 책들을 보면 쉽게 풀어서 설명해 준 책은 많이 없다.
대부분 소스코드를 던져 주고 코드를 통해서 이해를 하라거나, 슈도코드를 추적해봐야 알 수 있다.
BST의 삭제를 처음 구현하는 사람은 다음 순서를 따르면 좋다.
1. 경우의 수 파악하기.
2. 각 경우의 수에서 어떤 식으로 삭제가 되는지 파악하기.
3. 코드 구현.
(이런 순서대로 공부해야 하는데, 소스코드 던져주고 니들이 알아서 파악해보세요~라고 하니 비효율적이 될 수밖에 없다)
일단은 경우의 수는 3가지가 나온다.
이것만 알아도 BST 삭제의 뼈대를 잡는 거다.
아래 그림에서 주황색으로 표시된 부분을 주목해서 보면 된다.
경우1) 삭제할 노드의 우측자식이 없음.
-> 삭제할 노드의 좌측자식을 그대로 삭제한 위치에 올려주면 됨!
경우2) 삭제할 노드의 우측자식은 있지만, 우측자식의 좌측자식은 없음(말이 이해 안되면 그림의 주황색 캡슐을 보면 됨)
-> 삭제할 노드의 우측자식을 그대로 삭제한 위치에 올려주면 됨!
경우3) 삭제할 노드의 우측자식이 있고, 우측자식의 좌측자식도 있음.
-> 이 경우가 그나마 어렵다.(지금은 귀찮으므로 추후에 그림으로 업데이트 할 예정. 일단 말로 설명.)
삭제할 우측자식으로 포인터를 이동한 후, 그것의 좌측자식으로 계속 이동한다. NULL이 나오기 전까지 이동하면 됨. 그럼 그 노드가 삭제할 위치를 대신할 노드가 된다.
노드를 저장할 포인터는 총 4개가 필요하다.
1. 삭제할 노드의 부모 : delp
2. 삭제할 노드 : del
3. 후보(삭제할 자리를 대신 채울) 노드 : cdd
4. 후보 노드의 부모 : cddp
1단계) cdd가 사라질 것을 대비한 연결 : cddp->left = cdd->right
2단계) del이 가리키던 것 cdd도 똑같이 가리키게 하기 : cdd->left=del->left; cdd->right=del->right;
3단계) del의 부모가 del대신 후보 가리키게 하기 : delp->right = cdd;
4단계) del의 동적할당 해제하기
말로 쓰니 어려워 보이지만... 귀차니즘이 없어지면 그림으로 과정을 정리해서 올릴 생각.
그리 어려운 개념이 아님. 과정만 정확히 파악한다면 코드로 옮기는 것은 어렵지 않음.
'자료구조&알고리즘' 카테고리의 다른 글
정규 표현식(regular expression) (0) | 2017.01.05 |
---|---|
Java의 자료구조 (0) | 2016.12.21 |
퀵정렬 시뮬레이션 (0) | 2016.11.28 |
알고리즘 연습 사이트 (0) | 2016.09.11 |