오른쪽 오른쪽 회전 또는 오른쪽 왼쪽 회전이 필요한지 여부를 결정하는 방법

AVL 트리를 구현하려고하는데 RR 또는 RL 회전이 필요할 때를 알기 힘듭니다 (LL 및 LR과 동일) .오른쪽 오른쪽 회전 또는 오른쪽 왼쪽 회전이 필요한지 여부를 결정하는 방법

각각의 전제 조건은 무엇이며 어떻게 다릅니 까? 나는 나무의 그림을 보았을 때 (직관적으로) 알 수 있지만 실제 조건은 무엇입니까?

이것은 논리 문제이므로 코드가 필요하지 않습니다. 감사합니다.

제가 아는 것은입니다. 나무가 무겁거나 오른쪽 무거워 져야합니다. 그런데 어떻게 결정합니까?

2012-07-01 Kalec

특정 작업으로 간주됩니까? 예 : 트리에 노드를 추가 한 다음 밸런스 속성을 유지? – niklon

추가 및 제거 모두에서, 그러나 내가 이해한다면, 다른 하나는 쉽게 알 수 있다고 상상해보십시오. 나는 나무가 항상 균형을 유지하기를 원하지만, 수정되는 유일한 시간은 요소를 추가하거나 제거하는 것이므로 다른 순간을 볼 수 없습니다. ** 그러나 ** – Kalec

이 다른 솔루션 수 있지만 하나는 다음과 같습니다 수 있습니다

이 시켜서 (해당 통화가 왼쪽이나 오른쪽 서브 트리에 노드를 추가할지 여부를 추적한다 각 재귀 호출에 재귀 항목을 추가 할 때 예를 들어 add 함수가이를 반환합니다. 재귀 호출 후 높이 불변성을 확인합니다. 삽입 후 해당 노드에서 위반되었다는 것을 알게되면 불균형에 대한 경로를 알게됩니다.

일부 (불완전) 의사 코드 :

add(item, node): 
    if item < node.value //should add to left subtree 
    if node.left is empty 
     //add item here 
    else 
     addedLeft := add(item, node.left) 
     if node.left.height - node.right.height > 1 
     if addedLeft 
      //you know the path to the subtree causing the imbalance is LL, do a RR (single-right) rotation 
     else 
      //path is LR, do a LR (double-right) rotation 
    ...

재귀 호출이 추가 된 노드에서 상향식 (bottom-up)을 전개하고 일반적인 생각이되는 불변 (있는 경우)을 위반 노드 확인하는 것입니다. 해당 노드가 발견되면 불균형을 초래하는 하위 트리에 대한 경로를 알아야합니다. 어떻게 든이 문제를 해결해야합니다. 이것이 하나의 해결책입니다.

출처

2012-07-01 09:50:55 niklon

순간에 요소 추가에 집중하기를 원하므로 노드를 추가하는 동안 진행 한 경로를 추적해야합니다. 이것은 내가 마지막 두 경로를 기억해야한다는 것을 의미합니까? (LL 또는 LR 등)? – Kalec

음, 그렇습니다. 네, 위의 pseude 코드보다 "기억"할 필요가 없으므로 수행 할 회전을 결정하는 데 필요합니다. 논리는 여기에 노드를 왼쪽 하위 트리에 추가하기로 결정한 것입니다 add에 대한 재귀 호출도 왼쪽 하위 트리에 항목을 추가하기로 결정할 때 불균형을 초래하는 하위 트리는 현재 노드에서 왼쪽으로 남겨 두어야합니다. 그게 도움이 되니? – niklon

예, 알았습니다. 먼저 이것을 구현할 필요가 있지만 작동한다면 (당신이 의미하는 바를 얻었음을 의미합니다) 나는 대답을 선택합니다. 그렇지 않으면 질문을 업데이트 할 것입니다. 어쨌든 고맙습니다. – Kalec

오른쪽 오른쪽 회전 또는 오른쪽 왼쪽 회전이 필요한지 여부를 결정하는 방법

답변

관련 문제