Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2018
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.79 KB | None | 0 0
  1. def _remove_aux(self, node, key):
  2. """
  3. -------------------------------------------------------
  4. Attempts to find a value matching key in a BST node. Deletes the node
  5. if found and returns the sub-tree root.
  6. Private recursive operation called only by remove.
  7. Use: node, value = self._remove_aux(node, key)
  8. -------------------------------------------------------
  9. Preconditions:
  10. node - a bst node to search for key (_BSTNode)
  11. key - data to search for (?)
  12. Postconditions:
  13. returns
  14. node - the current node or its replacement (_BSTNode)
  15. value - value in node containing key, None otherwise.
  16. -------------------------------------------------------
  17. """
  18.  
  19. if node is None:
  20. value = None
  21. elif key < node._data:
  22. node._left, value = self._remove_aux(node._left, key)
  23. elif key > node._data:
  24. node._right, value = self._remove_aux(node._right, key)
  25. else:
  26. value = node._data
  27. if node._left is None:
  28. node = node._right
  29. elif node._right is None:
  30. node = node._left
  31. else:
  32. if node._left._right is None:
  33. repl_node = node._left
  34. else:
  35. repl_node = self._delete_node_left(
  36. node._left, node._left._right)
  37. repl_node._left = node._left
  38. repl_node._right = node._right
  39. node = repl_node
  40. node._update_height()
  41. self._count -= 1
  42. if node is not None and value is not None:
  43. node._update_height()
  44.  
  45. return node, value
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement