목록2025/04/28 (1)
나의개발일지
레드-블랙 트리 (삭제)
📌 Red-Black 삭제요번 포스팅에서는 레드-블랙 트리의 삭제에 대해 알아보자. 이전 포스트에서도 말했듯이 레드-블랙 트리는 이진 탐색 트리 중에서 균형을 보장하는 대표적인 자료구조이다. 삭제하기전 알아야 할 개념- Extra Black삭제시 필요한 개념으로 노드에 임시로 부여 할 수 있다. - Doubly BlackBlack 노드에 Extra Black이 붙은 경우이다. - Red-and-BlackRed 노드에 Extra Black이 붙은 경우이다. - Successor오른쪽 서브트리에서 가장 작은 값 ❗ 레드-블랙 트리에서 삭제 대상 노드가 자식 들을 가질 경우, 실제로 삭제되는 노드는 successor이다 레드-블랙 트리 삭제의 흐름삭제할 노드를 찾는다.자식이 둘이면 successor와 교체..
기본기를 다지자/자료구조
2025. 4. 28. 17:09