dummy 노드 (즉, 실제로 null 포인터 인 리프 노드)를 사용하지 않고 red-black-tree에서 요소 삭제를 구현하는 방법을 안내를 찾고 있습니다. google/wikipedia 및 표준 문학 (sedgewick 및 cormen al)에서 발견 된 모든 구현은 더미 NIL 노드를 사용하고 있으므로 피하고 싶습니다.빨간색 검은 색 트리 - dummys가없는 요소 제거
삽입시 Okasaki의 이중 빨간색 제거 기능이 기본적으로 작동합니다. 평소와 같이 BST에 넣고 뿌리까지 두 배의 붉은 색을 계속 제거하십시오.
빨간색 노드를 삭제해도 문제가 발생하지 않습니다. BST에서 두 명의 하위 노드가있는 노드는 절대 삭제하지 않습니다. 하나의 자식이있는 검은 노드를 삭제하면 자식을 검정색으로 채우고 완료됩니다. 검은 잎 (실물이 아닌 더미)을 삭제하는 것만이 문제가됩니다. Matt Might's approach은 더미 노드없이 작업 할 수 있습니다. 트릭은 매트의 "버블 링"을 사용하여 잎을 빨간색으로 변 환하는 것입니다. 그런 다음 간단히 제거하십시오.
Here은 코드가 포함 된 솔루션입니다.