가중치로 BST 밸런싱

Question

각 노드의 가중치를 사용하여 이진 검색 트리 (int를 사용하지만 범용 설계됨)의 균형을 유지하는 재귀 적 Java 메소드를 빌드하고 있습니다. 내 목적을 위해, 노드의 무게가 균형의 끝에서 + 1.

2 
/ \ 
1 3 

The weight of the root is 3, and the weight of both leaves is 1. 

아이의 수로 정의된다, 모든 노드의 값은 모든 노드에서 값의 평균해야한다 그 노드를 루트로하는 서브 트리.

여기 내 코드입니다 : 난 아무것도 반환하지 않고 장소에 나무를 수정하기 위해 노력하고있어

public void weightBalance (BinarySearchTree<AnyType> t) { 

    // Base case 
    if (t.getRoot().left == null && t.getRoot().right == null) { 
     return; 
    } 

    // Get median of tree 
    AnyType median = t.getMedian(); 

    // Create new BST with median as root 
    BinarySearchTree<AnyType> newTree = new BinarySearchTree<AnyType>(); 
    newTree.insert(median); 

    // Insert all values except median into new BST 
    ArrayList<AnyType> stack = new ArrayList<AnyType>(); 
    inorderTraverse(t.getRoot(), stack); 
    Iterator<AnyType> itr = stack.iterator(); 
    while (itr.hasNext()) { 
     AnyType temp = itr.next(); 
     if (temp != median) { // Comparing values or reference? 
      newTree.insert(temp); 
     } 
    } 

    // Replace old BST with new BST 
    t = newTree; // t is a copy of the reference, is this the problem? 

    // Recurse through children 
    // Tree constructor for reference: 
    // public BinarySearchTree (BinaryNode<AnyType> t) { 
    // root = t; 
    // } 

    if (t.getRoot().left != null) { 
     weightBalance(new BinarySearchTree(t.getRoot().left)); 
    } 
    if (t.getRoot().right != null) { 
     weightBalance(new BinarySearchTree(t.getRoot().right)); 
    } 
} 

하지만, 코드 트리를 변경하지 않습니다. 나는 을 알고있다. 나는 참조로 지나가는 어딘가에서 가치를 지나쳐 어지럽히지만, 나는 어디에서 도와 줄 수 있는가? 몇 시간 동안 디버깅을했는데 재귀를 디버깅 할 때 혼란스러워집니다.

Answer 1

균형 알고리즘은 매우 일반적이며 문서화되어 있습니다. TreeMap은 BST이며 원본을 볼 수 있습니다. 나는 데이터 복사본을 사용하는 것을 본 적이 없다. 스택을 만들거나 균형을 맞추기 위해 새로운 트리를 만들 필요가 있는지 의심 스럽다.

정상적인 동작은 노드를 왼쪽 또는 오른쪽으로 회전하거나 두 가지를 더 복잡한 조합으로 회전시키는 것입니다. 이렇게하면 관련된 작업이 줄어들고 쓰레기가 생성되지 않습니다.