Java 平衡二叉搜索树

Balancing a binary search tree

提问by Neonjoe

Ok, I am trying to get a binary search tree to balance, and I know why it's not working, but I don't know how to fix it. This is what I have for my balancing methods.

好的，我正在尝试平衡二叉搜索树，我知道它为什么不起作用，但我不知道如何修复它。这就是我的平衡方法。

    public void balance(){
    if(isEmpty()){
        System.out.println("Empty Tree");
        return;
    }
    if(!isEmpty()){
        values = new Object[count()];
        index = 0;
        createAscendingArray(root);
        clear();
        balanceRecursive(0, index);
                    values = null;
    }


}

private void createAscendingArray(TreeNode<E> current){
    if(current == null)
        return;
    if(current.getLeftNode() != null)
        createAscendingArray(current.getLeftNode());
    else if(current.getRightNode() != null)
        createAscendingArray(current.getRightNode());
    values[index] = current.getData();
    index++;


}

private void balanceRecursive(int low, int high){
    if(low == high)
        return;
    else if(low > high/2)
        balanceRecursive(high/2, high);
    else if(low < high/2)
        balanceRecursive(low, high/2);  

    E insert = (E) values[(low + high)/2];
    insertItem(insert);

}

To add some clarity, index is a predefined private int variable, values is also a predefined Object[]. Root is the node at the start of my unbalanced tree. First off, I know my array is adding the values in reverse order. Right now I'm just testing with 1, 2, 3, 4, 5, 6 being added to the tree, so then my array comes out with 654321. I'm not sure how I need to place the addition of the values to my array so that it will add them in the correct ascending instead of descending order.

为了更清楚，index 是一个预定义的私有 int 变量，values 也是一个预定义的 Object[]。根是我的不平衡树开始处的节点。首先，我知道我的数组是以相反的顺序添加值。现在我只是在测试将 1, 2, 3, 4, 5, 6 添加到树中，然后我的数组出现了 654321。我不确定我需要如何将这些值添加到我的数组，以便它将以正确的升序而不是降序添加它们。

Now when I look at my code, I know that the balanceRecursive() method is never going to work for implementing the top half of the array. My issue is I don't know how to write it so that it will. I am tasked to do this with recursion, which I am not very familiar with. I could do this with iteration, but it's strictly defined I must use recursion.

现在，当我查看我的代码时，我知道 balanceRecursive() 方法永远不会用于实现数组的上半部分。我的问题是我不知道如何编写它以便它会。我的任务是用递归来做这件事，我不太熟悉。我可以用迭代来做到这一点，但严格定义我必须使用递归。

Balance is supposed to work like this: Algorithm for balance()

Balance 应该是这样工作的：Algorithm for balance()

• Check if tree is empty

• 检查树是否为空

o If it is, print “Empty Tree”

o 如果是，打印“空树”

o Return

o 返回

• If tree is not Empty

• 如果树不是空的

o Create array of Objects the size of the Tree

o 创建树大小的对象数组

o Set index to 0

o 将索引设置为 0

o Populate the array with all values in ASCENDING order (createAscendingArray())

o 用 ASCENDING 顺序的所有值填充数组 (createAscendingArray())

o Clear Tree

o 清除树

o Repopulate Tree from Object array (balanceRecursive())

o 从对象数组重新填充树 (balanceRecursive())

o Set the values array to null

o 将值数组设置为 null

(I have methods written already for count() to count the number of nodes in my tree and clear() to empty the tree)

（我已经为 count() 编写了用于计算树中节点数和 clear() 以清空树的方法）

balanceRecursive() is supposed to do the following Repopulates the Tree with the values in the values data member. These must be added in the appropriate order to create a balanced tree.

balanceRecursive() 应该执行以下操作 使用 values 数据成员中的值重新填充树。这些必须以适当的顺序添加以创建平衡树。

• Add the middle element

• This creates two sub arrays, a left and a right

• Add the middle of those sub arrays

• This creates even more sub arrays

• Keep adding middles of sub arrays until there are none

• 添加中间元素

• 这将创建两个子数组，一个左数组和一个右数组

• 添加这些子数组的中间

• 这会创建更多的子数组

• 继续添加子数组的中间，直到没有

I know for this method I am never using the larger set of sub arrays and that's the part of the recursion that I can't figure out how to implement. Any suggestions on how to clean up my recursion?

我知道对于这种方法，我从不使用更大的子数组集，这是我无法弄清楚如何实现的递归部分。关于如何清理我的递归的任何建议？

EDIT:

编辑：

I changed my createAscendingArray() to the following:

我将 createAscendingArray() 更改为以下内容：

    private void createAscendingArray(TreeNode<E> current){

    if(current == null)
        return;
    createAscendingArray(current.getLeftNode());
    values[index] = current.getData();
    index++;
    createAscendingArray(current.getRightNode());



}

That should function like an inOrder traverse of the BST am I right?

这应该像 BST 的 inOrder 遍历一样，对吗？

回答by Andy Jones

First, you don't need to copy the old tree. You can rebalance it in-place using the Stout-Warren algorithm, though admittedly that's a bit more complex than just reading out the old tree, clearing it and creating a new one.

首先，您不需要复制旧树。您可以使用Stout-Warren 算法就地重新平衡它，尽管不可否认，这比读取旧树、清除它并创建新树要复杂一些。

But as to your actual question, the recursion function you want is

但至于你的实际问题，你想要的递归函数是

private void balanceRecursive(int low, int high){

    if(low == high)
        return;

    int midpoint = (low + high)/2;

    E insert = (E) values[midpoint];
    insertItem(insert);

    balanceRecursive(midpoint+1, high);
    balanceRecursive(low, midpoint);  
}

As an aside, don't use an array of objects for values, use a List<E>so you don't need to cast to type Ewhen you read out of it.

顺便说values一句，不要使用对象数组 for ，使用 aList<E>这样你就不需要E在读取它时强制转换为类型。