Jump to content

Balanced Binary Tree

- - - - -

This topic has been archived. This means that you cannot reply to this topic.
1 reply to this topic

#1
jendana89

jendana89

    Newbie

  • Members
  • Pip
  • 2 posts
Hello -

I was hoping someone could help me with an assignment I am working on to create a balanced binary search tree. Earlier in the course we had an assignment to take input from a user (integer) and then create a node, and add the node to the tree. This worked great, except the tree(s) were extremely unbalanced. To do this current assignment I was hoping I could just take the code I used before and change it so that it will now created a balanced tree. I have an algorithm going to do this, but I am still pretty confused.

The code/algorithm I have so far is:

public IntBTNode2 addNode (IntBTNode2 node, int value) {
if (node == null) {
node = new IntBTNode2 (value);

// if number of nodes in left subtree == number of nodes in right subtree
// treeSize(IntBTNode2) tells the number of nodes in a tree, in this case the right and left subtrees
if (root.treeSize(left) == root.treeSize(right)) {
// if value <= root of tree
if (value <= root.data) {
// insert value into left subtree - create new tree (t')
// replace left subtree with t'
}
}

// value > root of tree
// the new root is value:
// new left subtree will be the result of inserting root into left subtree
// no new right subtree
// the new root is the leftmost node in the right subtree
// if number of nodes in left subtree == number of nodes in right subtree + 1
}
else {
// if value is < value in root
if (value < node.data) {
node.left = addNode (node.left, value);
}
// if value is < value in root
// etc etc etc for algorithm
else if (value > node.data) {
node.right = addNode (node.right, value);
}
else
return null;
}

return(node);
}

Could you help me with simpler ideas of how to created a balanced binary search tree or show me how to better understand my algorithm?

#2
WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderators
  • 16,831 posts
AVL tree - Wikipedia, the free encyclopedia
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog