5 - BST(Binary Search Tree) remove

자, 그리고 이번엔는 remove를 만들어보겠습니다.

 

remove는 여러가지 케이스를 고려해줘야 합니다.

 

1) 자식이 없을 때

2) 자식이 한개일 때

3) 자식이 두개일 때

 

의 3개의 케이스를 고려해줘야 합니다.

 

1) 케이스를 봐 볼까요?

 

 

 

여기 보이시는 맨 밑의 노드가 없어진다고 해도 딱히 특별한 변화가 있지 않습니다.

 

때문에, 그냥 지워주면 됩니다.

 

그러면 2)의 경우 자식 노드가 하나일 때를 생각해볼게요

 

 

30이 지워지면 20이 들어오면 끝납니다.

 

그런데 자식이 2개면 어떻게 될까요??

 

3)의 케이스를 한번 보겠습니다.

 

 

이렇게 자식 노드가 2개인 50이 remove되면, 얘의 오른쪽에서 가장 왼쪽에 있는 노드를 찾아와서 맨 위로 넣어줍니다.

 

여기에서는 60이죠?

 

 

그러면 얘를 코드로 한번 표현해보겠습니다.

 

 

참조

[1] - https://www.youtube.com/watch?v=xxADG17SveY

[2] - https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

[3] - http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html