달력

3

« 2024/3 »

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
2016. 12. 3. 23:47

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
:
Posted by 클레잇