인프런 커뮤니티 질문&답변

안녕하세요 산성님!
질문 내용으로 봤을 때 재귀로 구현한 부분이 헷갈리신 것 같아서 예시와 함께 설명드리겠습니다.

먼저 아래 사진과 같은 트리에서 9를 제거하는 상황으로 가정하겠습니다.

그럼 getUnbalanceNode() 함수의 targetRootNode가 7인 노드를 가리키고 있을겁니다.

이 상황에서는 getUnbalanceNode의 기저조건에 해당하지 않으니 왼쪽 자식이 더 큰 상황으로 아래 코드가 실행됩니다.

if(balanceFactor > 0){
    unBalanceNode = this.getUnBalanceNode(targetRootNode.getLeftSubTree(), unBalanceNode);
} ...

이렇게 재귀로 자기 자신을 호출하면서 getUnbalanceNode의 targetRootNode는 아래 사진처럼 4가 됩니다.

targetRootNode가 4인 새로 호출된 getUnBalanceNode에서는 좌우 밸런스가 0으로 똑같습니다.
현재 실행되는 getUnBalanceNode에선 4가 루트노드이고 이 루트노드보다 큰 값은 5이기 때문에 오른쪽 자식이 가장 큰 값이라고 말할 수 있습니다.

이런 이유로 좌우 밸런스가 0으로 같을 땐 오른쪽 노드를 리턴해주는 것입니다.

궁금증이 해결되셨나요?😊

안녕하세요, 인프런 AI 인턴입니다. 산성님께서 AVL 트리의 getUnBalanceNode 함수 설명에서 헷갈리신 부분에 대해 도움을 드리겠습니다.

AVL 트리는 자가 균형 이진 탐색 트리로, 트리의 높이 균형이 깨질 때 회전을 통해 균형을 유지합니다. getUnBalanceNode 함수는 균형이 깨진 노드를 찾는 데 사용됩니다. 질문하신 내용을 중심으로 설명을 드리겠습니다.

1. 대체할 노드:

   • AVL 트리에서는 균형이 깨졌을 때 회전을 통해 트리를 수정합니다. 이 경우 대체할 노드는 회전 후 트리의 루트가 될 새로운 노드를 의미합니다. 균형이 깨진 노드의 오른쪽, 왼쪽 자식 중 필요한 방향으로 회전을 수행하고 대체할 노드를 결정하게 됩니다.
     

2. 왼쪽 자식 노드의 가장 큰 값:

   • AVL 트리에서 노드를 삭제할 때, 대체할 노드를 찾는 방법 중 하나는 노드의 왼쪽 하위 트리의 가장 오른쪽 자식(가장 큰 값)을 선택하는 것입니다. 때문에, 말씀이 맞습니다. 그 자식은 서브트리 내 가장 큰 값이며, 부모 노드와 비교했을 때 상대적으로 작은 서브트리 내의 가장 큰 값입니다.
     

3. 강의 내 선택 부분:

   • 보통 AVL 트리 구현 강의에서 이와 같은 내용은 균형이 깨지는 상황(예: LL, RR, LR, RL 회전)에 대한 설명과 함께 진행됩니다. getUnBalanceNode 함수의 경우 트리의 불균형을 체크하는 로직으로, 불균형이 감지된 분기에서 이미 반환된 대체 노드가 결정됩니다. 강의를 다시 확인하시어 회전 및 노드 교체 설명을 주의 깊게 보시면, ‘가장 큰 값을 선택’하는 부분이 확실히 이해되실 것입니다.
     

아래 링크에서 관련 구현에 대한 추가 설명을 확인하실 수 있을 것입니다.
- AVL 트리의 회전과 균형 잡기 설명

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.