Java

Question

我正在尝试在Java中编写一个平衡二叉树的方法，描述如下：

... write an inorder traversal of the tree to an array and then use a recursive method (much like binary search) to insert the middle element of the array as the root, and then build balanced left and right subtrees.

但是，我对如何一起完成这一切感到困惑。到目前为止，我已经尝试了多种方法，但没有任何效果。

我也已经有了一个 inOrder 迭代器，它 returns 是树中所有元素的 ArrayList，所以这已经涵盖了。

这是我目前正在构建的内容：

public void rebalance()
{
    Iterator<T> it = iteratorInOrder();
    List<T> list = new ArrayList<>();

    while (it.hasNext())
    {
        list.add(it.next());
    }
    balanceRecursive( );
}

private void balanceRecursive( )
{
    //something here
}

然后我在 add/remove 元素方法的末尾简单地添加了这个：

if ((getHeight() - getMinHeight()) > 5)
            rebalance();

那么，我该怎么做呢？

Answer 1

在一棵平衡树中，左右子树的大小最多相差1个元素。给定一个排序数组 - 由你的 inorder-traversal 生成 - 这变得非常简单。基本思想是构建一棵实际的树，它等于二分搜索隐式遍历的树。从数组的中间元素作为根开始，中间左边的子数组的中间元素成为左边的child，右边的模式相同child。根据数组的左半部分，以左 child 为根构建子树，右子树也是如此。

//lower and upper are the INCLUSIVE bounds of the sublist, from which the tree should be built
Node<T> buildRecursively(int lower , int upper , List<T> elements){
    //no more nodes can be produced on this path
    if(lower > upper)
        return null;

    //build node from the middle-element of the elements
    int middle = (lower + upper) / 2;
    Node<T> result = new Node<>(elements.get(middle));

    //build left and right child for the according pieces of the array/list
    result.setLeftChild(buildRecursively(lower , middle - 1 , elements);
    result.setRightChild(buildRecursively(middle + 1 , upper , elements);

    return result;
}

//build entire tree:
Node<T> root = buildRecursively(0 , elements.size() - 1 , elements);

对于实际的数组，它看起来像这样：

             sorted ascending--------->
                         4
                2                6
             1     3          5     7
indices:     0  1  2     3    4  5  6

Answer 2

构建一个以中间数组元素为值的节点。
递归地将(1)应用于数组的左侧部分，并将如此构造的节点设置为根节点的左子节点。
将(1)应用于数组的右侧部分，递归，并将如此构造的节点设置为根节点的右子节点。

Answer 3

一旦你有了 List 按顺序遍历，这就变得相对简单了。 sublist 操作意味着您甚至不需要传递索引：

Node<T> buildBalancedTree(List<T> values) {
    if (values.isEmpty()) {
        return Node.NULL;
    } else {
        int middle = values.size() / 2;
        Node node = new Node(values.get(middle));
        node.setLeft(buildBalancedTree(values.subList(0, middle)));
        node.setRight(buildBalancedTree(values.subList(middle + 1, values.size())));
        return node;
    }
}

我假设你有一个 Node.NULL 来表示空子树而不是 'null' 因为你应该:-)

因此您的再平衡方法将类似于：

root = buildBalancedTree(root.getListOfValuesInOrder());

Java - 用 "Brute Force" 平衡二叉树

Java - Balance a Binary Tree with "Brute Force"

algorithm

tree

recursion

binary-search-tree