(still in progress)
Follow the Style Guide for Python Code.
Add docstrings, at least for "everything to be used externally".
Add tests(doc)tests. Or, at least, a start for tinkering:
Python naming style is CapWords for classes, only: that would be new_node.
The left = None statement is there for the comment.
The paranoid prefer is None/is not None over just using what should be a reference in a boolean context.
Above rendition tries to keep DRY and avoids some of what looks repetitious in the insert() you presented.
But, wait, doesn't that descend left or right thing look just the same in lookup() and remove()?
If I had a method
def _find(self, value):
""" Find node with value, if any.
Return this node and setter for (re-)placing it in this tree.
"""
pass
, insert() was simple, and lookup() trivial (if questionable: wording
• lookup: returns the value if it exists in the BST else returns None
, implementation returns a Node):
def insert(self, value):
""" Insert value into this tree.
ToDo: document behaviour with identical keys
"""
existing, place = self._find(value)
if existing is not None:
pass
place(Node(value))
return self
def lookup(self, value):
""" Return node with value, if any. """
return self._find(value)[0]
Remove can profit from a modified successor method
@staticmethod
def leftmost(child, parent=None):
""" Return the leftmost node of the tree rooted at child,
and its parent, if any. """
if child is not None:
while child.left is not None:
child, parent = child.left, child
return child, parent
def deleted(self, node): # node None?
""" Return root of a tree with node's value deleted. """
successor, parent = BinarySearchTree.leftmost(node.right, node)
if successor is None:
return node.left
node.value = successor.value
if node is not parent:
parent.left = successor.right
else:
node.right = successor.right
return node
def remove(self, value):
""" Remove value.
Return 'tree contained value'. """
node, place = self._find(value)
if node is None:
return False
place(self.deleted(node))
return True
My current rendition of _find() adds in Node
def _set_left(self, v):
self.left = v
def _set_right(self, v):
self.right = v
, in BinarySearchTree
def _set_root(self, v):
self.root = v
def _find(self, value):
""" Find node with value, if any.
Return this node and setter for (re-)placing it in this tree.
"""
if self.root is None or self.root.value == value:
return self.root, self._set_root
child = self.root
while True:
node = child
smaller = value < child.value
child = child.left if smaller else child.right
if child is None or child.value == value:
return child, node._set_left if smaller else node._set_right
(TBC)