나는 Left Leaning Red Black Trees에 대해 학습 중입니다.왼쪽으로 기울어 진 빨강 검정 나무의 삭제
종이에 나타난 삭제 알고리즘에서 키가 노드와 일치하고 해당 노드에 대해 올바른 하위 트리가 NULL이면 해당 노드가 삭제됩니다. 그러나 고려되지 않은 왼쪽 하위 트리도있을 수 있습니다.
왼쪽 서브 트리가 NULL이면서 인 이유는 무엇입니까? 을 이해할 수 없습니다. 최소값 또는 최대 값을 삭제할 때도 비슷한 일이 발생합니다. 아무도 이걸 안내하지 않겠습니까?
당신이 코드의이 작품에 대해 말하는 것 같다 코드를 이전하면 오른쪽으로 회전 때문에
if (isRed(h.left))
h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;
여기에 왼쪽 후손 "빨간색"이 될 수 없습니다.
왼쪽 자손은 "검은 색"일 수 없습니다.이 경우 "검은 색"노드가 하나 이상있는 "검은 색"노드가있는 h의 왼쪽 경로가 있고 "검은"노드가있는 경로가 없기 때문입니다. 그러나 RB-tree에서 모든 경로의 검정 노드 수는 동일해야합니다.
이것은 왼쪽 자손이 전혀없고 노드 h이 리프 노드임을 의미합니다.
deleteMin 함수에서 LLRB 트리의 오른쪽 하위 트리가 해당 왼쪽 하위 트리보다 클 수 없기 때문에 왼쪽 하위 트리가 비어 있으면 오른쪽 하위 트리를 확인할 필요가 없습니다.
왼쪽에서 기울고있는 빨강 검정 나무가 이전 구현보다 실제로 더 좋고 간단한 지에 대한 흥미로운 분석이 있습니다. Harvard Comp Sci 교수 Eddie Kohler이 작성한 Left-Leaning Red Black Trees Considered Harmful 문서. 그는 글을 참고하세요 :
Tricky writing
Sedgewick’s paper is tricky. As of 2013, the insert section presents 2–3–4 trees as
the default and describes 2–3 trees as a variant. The delete implementation, however,
only works for 2–3 trees. If you implement the default variant of insert and the
only variant of delete,your tree won’t work. The text doesn’t highlight the switch
from 2–3–4 to 2–3: not kind.