[Tutor] Re: Tutor digest, Vol 1 #260 - 6 msgs

[dyoo]

On Tue, 14 Mar 2000, you wrote:

The bug occurs when you initially insert the first element of the list --
Although you've set branch to the newnode, the tree reference in your self
hasn't changed.  In your _InsertTree():

  if branch == None:
    branch = newnode

will not affect your original tree. Likewise, _InsertTree repeats the same bug.

Try out the following code that demonstrates the problem:
class Number:
  def __init__(self, x):
    self.x = x

# note - this is buggy: the swap won't work because references haven't changed
def swap(a, b):
  t = a
  a = b
  b = a

if __name__ == "__main__":
  firstnumber = Number(42)
  secondnumber = Number(17)
  print firstnumber.x
  print secondnumber.x

  swap(firstnumber, secondnumber)

  print firstnumber.x
  print secondnumber.x

Once you understand why this doesn't work, you'll see why the Insert() code
isn't working.

If you don't want to spoil the solution for yourself, don't read below.
##############

There's an easier way to build up your binary tree.  Let's define
_InsertTree to insert its element into the tree, and then _return_ itself.  By
using return, we can properly redirect our references.

def _InsertTree(self, branch, newnode):
  if branch == None:
    return newnode
  elif newnode.entry.key < branch.entry.key:
    branch.left = self._InsertTree(branch.left, newnode)
    return branch
  else:
    branch.right = self._InsertTree(branch.right, newnode)
    return branch

def Insert(self, newnode):
  self.tree = self._InsertTree(self.tree, newnode)

Note -- I have not tested this code yet.  *grin*