질문 게시판 / Q&A

BTS -string 에 대해 질문 있습니다!!

by peterzzo, 11월 18일, 01:06

"만일 그것이 내부 노드라면 그것을 지운 다음 왼쪽 부트리의 최대값으로 대치한다. 왼쪽 부트리가 없으면 오른쪽 부트리의 최소값으로 교체한다. 이 작업은 지울 대상 노드가 leaf가 될 때까지 반복한다. 즉 중간노드를 지우는 작업은 각 subtree에서 재귀적으로 적용된다."
이부분이 이해가 잘 안돼서 질문 드립니다!!
만약
soju
main
left right

이런 형식의 트리에서 -soju 를 한다면

left
main
right

이렇게 되고 만약 -main 을 한다면
soju
left
right

이렇게 되는게 맞습니까? ㅠㅠ 헷갈려서 질문 드립니다!!!

peterzzo , 11월 19일, 02:12
 아 이해했습니다 감사합니다 교수님!! 
prof , 11월 18일, 12:44
 좀 더 "지능적"으로 한다면 오른쪽 왼쪽 subtree중에서 depth가 더 큰 쪽에서하나를
들어 오면 좋겠죠.  이러면 비용은 더 들지만 트리는 좀 더 통통해질 수 있습니다.

AVL이나 Red-Black 트리는 이런 식의 시도로 탄생한 것이라 보면 됩니다. 
prof , 11월 18일, 10:59
 left
                  main
                        right

에서 'main'을 제거하면
1) main을 제거합니다.
2) 왼쪽 tree는 null이므로 차례를 오른쪽으로 pass
3) 오른쪽 subtree에서 제일 큰 것은 right (크고 자시고 할 것도 없이 하나 뿐이라...)
4) 이 놈은 leaf이라 더 이상 진행할 것도 없이
5) 따라서결과는

             left
                   |
                   right

(질문) 근데 위 설명에서 난데없이 "soju"는 왜 나타나는지요 ?