BST (yes, that's binary search tree)
Quote:
> How can I implement a balanced BST in scheme. I'm guessing using
BST: binary search tree or balanced search tree?
Quote:
> improper lists but I'm not sure... I need to be able to do a 'find' and
> 'insert' for this particular binary tree. Please help, I'm a newbie who
> just needs a little help starting out programming in this weird
> language.
> consider 'weird' a compliment
Thank you for the compliment. Forgive me, you probably referred to the
language. I dont think Scheme *are* weird languages, though.
I suggest that you first try to abstract from representation. You may use
proper lists, improper lists, vectors, objects or ADT's. That's not the
point. Anything that can be composed of two or more elements, will do. In
the first stage of the design of a good algorithm even the question whether
or not insert is going to be desctructive, is irrelevant, I think. If you
dont like to invent your own notation for the problem, using ADT's may help
to abstract. For myself, I try to postpone coding until I have well
understood the problem and its (abstract) solutions. I hope you soon will
experience that Scheme is an easy language with respect to converting
abstract solutions into concrete code. Prove that your solution is correct
and you almost have your code in Scheme.
It happens that I recently wrote R5RS compliant code (I think) in oop style
for balanced trees (with destructive insert/remove and with option for a
specified degree of allowed imbalance). It seems to work nice in MScheme. If
you like I can send you the code, but first convince me that this is not
homework. Mail me privately if you like. I am rather sure that searching the
web can provide you with better solutions, though.
Jos
(Jacob J. A. Koot).
