Thread: trouble balancing an unbalanced binary tree

  1. #1
    Registered User
    Join Date
    Nov 2001

    trouble balancing an unbalanced binary tree

    does anyone have now any good websites that have a page devoted to balancing an unbalanced tree, i found one myself but its in c++ only and i cant find any others.

    also if anyone has any advice, (dont want the code), that would be just as good

    heres what i think i should do

    1) put the node pointers into an array
    2) sort the array
    3) destroy the root of the tree
    4) find the middle of the array
    5) do some recursion and keep finding the middle until all the remaining pointers are added to the new tree

    when i tried to read the addresses in they sorted themselves, but not the information contained within the addresses, i used an in order traversal

    my information is all characters so i want the lowest letters at the start of the array

    heres what i got so far (not much i'm afraid)

    void balanceTree(PTRnode* &root, datatype &data, int &numberCDS)
    PTRnode *tempnode[300]; //temporary storage for node addresses
    static int index = 0;

    tempnode[index]=inOrderTraversal(root, data); //call to function that sorts in Order
    index++; //increment index by 1


    PTRnode* inOrderTraversal(PTRnode* &root, datatype &data)
    if(root->left!=NULL) //check if root->left is not equal to NULL
    inOrderTraversal(root->left, data); //call function and go left
    return root; //return the roots contents
    if(root->right!=NULL) //check if root->right is not equal to NULL
    inOrderTraversal(root->right, data); //call function and go right

    i hope you can make sense out of all that

  2. #2
    Registered User
    Join Date
    Sep 2001
    Well, first off you need to fix up your inOrderTraversal() to actually write the array. There's a couple ways to do this, but here's a prototype that I think works well...
    int inOrderTraversal (PTRnode * root, PTRnode * array);
    // Copies the elements of root's tree into array.
    // Returns the number of elements copied.
    However, the code you have here appears to have a lot of incorrect syntax, and I fail to understand what the data parameter is for.
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Registered User
    Join Date
    Dec 2001
    Here is some info on a balanced binary tree aka AVL tree.

    More sites can be found at

    What you have is a good algo for balancing an unbalanced tree, it would be inefficent to call that everytime the tree is changed. It would be better to keep the tree balanced at all times by taking care of it during the inserts and deletes

  4. #4
    Join Date
    Aug 2001
    Groningen (NL)
    There are many kinds of balanced trees. For example AVL trees, Splay trees, etc. Google gives many results when searching for these things.

  5. #5
    In database code, in order to balance a tree (shorter sort times) you essentially "roll" your tree left or right until it is once again balanced.

    This works with any tree, b, b+, b*, n-way, k-way, etc.

    I would recommend you find a book on database file structures-- usually in your college bookstore. It will explain all of this. Don't be mislead by the title referring to 'file structures'. Back when most of this stuff was figured out, the program usually had to work off disk because there wasn't enough RAM to hold everything.

    Principles are the same.


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM