Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def _remove_aux(self, node, key):
- """
- -------------------------------------------------------
- Attempts to find a value matching key in a BST node. Deletes the node
- if found and returns the sub-tree root.
- Private recursive operation called only by remove.
- Use: node, value = self._remove_aux(node, key)
- -------------------------------------------------------
- Preconditions:
- node - a bst node to search for key (_BSTNode)
- key - data to search for (?)
- Postconditions:
- returns
- node - the current node or its replacement (_BSTNode)
- value - value in node containing key, None otherwise.
- -------------------------------------------------------
- """
- if node is None:
- value = None
- elif key < node._data:
- node._left, value = self._remove_aux(node._left, key)
- elif key > node._data:
- node._right, value = self._remove_aux(node._right, key)
- else:
- value = node._data
- if node._left is None:
- node = node._right
- elif node._right is None:
- node = node._left
- else:
- if node._left._right is None:
- repl_node = node._left
- else:
- repl_node = self._delete_node_left(
- node._left, node._left._right)
- repl_node._left = node._left
- repl_node._right = node._right
- node = repl_node
- node._update_height()
- self._count -= 1
- if node is not None and value is not None:
- node._update_height()
- return node, value
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement