tree erase 구현

tree 내부에서 중위순회 , 노드 추가등을 구현했지만

erase의 구현을 목표로 코딩을 했어지만 코드를 작성하는과정에서 과부하가 와서

강의를 듣고 따라서 구현을 하였다.

 

erase 의 작동원리를 정리해보았다. 크게 3가지로 나눌 수 있었다.

1. 자식노드가 없는 경우

자식노드가 없는 경우에는 두가지 경우로 다시 나눌 수 있었다

노드가 한개라서 자기자신이 루트노드인 경우에는 노드를 딜리트하고

iteraotor 가 가리키는 root 노드를 nullptr로 수정해주고

부모노드가 있은 경우에는 부모노드내의 왼쪽자식인지 오른쪽자식인지 확인후에

노드 포인터를 nullptr로 수정해준다.

 

2. 자식노드가 한개인 경우

자식노드가 한개인경우에는 부모노드와 자식노드를 이어주면 된다.

이때 만약에 부모노드가 없는 경우에는 자기자신이 루트노드이므로 자식노드가 루트노드가

되고 root노드 포인터들을 자식노드를 가리키면 된다.

 

3. 자식노드가 2개인경우

이분이 가장어려웠던 부분이였다. 처음에는 노드의 스왑해주는 형식으로 코딩할려했지만 실패하고

나서 강의를 들었었는데 중위선행자의 자식노드는 0이나 1개라는 점이 가장핵심이였다.

중위선행자를 재귀함수형태로 구현하여 다시한번 erase함수에 넣어주는 방법으로 해결했다.

중위선행자의 자식노드는 2개미만으로 무한루프에는 빠지않으며 한번만 실행된다.