BSTとウェイトのバランスをとる

Question

私は、各ノードのウェイトを使って、バイナリ検索ツリーのバランスをとるための再帰的な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で、ソースを見ることができます。私はそれがデータのコピーを使用することを見たことがない、あなたはスタックを作成するか、単にそれをバランスさせるために新しいツリーを構築する必要があるとは思わない。

通常の動作では、ノードを左右、またはより複雑な組み合わせで回転させます。これにより、関係する作業が減り、ゴミも発生しません。