Thread: btree balancing

  1. #1
    Registered User
    Join Date
    Nov 2001

    btree balancing

    I came to the realization that unbalanced btrees are not much more efficient than linked lists. So I've been mulling over a balancing algorithm for them and I was looking for suggestions.

    I will use the following terminology:
    node - entry in the tree, has 2 children, left child and right child
    leaf - a node that has two null pointers for children
    root - first node in list
    distance - number of nodes in the path from one node to another, minus one
    sub tree - a tree extending from any node to it's decendents (that node is the root in the sub tree)
    full tree - a tree in which all nodes are either leaves or have 2 non-null children and the distance from the root to any leaf is the same

    Which child is greater than, less than is irrelevant. Here is what I have so far:

    1. take the root and one of it's children and feed this back into the tree, using the root's other child as the new root.
    problems: this will only balance the tree if the number of entries in the old root's left child's sub tree were close to the number of entries in the old root's right child's sub tree (wow, good luck understanding that)
    2. find the mean value of the entries in the tree and make this a root in a temporary tree. Take the entries from the first tree, and put them in the temporary tree, then copy the temp tree back to the original
    problems: this will only approximately balance the tree if there are no large gaps between the values of the nodes in the tree, otherwise one side will be top heavy

    geez, I haven't come up with much, and none of it's very good. Neither of these even come close to giving me a full tree, which would be ideal. The other problem I've come to is deciding when to balance. Now if I had a way to balance that would give me a full tree I imagine I could balance every time I created old_distance^2 nodes, where old_distance is the maximum distance after the last balance. Well I'm confusing myself now and I should probably put some more thought into this, but any help would be greatly appreciated. Thanks


  2. #2
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    You might want to do a search for AVL or red black trees on google. Here's a random link.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree/Recursion
    By kwikness in forum C Programming
    Replies: 8
    Last Post: 12-14-2007, 10:01 AM
  2. Balancing a tree (AVL Tree)
    By BoneXXX in forum C Programming
    Replies: 20
    Last Post: 04-12-2007, 01:15 PM
  3. AVL tree balancing problem
    By sweets in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2004, 12:17 PM
  4. printing a btree using recursion
    By agerealm in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2003, 08:57 AM
  5. trouble balancing an unbalanced binary tree
    By korbitz in forum C Programming
    Replies: 4
    Last Post: 01-04-2002, 08:19 AM