4 Replies - 2192 Views - Last Post: 26 May 2013 - 04:57 AM

#1 NecroWinter   User is offline

  • D.I.C Regular

Reputation: 38
  • View blog
  • Posts: 348
  • Joined: 21-October 11

Straight forward question, WHEN do you balance a BST?

Posted 25 May 2013 - 08:10 PM

Im working on a project now, and I have a BST that works, and I have a function that balances the tree. I was told that you shouldnt balance after every insert and delete because its not really necessary.

I dont really know when to do it currently, what is the most efficient way?
Is This A Good Question/Topic? 0
  • +

Replies To: Straight forward question, WHEN do you balance a BST?

#2 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,861
  • Joined: 27-December 08

Re: Straight forward question, WHEN do you balance a BST?

Posted 25 May 2013 - 08:17 PM

Depends on the type of balanced BST. Look into AVL and Red-Black Trees. They have different rules for balancing.
Was This Post Helpful? 1
  • +
  • -

#3 NecroWinter   User is offline

  • D.I.C Regular

Reputation: 38
  • View blog
  • Posts: 348
  • Joined: 21-October 11

Re: Straight forward question, WHEN do you balance a BST?

Posted 25 May 2013 - 08:37 PM

Its just a normal BST. Basically, I take the user input, and input it into the tree based on whether the item is bigger or smaller than the current node, much like you'd expect.

the balancing function that I have now just takes the middle item and inputs it into the tree, and loops this process

so with that being said, its just a normal BST. When do you think the best time to balance it would be?

They say its not always good to balance after every insert and delete, and I was thinking that I could balance it before a search or any kind of tree traversal, but the point of a BST is to speed up the process and it just seems like thats not the best time to do it. I've heard some people do it after so many inputs/deletes but I havent been able to find a consensus.

This post has been edited by NecroWinter: 25 May 2013 - 08:41 PM

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,861
  • Joined: 27-December 08

Re: Straight forward question, WHEN do you balance a BST?

Posted 25 May 2013 - 09:05 PM

Quote

Its just a normal BST

I'm not trying to be argumentative, but the moment you add in balancing, it is no longer a normal BST. It becomes a balanced binary search tree. Thus, it makes sense to look at what is already out there. Don't blow off what's out there because it isn't explicitly specified. The whole point of studying data structures is to apply the bits (no pun intended) and pieces that fit your problem as appropriate.

So again, look at the AVL and Red-Black Trees. They provide good schemes to balance your tree. The AVL Tree is (imo) easier to implement and provides a better balance. It is more efficient with searching. The Red-Black Trees are a little more relaxed on when to balance, and thus are more efficient for insertion and deletion. If you want to base an approach off these two trees, that's where I'd start. It really depends on what you're going after. Both guarantee O(log(n)) insertion, deletion, and search time though.
Was This Post Helpful? 1
  • +
  • -

#5 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7505
  • View blog
  • Posts: 15,553
  • Joined: 16-October 07

Re: Straight forward question, WHEN do you balance a BST?

Posted 26 May 2013 - 04:57 AM

View Postmacosxnerd101, on 26 May 2013 - 12:05 AM, said:

Quote

Its just a normal BST

I'm not trying to be argumentative, but the moment you add in balancing, it is no longer a normal BST.


Huh?

To be clear, there are binary trees, or just trees, that implement balancing as part of their standard processing. In these cases, there are often extra structural considerations to assist the process. The balancing process usually happens every insert.

However, there's nothing that says you can't take a simple old BST and try to restructure the thing to make it more balanced. This, it appears, is what the OP is talking about.

When you do manually balance a simple BST? The answer, I suppose, it as little as possible. :P

Manually balancing an unbalanced tree from ground zero is worst case scenario, processing wise. However, if you intend to only do it once, then it might be a viable choice.

If you're asking the question, do take a look at the auto balanced ADTs noted. They're all rather clever and some of them aren't horribly complex. (Many, well, are.)
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1