Балансировка 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, и вы можете увидеть его источник. Я никогда не видел, чтобы он использовал копию данных, я сомневаюсь, что вам нужно создать стек или построить новое дерево, чтобы сбалансировать его.

Нормальным поведением является вращение узлов влево или вправо или более сложная комбинация обоих. Это уменьшает вовлеченную работу и не создает мусора.