Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Balancing a binary search tree

Posted on 2000-04-06
11
Medium Priority
?
422 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

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 180 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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
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 opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

730 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