WOONY's 인사이트

지금 시간은 3시 3분..자그마치 6명의 집단 지성이 힘을 합쳐 겨우 디버깅을 완료하고 모든 테스트 케이스 통과!! 삭제 기능에 대해 빠르게 로직 정리하고 집 가야겠다.. 삭제(Deletion) 옮기거나 삭제하는 노드의 원래 색을 기억해뒀다가 옮기거나 지우려는 노드 색이 검정인 경우에만(=이중 흑색 노드) 트리를 고친다. 지우려는 노드 z 혹은 옮기려는 노드가 빨간색이면 rb트리 특성을 위반하지 않으니 고칠 필요가 없다. 지우려나 옮기려는 노드가 검정일 때는 경로 상의 검정 노드 개수가 변하므로 트리 특성을 위반한다. 이 경우에는 fixup 함수로 수정한다. 삭제 기능은 세 가지 케이스로 나눠서 구현한다. 1. 삭제하려는 노드(=z)의 왼쪽 자식만 있는 경우 (=오른쪽 자식이 NIL인 경우) 이때는 왼쪽..

요 며칠간 끊임없이 고통을 안겨줬던 레드블랙 트리(이하 RB트리)..그래도 계속 보다 보니까 얼추 감이 잡히기 시작한다. 아직 가장 큰 관문인 삭제가 남아있지만 그래도 삽입 구현 완료! RB트리 개념부터 시작해서 삽입까지 빠르게 정리하고 마무리할 예정. 오늘 풀었던 알고리즘 문제는 따로 포스팅해야겠다. Red-Black Tree(레드블랙 트리) 1. RB트리 정의 rb트리는 균형 이진 탐색 트리의 여러 버전 중 하나이다. 균형 이진 탐색 트리란, 이진 탐색 트리에 노드를 삽입/삭제하는 과정에서 어느 한 쪽으로 노드가 쏠리는 것을 방지하기 위해 규칙을 추가한 심화 버전 이진 탐색 트리라고 보면 되겠다. 왜 이런 짓을 하냐? 이진 탐색 트리를 만드는 이유는 특정 노드를 검색하는데 드는 시간 복잡도가 O(lo..