• Status: Solved
• Priority: Medium
• Security: Public
• Views: 438

Balancing a binary search tree

Is there a way to balance a binary search tree (not AVL tree, not red-black tree or anything other then BST) without reading all its content and then rebuilding it from the sorted list of values ?
0
nimrodh
1 Solution

Commented:
there is a way but not really a normal one that the problem with binary search tree

that way there are tree's like 2-3 tree and the others you talked about

you balance a binary search tree you"ll have to rebuild it each time or fix it
but i think it will worser then to use a not balance one
so if you want a balance tree use 2-3 tree <all the opertaion with it are in log(n)>
0

Commented:
can you be a bit clearer ?

You want to balance the tree WITHOUT

I don't think there is a way.

Maybe you ment to read it in inorder
(go left, visit, go right)
and get a sorted list.
then rebuilding the tree from the middle items to the borders.

example:
1
2
3
4
5
6
7

will give us after inorder:
1 2 3 4 5 6 7
then we will insert the items in the following order
4 3 5 2 6 1 7
and get:

4
3     6
2 5   1 7

0

Commented:
You might do a partial balance during every search operation, which can produce a good average balance at equilibrium
0

Author Commented:
I do'nt mind reading all the nodes but not on every insert.
I was looking for a way to insert nodes in a way that will preserve a reasonable tree hight (say c*log(n)) in the average case.
using the rebuild method (I ruled out in my question) will make the insert operation cost O(n) time and O(n) space.
0

Author Commented:
ozo,
how can such 'partial balance' be performed?
0

Commented:
There iis a structure that is called Treap.
Treap has the qualities of a Bin-tree
AND the qualities of a heap.

you insert a new item with a random number
that is its Priority.

You find its poistion like a regular  Bin-Tree and then
"correct" the nodes that the random numbers
attached to the items will remain in a heap structure.

I saw some metirial on the web but nothing too clear.

Another structure will be Skips lists.

Both of them use probability and known to have limited
hight of O(ln(n))

Yair
0

Author Commented:
yair,

I agree that skip list seems the best data structure for this purpose.
but I am looking for a BST algorithm for educational purposes (I'm teaching a programming lab course).
0

Commented:
treaps is really lovely and very simple.

one can prove that if you scramble
the items before insertion you odd to get a fairly balanced tree.

I'll try to look up the treaps algs for
you.

Yair
0

Commented:
0

Author Commented:
not exactly a BST but very close to it.
I especially like the randomized version.
thx, yair.
0

Commented:
You might "invent" a proper methode yourself.
For example, For every walk in probability of
1/n, reorder the subtree you are in.

I don't think there is a "perfect" solution,
If you want to gain you need to pay.

Yair
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.