5
주로 레드 - 블랙 트리의 버전을 구현했습니다. 주로 위키 피 디아 (http://en.wikipedia.org/wiki/Red-black_tree)의 알고리즘을 사용하고 있습니다. 그 부분은 상당히 간결하지만, 부분적으로 설명하고 싶습니다.레드 - 블랙 트리 - 리프가 아닌 두 개의 자식이있는 노드 지움
2 자 리프가 아닌 (NULL이 아닌) 자식이있는 트리에서 노드를 지울 때 양쪽 노드의 자식을 삭제 가능 노드로 이동하고 해당 자식을 제거한다고 말합니다.
나는 그것을 기반으로 어느 쪽을 제거해야하는지 조금 혼란 스럽습니다. 무작위로 측면을 선택합니까, 측면을 번갈아 변경합니까? 아니면 이후에 삭제 될 때마다 같은면을 고수하고 있습니까?
+1 - 의도적으로 임의의 동작을 도입하지 마십시오. 어떤 시점에서는 어딘가에서 버그가 발생하며 임의의 동작으로 인해 버그의 효과가 더욱 어려워지고 지속적으로 재현하기가 더 어려워집니다. –
동의 함. 무작위적인 행동을 도입 할만한 가치가있는 한 가지 상황은 특정 입력에 예측 가능하게 발생하는 것이 아니라 병적 인 최악의 행동을 낮은 확률로 예기치 않게 발생시키는 것입니다. 따라서 introsort가 발명되기 전에 qsort에서 무작위 피벗 선택. 나는 붉은 색 검은 나무의 최악의 행동이 여기 그것을 정당화하기에 충분히 나쁘지 않다고 생각합니다. 잘 알려진 무작위 "아마도 균형 잡힌"트리 구조가 있습니다. 잠시 동안 그 이름을 기억할 수 없습니다. –
빠른 응답을 보내 주셔서 감사합니다! – Salami