0

各ノードの重みを使用して、(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));
    }
}

何も返さずにツリーを変更しようとしていますが、コードはツリーを変更しません。どこかで参照渡しと値渡しで混乱していることは知っていますが、どこにあるのかわかりません-誰か助けてもらえますか? デバッグに数時間費やしましたが、再帰をデバッグするときは本当に混乱します。

4

1 に答える 1

0

バランシング アルゴリズムはかなり一般的で、よく文書化されています。たとえば、TreeMap は BST であり、そのソースを見ることができます。データのコピーを使用しているのを見たことがありません。バランスをとるために、スタックを作成したり、新しいツリーを構築したりする必要があるとは思えません。

通常の動作では、ノードを左または右に回転するか、両方をより複雑に組み合わせて回転します。これにより、関連する作業が軽減され、ゴミが作成されません。

于 2012-03-26T08:04:42.460 に答える