Балансирование бинарного дерева поиска рекурсивно

Question

У меня есть BinarySearchTree с объектами Instance bankaccount, который является классом, который я создал, так что в основном это просто двоичное дерево поиска, и я написал метод, который возьмет дерево и уравновесит его, по какой-то причине он печатает точнодерево перед балансом:

Теперь, во-первых, у меня есть метод createList, который берет список и tree(one node) и создает arrayList(DynamicArray) данных дерева, просматривая их по порядку, так что это отсортированомассив.Затем другой метод используется для сбалансированного создания дерева, делая средний элемент корня массива, затем левый средний корень левого поддерева и правый средний корень правого поддерева

import java.util.Comparator;
import java.util.Iterator;

public class BankAccountsBinarySearchTree extends BinarySearchTree<BankAccount>{

public BankAccountsBinarySearchTree(Comparator<BankAccount> myComparator) {
    super(myComparator);
}

//Complete the following method
public void balance(){


    // create a sorted list and a binary tree
    List<BankAccount> list = new DynamicArray<BankAccount>();
    BankAccountsBinarySearchTree tree = new BankAccountsBinarySearchTree(comparator);
    createList(tree.root, (DynamicArray<BankAccount>) list);

    // build balanced tree recursively
    buildBalancedTree(tree, list, 0, list.size()-1);
}

//Complete the following method
private void buildBalancedTree(BankAccountsBinarySearchTree tree, List<BankAccount> list, int low, int high){

        // base case
        if (low > high)
            return ;

        // Get the middle element and make it root
        int mid = (low + high) / 2;
        tree.root.data = list.get(mid);

        // create left and right subtrees and go on to balance each
    BankAccountsBinarySearchTree leftTree = new BankAccountsBinarySearchTree(comparator);
    BankAccountsBinarySearchTree rightTree = new BankAccountsBinarySearchTree(comparator);

    buildBalancedTree(leftTree, list , low, mid - 1);
    buildBalancedTree(rightTree, list, mid + 1, high);

    root.left = leftTree.root;
    root.right = rightTree.root;


}

// method to create a list with all objects of BankAccountBinarySearchTree in a sorted array because it's in Order.
private void createList(BinaryNode<BankAccount> root, DynamicArray<BankAccount> list)
{
    // Base case
    if (root == null)
        return;

    // Store nodes in Inorder (which is sorted
    // order for BST)
    createList(root.left, list);
    list.add(root.data);
    createList((BinarySearchNode) root.right, list);
}

public Iterator<BankAccount> iterator(){
    return new FilteredBankAccountsIterator(this);
}

}

По какой-то причине, если я сделаю это:

Comparator<BankAccount> c = new AccountComparatorByNumber();

   BankAccountsBinarySearchTree t3 = new BankAccountsBinarySearchTree(c);
    t3.insert(new BankAccount("a", 2, 0));
    t3.insert(new BankAccount("a", 1, 0));
    t3.insert(new BankAccount("a", 3, 0));
    t3.insert(new BankAccount("a", 4, 0));
    t3.insert(new BankAccount("a", 5, 0));
    t3.insert(new BankAccount("a", 6, 0));
    t3.insert(new BankAccount("a", 7, 0));
    t3.insert(new BankAccount("a", 8, 0));
    System.out.println("----------unbalanced t3:----------\n" + t3);
    t3.balance();
    System.out.println("\n----------balanced t3:----------\n" + t3 + "\n\n");

хорошо, сначала он будет использовать компаратор для сортировки массива по номеру, поэтому массив должен быть {1,2,3,4,5,6,7,8} (так работает этот компаратор), и тогда я ожидал, что дерево будет сбалансированным, однако оно останется прежним.Есть идеи, что не так с кодом?

edit: это то, что я изменил до сих пор, и buildBalancedTree дает мне исключение NullpointerException

public void balance(){


        // create a sorted list and a binary tree
        List<BankAccount> list = new DynamicArray<BankAccount>();

        BankAccountsBinarySearchTree tree = new BankAccountsBinarySearchTree(comparator);

        tree.root = this.root;

        createList(tree.root, (DynamicArray<BankAccount>) list);


        // build balanced tree recursively
        buildBalancedTree(tree, list, 0, list.size()-1);

    }

Answer 1

BankAccountsBinarySearchTree tree = new BankAccountsBinarySearchTree(comparator);
createList(tree.root, (DynamicArray<BankAccount>) list);

Вы создаете новый объект BankAccountsBinarySearchTree и затем передаете объект root (который будет null ) методу createList.

Вам необходимо передать корень текущего объекта (который не показан в вашем коде) методу createList.