binary tree balance problem

This is a discussion on binary tree balance problem within the C++ Programming forums, part of the General Programming Boards category; i need a optimal tree balancing algorithm. for example: Code: 12 / \ 9 20 / \ / \ 6 ...

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    1

    Exclamation binary tree balance problem

    i need a optimal tree balancing algorithm.
    for example:
    Code:
                            12
                   /                   \
                  9                  20
                /   \            /             \
              6    10      16                 25
                               \                   /
                              17                22
    a)if add 30?
    b)if add 28?
    c)if add 14?
    d)if add 18?
    Last edited by Salem; 08-16-2006 at 10:45 AM. Reason: Tried to code tag the tree, but it didn't help

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Optimal is expensive. You're looking at a global rebalance of the tree after every modification. Do a google search for the DSW algorithm. If you're willing to live with "pretty darn close", the AVL balancing scheme is as good as it gets without really hurting performance.
    My best code is written with the delete key.

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    I'm sure modesty prevented the posting of this link. Even if you don't use any of the code, the detailed explanations sure taught me a lot about different ways to balance a tree. I think my personal favorite is the red-black tree.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Man, that's, like, 100+ pages of pure confuzzledness I'll be putting my brain cells on it when I have the time, but I don't think we all should expect the OP to.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,069
    It's so confuzzled, I'm not even sure Prelude knows what she wrote.
    Sent from my iPadŽ

  6. #6
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by jafet
    Man, that's, like, 100+ pages of pure confuzzledness I'll be putting my brain cells on it when I have the time, but I don't think we all should expect the OP to.
    Yeah, I had to put a lot of brain cells on it, reading and re-reading paragraphs over and over. I'm not saying that it's a bad read; the information is just very densely packed, and my mental decompression algorithm wasn't quite up to it in a few sections.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary tree problem
    By moddinati in forum C++ Programming
    Replies: 8
    Last Post: 06-19-2008, 05:05 PM
  2. Binary Search Tree scope? problem
    By tms43 in forum C++ Programming
    Replies: 5
    Last Post: 11-01-2006, 09:13 PM
  3. binary tree problem
    By spank in forum C Programming
    Replies: 4
    Last Post: 04-24-2006, 05:27 AM
  4. problem in storing data in a binary search tree
    By alavardi in forum C Programming
    Replies: 5
    Last Post: 02-13-2005, 02:20 PM
  5. Problem with binary search tree :(
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 05-01-2002, 10:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21