OTHER
C - 이진트리 구현
TEST
COMMENT
현재 시각 새벽 3시..
이진(탐색)트리를 대강 구현하고, RB Tree 를 시작할 예정이었건만 예상외로 삭제가 너무 어렵게 다가왔다.
이진탐색트리에서 삽입은 트리의 현재 구조를 변경하지 않고 자신의 올바른 위치만 제대로 찾아가기만 하면 되기 때문에 크게 문제되지 않았지만, 삭제의 경우에는 자신의 위치를 파악한 뒤, 조건에 따른 처리 절차가 생각보다 복잡했다.
본인이 루트 노드인지 아닌지
자신에게 자식이 있는지 없는지
2-1. 있다면 왼쪽 자식만 있는지
2-2. 오른쪽 자식만 있는지
2-3. 양쪽 다 있는지오른쪽 자식이 있는 경우(2-2, 2-3), 오른쪽 자식 중 가장 작은 값으로 삭제된 노드의 위치를 메꿈
3-1. 교대할 오른쪽 자식의 가장 작은 값이 오른쪽 자식 노드가 있는지
위의 경우에서 나는 루트노드인지 아닌지에 따라 2, 3번의 조건의 경우를 각각 다르게 작성하였는데(부모 노드 처리 때문에) 그렇게 작성하니 각각의 조건을 모두 고려하는 deletion 함수의 길이가 150줄 가량이 되었다.
심지어, 하나의 조건문에서 디버깅을 진행하면 다른 조건문에서 에러가 발생하는 끝없는 디버깅의 늪에 빠지게 되었다.
결국 약 6시간의 디버깅 끝에 deletion 함수를 다시 작성하는 방향으로 결정했다.
이후 내가 작성한 이진탐색트리에 대한 동기의 코드 리뷰 결과, 이중 포인터를 활용하는 것을 추천해줬는데 아직 이중 포인터를 어떤 식으로 활용해야할 지 머릿속에서 그려지지 않아 설 과제를 다 해결한 뒤에 다시 한 번 고민해볼 생각이다. (근데 설 과제 중에 이진탐색트리 구현이 있던데..)
