이진 검색 트리 균형

Question

히트는 find(), contains() 등을 사용하여 노드를 찾을 때 증가하는 특성 인 히트 및 해당 요소에 따라 노드의 균형을 조정하는 BST에서 작업하고 있습니다. 트리의 루트는 적중 횟수가 가장 많은 노드입니다. 내 코드는 모두 괜찮 았지만 균형을 맞추는 방법은 제외하고 균형을 조정합니다. 수정 된 AVL Tree rotate 메서드 (https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java)를 사용하고 있습니다. 여기서는 요소를 비교하지 않고 노드의 히트 수를 비교합니다. 내가 상관없이 내가 무엇을하려고 작동하지 얻을 수 없습니다, 나는 나무가 제대로 여기에 균형을 얻을 수없는 것은 지금까지 내 코드입니다 :

public void balanceTree() { 
    balanceTree(root); 
} 

private void balanceTree(Node node) { 

    if (node.left.getHits() <= node.getHits() && node.right.getHits() <= node.getHits()) { 
     return; 
    } else if (node.left.getHits() > node.getHits()) { 
     node = rotateWithLeftChild(node); 

    } else if (node.right.getHits() > node.getHits()) { 
     node = rotateWithRightChild(node); 

    } 


} 

static Node rotateWithLeftChild(Node k2) { 
    Node k1 = k2.left; 
    k2.left = k1.right; 
    k1.right = k2; 
    return k1; 
} 

static Node rotateWithRightChild(Node k1) { 
    Node k2 = k1.right; 
    k1.right = k2.left; 
    k2.left = k1; 
    return k2; 
} 

것은 지금 밸런스 방법은 단순히 노드는 삭제됩니다 회전해야하는데, 디버깅을 시도했지만 잘못된 것을 볼 수 없었습니다.

Answer 1

하나는, 전달 된 매개 변수를 변경할 수 없습니다.

public void balanceTree() { 
    root = balanceTree(root); 
} 

private Node balanceTree(Node node) 
    if (node.left.getHits() <= node.getHits() 
      && node.right.getHits() <= node.getHits()) { 
     node.left = balanceTree(node.left); 
     node.right = balanceTree(node.right); 
    } else if (node.left.getHits() > node.getHits()) { 
     node = rotateWithLeftChild(node); 
    } else if (node.right.getHits() > node.getHits()) { 
     node = rotateWithRightChild(node); 
    } 
    return node; 
} 

당신이 모든 삽입 한 후 나무를 의 균형을 가정하면, 다음 하나는 하위 트리의 균형을 회전 후 재귀 필요가 없다.

회전하지 않고 재발행해야합니다.

현재 알고리즘은 왼쪽과 오른쪽으로 반복되지만 왼쪽에 회전이 발생하면 오른쪽 하위 트리가 더 이상 재귀 될 수 없습니다.

이러한 종류의 수정 알고리즘에 대해 더 걱정되는 점은 안정화되지 않을 수도 있다는 것입니다. 즉, 재조정을 유지하는 것입니다. 그러나 당신은 분명히 테스트에 집중할 것입니다.

Answer 2

이 코드에는 2 가지 문제가 있습니다.
1)이 트리의 구조가 누락되었습니다. 따라서 hitCount를 기준으로 정렬해야합니다. 기본적으로 목록/컬렉션이 hitCount로 정렬되지 않았습니까?

지금은 자신보다 높은 hitCount가있는 노드를 왼쪽 및 오른쪽 노드로 교체하고 있습니다. 그래서 2 개의 노드 [A, B] A가 1 hitCount이고 B가 2 hitCounts라고 상상해보십시오. 그래서 (당신이 propably itterate 노드으로 초과거야) 정렬에 :
이 상황을 시작하기 : [A는 B]

첫 번째 정렬 : 은 오른쪽에 스왑 그래서 B보다 낮은 hitCount 있습니다. 결과 = [B, A]

두 번째 정렬 : A는 B보다 hitCount가 낮으므로 왼쪽으로 바꿉니다. 결과 = [A, B]

어디에서 끝나나요? 더 나은 아이디어는 목록을 사용하고 hitCount를 기반으로 노드를 정렬하는 것입니다. 이렇게하면 모든 것을 망칠 필요가 없습니다.

2) 스왑 방식이 생각한 것처럼 작동하지 않습니다. 다음을 자세히 살펴보십시오.

static Node rotateWithLeftChild(Node k2) { 
    Node k1 = k2.left; 
    k2.left = k1.right; 
    k1.right = k2; 
    return k1; 
} 

// exact the same results: 
static Node rotateWithLeftChild(Node k2) 
{ 
    k2.left = k2; 
    return k2.left; 
} 

나에게 맞는 것 같지 않습니다.

static Node rotateWithLeftChild(Node k2) 
{ 
    Node k1 = k2.left; 
    k1.right = k2.right; 
    k2.left = k1.left; 
    k1.left = k2; 
    k2.right = k1; 
    return k1; 
} 

그리고 물론

반대 "rotateWithRightChild"간다 : 아마 당신은 같은 것을 의미했다.

나는 이것이 당신을 조금 도왔 으면 좋겠다.

편집 :

방법 주문 목록/컬렉션을 구현하는 방법? 일단 노드가 트리에 추가되면 노드를 Lisf/Collection에 추가하기 만하면됩니다. 당신이 노드를 정렬 할 때, 단순히 이것을 사용 :

는

//myNodesCollection is the List/Collection containing all the nodes. 
static void sortByHitCount() 
{ 
    Collections.sort(myNodesCollection, (n1, n2) -> n1.getHits() - n2.getHits()); 
} 

이 복잡하게 보일 수도 있지만, 이것은 당신을 위해 모든 정렬을 수행하는 방법입니다. 첫 번째 매개 변수는 정렬 할 List/Collection입니다. 두 번째 매개 변수는이 경우 hitCount를 기준으로 각 노드를 비교하는 비교 자입니다.

문서 : 하나는 새로운 노드의 값을 반환 할 필요가 있도록 자바에서 https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html