Binary tree insert.

Discussion of Common Lisp
Post Reply
samohtvii
Posts: 12
Joined: Thu Aug 23, 2012 11:49 pm

Binary tree insert.

Post by samohtvii » Sun Sep 23, 2012 11:37 pm

Ok I have one last problem...
I have a binary tree like this....

Code: Select all

(question1 (question2 (question4 (answ3) (answ4) ) (question5 (answ5) (answ6) ) ) (question3 (answ1) (answ2) ) )

Code: Select all

                    question1
                    /       \
           question2        question3
          /        \         /      \
  question4  question5    answ1     answ2
   /     \    /      \   
answ3 answ4 answ5   answ6

yes goes left and no goes right
I have created a second tree that looks like this....

Code: Select all

(newQuestion (answ3)(newans))

Code: Select all

          newQuestion
           /       \
      answ3      newAns
So i have traversed my tree and found the answer 'answ3'. Now i have added a new question and a new answer.
I want to insert that newQuestion to the leaf where ans3 is/was.

I have found the answ3 so i was thinking of doing a search through my tree for that leaf. Then i need to replace that leaf with my new node which i am stumped at.
So it's essentially an insert function but I don't know how to go about it. Can I step through the tree and then cons or append it when i reach the right spot?

Thanks for the help.

just to clarify this will be the new tree...

Code: Select all

                    question1
                    /       \
           question2        question3
          /        \         /      \
  question4  question5    answ1     answ2
   /     \     /      \   
newQues answ4 answ5   answ6
  /   \
answ3  newAns

wvxvw
Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

Re: Binary tree insert.

Post by wvxvw » Mon Sep 24, 2012 1:30 am

You could do a doubly linked list - that way finding the parent of the leaf becomes trivial, but another, perhaps simpler way, if all nodes are unique would be to have a hash-map alongisde the list, which would contain all nodes in the format key = child, value = parent.

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: Binary tree insert.

Post by sylwester » Mon Sep 24, 2012 3:45 am

Wvxvw assumes you found answ3 only. It seems like you have done search prior to your insert? If you changed your search function to include the parent the insert would be trivial. You could return the parent as a second return value in your search with (values ans ans-parent) and do search for update with multiple-value-bind.. OR you could make a function to traverse the tree again to return the parent (assuming the extra search has little performance impact).No need to do messy doubly linked lists unless. You absolutely need to :)
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p

Goheeca
Posts: 271
Joined: Thu May 10, 2012 12:54 pm
Contact:

Re: Binary tree insert.

Post by Goheeca » Mon Sep 24, 2012 5:40 am

You can do this:

Code: Select all

(setq *print-circle* t)
(defvar *list* (list 1 2 3 nil))
(setf (nth (1- (length *list*)) *list*) *list*)
With this you can have links for parents in childs.
// That's a pity that last isn't setf-able (... by the standard - yeah I know about defsetf).

And with the same thing you can replace the element in a list.

Code: Select all

(defvar *test* (list 1 2 3))
(setf (nth 2 *test*) '(a b c))
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Binary tree insert.

Post by Paul » Wed Sep 26, 2012 6:39 pm

Your structure uses too many conses. Use (parent left . right) [i.e., (parent . (left . right))] rather than (parent (left) (right)) [i.e., (parent . ((left . nil) . ((right . nil))))], then you can tell whether, say, "left", is a question or an answer using CONSP. Your original tree looks like

Code: Select all

(question1 (question2 (question4 answ3 . answ4) question5 answ5 . answ6)
 question3 answ1 . answ2)
and what you're asking for is

Code: Select all

(subst '(newQuestion answ3 . newAns) 'answ3 <original>)

Post Reply