|
|
I had to implement one for a project I'm working on because it's in C, and C doesn't have anything like a binary tree in its standard RTL.
|
|
|
|
|
|
The 90's have just called me on the phone and told me they want this survey question back.
|
|
|
|
|
Just look up how to do it in for example Cormen, Leiserson, Rivest, Stein - Introduction to Algorithms
I never believed in memorization. Why bother. Isn't that one of the reasons we have computers and books i.e. to remember things for us? If you're interested in the theory sure learn the theory and when you have to apply it years later you'll have no trouble re-learning it as necessary. There are countless algorithms and theories. Are we to memorize each one and forbidden to re-open our texts? - Cheerio
|
|
|
|
|
Honestly I can't even imagine looking it up. I think the only right answer, in this decade, is to stop what you're doing and reassess the choices you've made in life (and language, and runtime library selection) that led you to implementing your own binary tree.
Unless maybe you're one of a select few individuals working on a collection library for a new language/runtime..
|
|
|
|
|
I just implemented one... why? Because C doesn't have one built-in.
|
|
|
|
|
Fair enough -- did you pause first, to reassess your choice of language and runtime libraries? (kidding)
But seriously, is there really no suitable open-source library for collections and basic data-structures, for C? (I honestly don't know, just surprised if there's not.)
Once upon a time I remember having to build crude List, Vector and Hashtable "classes" for a C/C++ codebase that couldn't use C++ exceptions (therefore no STL etc). But that was almost 20 years ago.
I suppose STL may have eliminated much of the incentive for someone to build a competing library just for low-level C programmers. 
|
|
|
|
|
there's nothing like the STL or Boost for C. but there's certainly plenty of open-source code. but for this it was easier to write my own, rather than fight with introducing a new library into the build/delivery system.
|
|
|
|
|
I can certainly appreciate that. And you'd probably want to write much of the same test code, either way.. would not be good to introduce a buggy/leaky 3p collection class into a codebase, just to save a few hours work.
|
|
|
|
|
in the Long Ago Time, it might be a tad difficult. While I have no problem with binary search trees (I use generalized trees more often), I don't know the algorithm for converting an arbitrary BST to a balanced one. While I can come up with an algorithm on my own (the back part of my brain is working on one now), I'd probably look the algorithm up and go from there.
I think any honest developer who's been out of school more than five years would say the same. That sort of minutiae goes by the wayside if you don't use it regularly.
Software Zen: delete this;
|
|
|
|
|
Google, Microsoft, Facebook, Amazon.
|
|
|
|
|
This sort of stuff is only needed in ancient languages, probably a crummy C derivative and still with the 0-based indexes!
If you offered me a job in a language which didn't have something far better (even JavaScript has decent enough dictionaries!) you'd get an instant rejection, and be lucky if it was polite.
Pete Lomax
|
|
|
|
|
But you still drink Jolt cola, I hope? 
Anything that is unrelated to elephants is irrelephant
Anonymous
-
The problem with quotes on the internet is that you can never tell if they're genuine
Winston Churchill, 1944
-
Never argue with a fool. Onlookers may not be able to tell the difference.
Mark Twain
|
|
|
|
|
I think one should avoid offending anyone and also consider "non-binary" options.
| Ravings en masse^ |
|---|
| "The difference between genius and stupidity is that genius has its limits." - Albert Einstein | | "If you are searching for perfection in others, then you seek disappointment. If you seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
Waaayyy back on 1996:01:08 I wrote some code for working with both linked lists and binary search trees (dynamically allocated) -- in C -- and it can convert between the two structures. A BST is not normally balanced, nor can it self-balance, but if the application chooses, it can balance a BST by converting to a linked list and back, because that produces a balanced BST.
I'm of the opinion that if your application's performance is degraded by using a BST which is unbalanced, then it should not be using a BST, and another structure might be a better choice -- maybe a hash table or similar. (A Decimal Search Tree?) Balancing -- particularly self-balancing -- a BST seems like a waste of resources, especially if you're already having issues with performance.
P.S. The correct answer is "no" because it's actually a bad question. There is no way to implement a way to balance any BST. The question doesn't even limit the task to balancing dynamically-allocated BSTs.
modified 7-Jun-21 11:04am.
|
|
|
|
|
... two years ago I was looking for a job and practicing interview questions, including self-balanced trees.
|
|
|
|
|
Do I get to look up the definitions?
I am confident I could code it, but I would need to do research to understand the exact definitions first.
|
|
|
|
|
|
Exactly! I can always look that up. Last time I wrote one was in undergrad.
"Computer games don't affect kids; I mean if Pac-Man affected us as kids, we'd all be running around in darkened rooms, munching magic pills and listening to repetitive electronic music."
-- Marcus Brigstocke, British Comedian
|
|
|
|
|
|
I have my suspicions of who created this one....
|
|
|
|
|
I'm absolutely 100% positive I couldn't.
Lucky for me I never needed it, but not a day goes by that I'm not afraid I'll have to do this and be exposed for the bad programmer that I apparently am 
Edit:
Should anyone ever need this for whatever reason (those reasons would probably be evil), the first Google search result has your back: Convert a normal BST to Balanced BST - GeeksforGeeks[^] 
I'll sleep a lot easier tonight, knowing the code is readily available 
|
|
|
|
|
Sander Rossel wrote: I'll sleep a lot easier tonight, knowing the code is readily available
Someone famous told once: Quote: I don't learn something I can find in my pocket.
M.D.V. 
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
Rating helpful answers is nice, but saying thanks can be even nicer.
|
|
|
|
|
and I will find a solution, don't give me academic tests when I've been out of University 10 years ago.
Besides, you can call them Fnord Tree and R'lyeh Tree for what is worth.
GCS d--(d+) s-/++ a C++++ U+++ P- L+@ E-- W++ N+ o+ K- w+++ O? M-- V? PS+ PE- Y+ PGP t+ 5? X R+++ tv-- b+(+++) DI+++ D++ G e++ h--- r+++ y+++* Weapons extension: ma- k++ F+2 X
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
