balance binary tree

This is a discussion on balance binary tree within the C++ Programming forums, part of the General Programming Boards category; I found this code on the net, but it doesn't work. Can someone provide me with some guidance. i created ...

  1. #1
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589

    Question balance binary tree

    I found this code on the net, but it doesn't work.
    Can someone provide me with some guidance.
    i created an accending sorted array, then executed the following code. Is this the most efficient way to do this? Is this a valid way to do this?

    Code:
    // Assuming array ranges from [0..arraySize-1]
    GetFromOrderedArray(0,arraySize-1)
      .
      .
    void GetFromOrderedArray(int lowBound,int highBound)
    {
      if (highBound < lowBound) return;
      middlePos = lowBound+(highBound-lowBound)/2
      // middlePos is now at the element in the middle
      // between lowBound and highBound, so we just add
      // it to the tree
    
      AddElement ( theOrderedArray[middlePos] )
    
      // Pick the middle one "to the left"
      AddFromOrderedArray(lowBound,middlePos-1)
    
      // Pick the middle one "to the right"
      AddFromOrderedArray(middlePos+1,highBound)
    }
    Above code found from this link

    I inserted test data to trace (no compiler available).
    An array

    - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - <-index
    --------------------------------
    |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |9 | <-Data
    --------------------------------

    In my trace it inserts 5,2,1,7,8,9 in that order.
    On my compile earlier at home it only inserted 2.

    more trace details

    recursive calls |Hi|Low| middlePos <-column labels
    start|8|0|4|
    rc1|3|0|1
    rc2|1|0|0
    nrc1|8|5|6
    nrc2|8|7|7
    nrc3|8|8|8
    nrc4|8|9|
    Last edited by xviddivxoggmp3; 12-05-2003 at 11:02 PM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    Advice: Don't download code that doesn't work.

    Hell, don't download code at all. Horrible way to'learn'.

  3. #3
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589

    i figured it out.

    It took me a while to fix it, but I did.
    I was advised once.
    Do not reinvent the wheel.
    and also
    reuse, reuse, reuse.
    isn't code made for people to interpret and alter to fit their needs.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  4. #4
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    Generally, code made for people to reuse works.

  5. #5
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Besides, std::set or std::map are already implemented as self-balancing binary trees, so use them. They aren't perfectly balanced, of course, but a worst-case node is at most twice as far from the root as a best-case.

    There is less ability to do various traversal types, but it's much faster.

    It's also faster on large sets, because your algorithm requires presorting the data -- self-balanced trees don't require a presort.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  6. #6
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    Besides, std::set or std::map are already implemented as self-balancing binary trees, so use them. They aren't perfectly balanced, of course, but a worst-case node is at most twice as far from the root as a best-case.
    Is there a website you recommend that references the set and map?
    I've never heard of that before.
    I will search google, but if you have any good indepth references I would very much appreciate it.
    Thanks.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,592
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

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

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