- Forum
- General C++ Programming
- How to Balance a Binary Search Tree?
How to Balance a Binary Search Tree?
I suppose the simplest would be to find the median, and use that as the root. The worst case would be the average case, which would be linear time, which is not that terrible.
Linear time IS the worst case of a BST, regardless of root choice. With the median as root, you still risk n/2 complexity of basic functions.
The easiest (but completely inefficient) way to balance a BST is to check for imbalance after a certain number of additions and then deleting one of the (non-leaf) nodes of the longest tree and then reinserting it. The advantage is that you only need "insert" and "delete" operations, which are needed anyway and use very easy decision rules. The efficient balancing technique is quite complex (and so are self-balancing trees).
The easiest (but completely inefficient) way to balance a BST is to check for imbalance after a certain number of additions and then deleting one of the (non-leaf) nodes of the longest tree and then reinserting it. The advantage is that you only need "insert" and "delete" operations, which are needed anyway and use very easy decision rules. The efficient balancing technique is quite complex (and so are self-balancing trees).
That's what I was trying to say. Finding the median and rebuilding the tree will always be the worst case, which will be linear time, which as far as simple algorithms, is not terrible. Not optimal, but it will finish before the end of time.
From what I read from the question, was to balance a tree that already exists, not one that is being added to. For balancing a tree once, I believe rebuilding the tree from the median would be the simplest algorithm. Then call that function recursively to add the next node (again finding the median for numbers below the root, and the median for the numbers above the root)
I should have been more clear.
From what I read from the question, was to balance a tree that already exists, not one that is being added to. For balancing a tree once, I believe rebuilding the tree from the median would be the simplest algorithm. Then call that function recursively to add the next node (again finding the median for numbers below the root, and the median for the numbers above the root)
I should have been more clear.
Linear time for a data structure is pretty bad, since it's pretty much the upper bound for basic operations.
Even with a pre-made tree, I think it's easier to iteratively remove and reinsert the nodes at the root of the skewed branch. Both ways work though. The median-search method can even be more efficient depending on the degree of imbalance.
Even with a pre-made tree, I think it's easier to iteratively remove and reinsert the nodes at the root of the skewed branch. Both ways work though. The median-search method can even be more efficient depending on the degree of imbalance.
Yes, we suppose that we have an existing binary search tree. I was tasked to make a function that can balance a tree when called. I'm still struggling how to do it. I'll try your suggestions though. Thanks.
See "http://en.wikipedia.org/wiki/Balanced_tree" and references there. The wikipedia site on the red-black tree has some C code, but is rather complicated. The AVL tree is quiet easy to implement, but on wikipedia there is no code to it. The splay tree is also rather easy to implement but has not all the guarantees, the other trees have. (the tree might not be properly balanced.) There's some code to it as well.
Last edited on
Topic archived. No new replies allowed.