이번 주는 결국 완성을 못했다.... 나의 호기심과 홍대병이 불러일으킨 대참사. 다들 이렇게 하길래 저렇게 하면 어떻게 되는데? 함 해볼까? 했다가 다른것까지 와장창 틀어져버렸다. 역시 사람들이 안하는 데에는 다 이유가 있어.
그래도 디버깅 엄청 열심히 했고 결국 왜인지 알아내서 뿌듯하다! 이게 웹개발 할때는 모르겠으면 다 콘솔 찍어보면서 했는데 추상적인 노드 개념이 들어가니까 모든 노드를 다 찍어볼 수도 없고 미칠 뻔 했다. 역시 개발할때는 해보고 안되면 찍어보고..가 초보자에게 가장 쉬운 방법은 맞지만 올바른 방법은 아니라는걸 다시 한번 느꼈다. 그래도 뭐 어째 모르겠으면 찍어봐야지!싶어서 이번엔 모든 노드의 메모리 주소를 찍어보면서 디버깅 했다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 참 한결같군! 나보다 더 열정적으로 새벽 세시까지 같이 디버깅해준 팀원도 아닌 동기 a씨와 팀원 b씨에게 무한한 감사를.
트러블슈팅
-
include<>는 내장라이브러리를 가져오는 거기 때문에 내가 만든 파일은 찾지 못한다. gcc 컴파일 할 때-o로 두개 묶어서 목적파일 만들어야 함. -
successor(삭제 노드보다 큰 노드 중 제일 작은 노드)를 가져오는게 아니라 predecessor(삭제 노드보다 작은 노드 중 제일 큰 노드)를 가져왔더니 뭔가 이상해졌다. 원래와 다르게, 부모와 자식 둘 모두 black인 상태에서 부모 노드를 삭제할 때 왼쪽 자식을 가져와서 붙이고 걔가 doubly가 되었다. 근데 이제 여기서 caseA를 적용하면서 부모를 왼쪽으로 rotate할 때 원래는 rotate하는 중심(부모)의 왼쪽 자손으로 더블,그 왼쪽 자손으로 나머지 서브트리가 붙어서 한번에 돌아아되는데 더블의 오른쪽 자손으로 서브트리가 붙으면서 rotate의 영향을 안받게 됨.
아닌데 이게 아니라 23-왼8-왼2-오12가 붙어있을 때 8을 삭제하면 원래는 12가 8자리에 붙으면서 doubly가 돼서 23을 중심으로 돌아야 하는데..? -
duplicate 함수를 실행하면 계속 memory leak가 났다. 근데 insert에서 어느 위치에 삽입할지 찾는 while문에서 키값 비교해서 같을 때 왼쪽에 넣으면 누수나고 오른쪽에 넣으면 괜찮음. key값이 같은 노드가 두개 이상 들어왔을 때 왼쪽에 넣으면 fixup하면서 유실되나? 근데 그러면 오른쪽에 붙이면 안난다고??라고 생각했는데 rotate나 fixup이 어느쪽에 붙는지에 따라 최적화돼야 할 듯 하다..
while (x != t->nil) { new_parent = x; if (key > x->key) { x = x->right; } else { x = x->left; } }
