BST (yes, that's binary search tree) 
Author Message
 BST (yes, that's binary search tree)

How can I implement a balanced BST in scheme. I'm guessing using
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

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Sun, 27 Apr 2003 03:00:00 GMT  
 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).



Mon, 28 Apr 2003 10:28:43 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Self-Adjusting Binary Search Trees (Splay Trees)

2. Self-Adjusting Binary Search Trees (Splay Trees)

3. Binary Search Trees

4. Binary Search Trees

5. binary search tree

6. Binary tree search in PL1

7. Breadth first print procedure for binary search trees

8. need code for red-black binary search tree

9. Pls Help! Need binary search tree module

10. binary search tree

11. Binary Search Trees

12. binary search tree

 

 
Powered by phpBB® Forum Software