Page 1 of 1

Binary tree insert.

Posted: Sun Sep 23, 2012 11:37 pm
by samohtvii
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

Re: Binary tree insert.

Posted: Mon Sep 24, 2012 1:30 am
by wvxvw
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.

Re: Binary tree insert.

Posted: Mon Sep 24, 2012 3:45 am
by sylwester
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 :)

Re: Binary tree insert.

Posted: Mon Sep 24, 2012 5:40 am
by Goheeca
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))

Re: Binary tree insert.

Posted: Wed Sep 26, 2012 6:39 pm
by Paul
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>)