How do you update node sizes in a BST balancing algorithm?

Derpman5000 0
Viewed 12
public void balance() {
    LinkedList<Node> tree = new LinkedList<Node>();
    sortTree(tree, root);
root = balanceTree(tree, 0, (size() - 1));
}

private Node balanceTree(LinkedList<Node> tree, int first, int last) {
    if (first > last) {
        return null;
    }
    int temp = first + last;
    int mid = temp / 2;
    if (temp % 2 == 1) {
        mid++;
    }
    Node midNode = tree.get(mid);
    midNode.left = balanceTree(tree, first, mid - 1);
    midNode.right = balanceTree(tree, mid + 1, last);
    return midNode;
}

private void sortTree(LinkedList<Node> tree, Node n) {
    if (n == null) {
        return;
    }
    sortTree(tree, n.left);
    tree.add(n);
    sortTree(tree, n.right);
}

This properly balances BST's but it does not update the nodes sizes, can I get some help on where I should be trying to update the node sizes?

binary-search-tree java
1 Answers

Assuming your Node has a size member, you can add a line in this block:

midNode.left = balanceTree(tree, first, mid - 1);
midNode.right = balanceTree(tree, mid + 1, last);
midNode.size = (midNode.left == null ? 0 : midNode.left.size)
             + (midNode.right == null ? 0 : midNode.right.size)
             + 1;
return midNode;

Unrelated to your question, but your algorithm is inefficient, as the get method on a linked list has O(n) time complexity, making the overall process O(n²). This would however work fine if the input were an array(list) that supports direct access by index in constant time.

If it has to work efficiently with a linked list, you'll need an entirely different algorithm, not the divide-and-conquer style of algorithm that you have here.

trincot0
Related