Search binary tree balancing

Question

Ok, I'm trying to get a binary search tree to balance, and I know why it doesn't work, 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, the index is a predefined private variable int, the values ​​are also a predefined object []. Root is the node at the beginning of my unbalanced tree. Firstly, I know that my array adds values ​​in reverse order. Right now, I'm just testing with the addition of 1, 2, 3, 4, 5, 6 to the tree, so my array comes out with 654321. I'm not sure how I need to add values ​​to my array so that it adds them to the correct upstream, and not in descending order.

Now, when I look at my code, I know that the balanceRecursive () method will never work to implement the upper half of the array. My problem is that I do not know how to write it so that it is. I have been instructed to do this with recursion, which I am not very familiar with. I could do it through iteration, but it is strictly defined. I have to use recursion.

Balance should work as follows: Balance Algorithm ()

• Check if the tree is empty.

o If so, type "Empty Tree"

o Return

• If the tree is not empty>

o Create an array of objects, tree size

o Set the index to 0

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

o Clean the tree

o Move a tree from an array of objects (balanceRecursive ())

o Set the array of values ​​to null

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

balanceRecursive () should do the following Returns a tree with the values ​​in the value data element. They must be added in the proper order to create a balanced tree.

• Add middle element

• This creates two auxiliary arrays: left and right

• Add the middle of these helper arrays

• This creates even more sub-matrices.

• Continue to add the middle of the auxiliary arrays until they are gone

I know that for this method I never use a large set of helper arrays, and that is part of the recursion that I cannot figure out how to implement. Any suggestions on clearing my recursion?

EDIT:

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

This should function as an inOrder trace from BST, if I am right?

Answer 1

Firstly, you do not need to copy the old tree. You can rebalance it in place using the Stout-Warren algorithm, although admittedly this is a bit more complicated than just reading the old tree, clearing it, and creating a new one.

But as for your actual question, you need a recursion function

 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 List<E> , so you don’t need to specify type E when you read it.

Answer 2

Balancing is performed when inserting and deleting: see Balancing trees .