Solved

Balancing a binary search tree

Posted on 2000-04-06
11
416 Views
Last Modified: 2010-04-15
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
Comment
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
  • Learn & ask questions
11 Comments
 
LVL 1

Expert Comment

by:ntdragon
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

by:yairy
ID: 2702416
can you be a bit clearer ?

You want to balance the tree WITHOUT
reading all its nodes ?

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

by:ozo
ID: 2702474
You might do a partial balance during every search operation, which can produce a good average balance at equilibrium
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:nimrodh
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

by:nimrodh
ID: 2703360
ozo,
how can such 'partial balance' be performed?
0
 
LVL 2

Expert Comment

by:yairy
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

by:nimrodh
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

by:yairy
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

by:
yairy earned 60 total points
ID: 2710197
0
 

Author Comment

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

Expert Comment

by:yairy
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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
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.

710 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question