Solved

# Balancing a binary search tree

Posted on 2000-04-06
416 Views
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
Question by:nimrodh
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 1

Expert Comment

ID: 2691333
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

LVL 2

Expert Comment

ID: 2702416
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

LVL 84

Expert Comment

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

Author Comment

ID: 2703356
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 Comment

ID: 2703360
ozo,
how can such 'partial balance' be performed?
0

LVL 2

Expert Comment

ID: 2704285
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 Comment

ID: 2704488
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

LVL 2

Expert Comment

ID: 2704713
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

LVL 2

Accepted Solution

yairy earned 60 total points
ID: 2710197
0

Author Comment

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

LVL 2

Expert Comment

ID: 2711875
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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

### Suggested Solutions

Trouble linking program with -lcrypt 3 167
Super Scope, DHCP 5 102
Is it possible to delete files one by one rather than the whole? 15 64
Excel formula to calculate ID # 4 44
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoâ€¦
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to useâ€¦
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
###### Suggested Courses
Course of the Month2 days, 3 hours left to enroll