平衡二叉搜索树 [英] Balancing a binary search tree

问题描述

好吧，我试图让一个二叉搜索树平衡了，我知道为什么它不工作，但我不知道如何解决它。这是我对我的平衡方法。

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);

}

要增加一些透明度，指数pdefined私人int变量，值$ P $也是一个predefined对象[]。根是在我不平衡树的开始节点。首先，我知道我的阵列，以相反的顺序添加值。现在我只用1，2，3，4，5，被添加到树6测试，所以后来我阵列出来有654321我不知道我该怎么需要将加入值来我的阵列，因此它会在正确的上升，而不是递减顺序添加它们。

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.

现在，当我看着我的code，我知道balanceRecursive（）方法是永远不会实现阵列的上半部分的工作。我的问题是我不知道该怎么写它，这样它会。我任务是递归做到这一点，对此我不是很熟悉。我可以反复这样做，但它严格界定我必须用递归。

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.

天平应该像这样的工作：
算法平衡（）

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

• 检查树为空

o如果是，打印空树

O返回

• 如果树不为空

o创建对象的数组树的大小

o Create array of Objects the size of the Tree

Ø设置指数为0

Ø填充升序排列的所有值阵列（createAscendingArray（））

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

0清零树

Ø重新填充树从Object数组（balanceRecursive（））

o Repopulate Tree from Object array (balanceRecursive())

o将值数组为null

o Set the values array to null

（我已经写了数（）方法来计算在我的树和节点的数量明显的（）为空树）

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

balanceRecursive（）是应该做到以下几点
重新填充与值数据成员的值的树。这些必须在适当的以创造一个平衡树添加。

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.

• 添加中间元素

• Add the middle element

这将创建两个子阵列，左，右

This creates two sub arrays, a left and a right

添加这些子阵列中间

这创造更加子阵列

请添加子阵列中段，直到有没有

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?

编辑：

我改变了我的createAscendingArray（）以下内容：

I changed my createAscendingArray() to the following:

    private void createAscendingArray(TreeNode<E> current){

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



}

这是应该的功能就跟BST的序遍历对吗？

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

推荐答案

首先，你并不需要复制的老树。您可以使用斯托特沃伦算法就地平衡它，但无可否认这是一个有点不仅仅是读出老树，清除它，并创建一个新的更复杂的。

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.

但作为你的实际问题，你想要的递归函数

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);  
}

顺便说一句，不要使用对象的数组值，使用列表＆LT; E＆GT; 所以你不需要投，当你读出它来输入电子。

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 E when you read out of it.

这篇关于平衡二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！