Hello,
I need help with creating an insert funtion for a biniary tree...
The structure is (root left-tree right-tree). Is there a quick way to
insert (in order) an atom into the tree? Thanks
Paul
PAUL G SEMS <······@cs.uakron.edu> writes:
> I need help with creating an insert funtion for a biniary tree...
> The structure is (root left-tree right-tree). Is there a quick way to
> insert (in order) an atom into the tree?
Yes.
Christopher
PAUL G SEMS <······@cs.uakron.edu> writes:
>
> Hello,
>
> I need help with creating an insert funtion for a biniary tree...
> The structure is (root left-tree right-tree).
What help do you need?
I suggest starting with a small tree with maybe 5 elements in it. Then
add another element.
Do this by hand, perhaps with drawings.
As you go through the process of deciding how to insert the new element,
you will have the outline of a procedure for doing the insertion
programatically.
You will then want to create a general, recursive procedure that will
accomplish what you just did by hand.
> Is there a quick way to
> insert (in order) an atom into the tree? Thanks
Depends on what you mean by quick.
Quick to implement? Yes.
Quick to run? Not necessarily. You would expect average runtimes of
around O(ln N) for a tree with N elements and reasonable balance.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
In article <···············@sevak.isi.edu>,
Thomas A. Russ <···@sevak.isi.edu> wrote:
>PAUL G SEMS <······@cs.uakron.edu> writes:
>> I need help with creating an insert funtion for a biniary tree...
>> The structure is (root left-tree right-tree).
>
>What help do you need?
>
>I suggest starting with a small tree with maybe 5 elements in it. Then
>add another element.
>
>Do this by hand, perhaps with drawings.
You could also try reading one of the many good textbooks on algorithms and
data structures. They probably won't provide Lisp code, but the general
structure of the algorithm should be independent of the language. Once you
understand the algorithm, generating Lisp code should be relatively easy.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
PAUL G SEMS <······@cs.uakron.edu> writes:
> I need help with creating an insert funtion for a biniary tree...
> The structure is (root left-tree right-tree). Is there a quick way to
> insert (in order) an atom into the tree? Thanks
The theory of binary trees is rather well known. Any algorithms book
worth its salt will provide the answer to this question and pseudocode
to implement it. These are pretty easy to translate into Lisp.
--tim