Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 436
  • Last Modified:

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
Asked:
nimrodh
1 Solution
 
ntdragonCommented:
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
 
yairyCommented:
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
 
ozoCommented:
You might do a partial balance during every search operation, which can produce a good average balance at equilibrium
0
Get Certified for a Job in Cybersecurity

Want an exciting career in an emerging field? Earn your MS in Cybersecurity and get certified in ethical hacking or computer forensic investigation. WGU’s MSCSIA degree program was designed to meet the most recent U.S. Department of Homeland Security (DHS) and NSA guidelines.  

 
nimrodhAuthor 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
 
nimrodhAuthor Commented:
ozo,
how can such 'partial balance' be performed?
0
 
yairyCommented:
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
 
nimrodhAuthor 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
 
yairyCommented:
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
 
yairyCommented:
0
 
nimrodhAuthor Commented:
not exactly a BST but very close to it.
I especially like the randomized version.
thx, yair.
0
 
yairyCommented:
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.

Join & Write a Comment

Featured Post

Turn Raw Data into a Real Career

There’s a growing demand for qualified analysts who can make sense of Big Data. With an MS in Data Analytics, you can become the data mining, management, mapping, and munging expert that today’s leading corporations desperately need.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now