From 812207530bba1ed2d9df634a1a827f4628181099 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Sat, 6 May 2023 17:48:39 -0700 Subject: [PATCH] Adds find_lowest_node_less_than_or_equal_to. --- src/pyutils/collectionz/bst.py | 105 ++++++++++++++++++++++++++------- 1 file changed, 84 insertions(+), 21 deletions(-) diff --git a/src/pyutils/collectionz/bst.py b/src/pyutils/collectionz/bst.py index 343ddc0..cefbf59 100644 --- a/src/pyutils/collectionz/bst.py +++ b/src/pyutils/collectionz/bst.py @@ -119,25 +119,88 @@ class BinarySearchTree(object): """ if self.root is not None: - return self._find(value, self.root) + return self._find_exact(value, self.root) return None - def _find(self, value: ComparableNodeValue, node: Node) -> Optional[Node]: - """Find helper""" - if value == node.value: + def _find_exact(self, target: ComparableNodeValue, node: Node) -> Optional[Node]: + """Recursively traverse the tree looking for a node with the + target value. Return that node if it exists, otherwise return + None.""" + + if target == node.value: return node - elif value < node.value and node.left is not None: - return self._find(value, node.left) - elif value > node.value and node.right is not None: - return self._find(value, node.right) + elif target < node.value and node.left is not None: + return self._find_exact(target, node.left) + elif target > node.value and node.right is not None: + return self._find_exact(target, node.right) return None - def _find_lowest_value_greater_than_or_equal_to( + def _find_lowest_node_less_than_or_equal_to( + self, target: ComparableNodeValue, node: Optional[Node] + ) -> Optional[Node]: + """Find helper that returns the lowest node that is less + than or equal to the target value. Returns None if target is + lower than the lowest node in the tree. + + >>> t = BinarySearchTree() + >>> t.insert(50) + >>> t.insert(75) + >>> t.insert(25) + >>> t.insert(66) + >>> t.insert(22) + >>> t.insert(13) + >>> t.insert(85) + >>> t + 50 + ├──25 + │ └──22 + │ └──13 + └──75 + ├──66 + └──85 + + >>> t._find_lowest_node_less_than_or_equal_to(48, t.root).value + 25 + >>> t._find_lowest_node_less_than_or_equal_to(55, t.root).value + 50 + >>> t._find_lowest_node_less_than_or_equal_to(100, t.root).value + 85 + >>> t._find_lowest_node_less_than_or_equal_to(24, t.root).value + 22 + >>> t._find_lowest_node_less_than_or_equal_to(20, t.root).value + 13 + >>> t._find_lowest_node_less_than_or_equal_to(72, t.root).value + 66 + >>> t._find_lowest_node_less_than_or_equal_to(78, t.root).value + 75 + >>> t._find_lowest_node_less_than_or_equal_to(12, t.root) is None + True + + """ + + if not node: + return None + + if target == node.value: + return node + + elif target > node.value: + if below := self._find_lowest_node_less_than_or_equal_to( + target, node.right + ): + return below + else: + return node + + else: + return self._find_lowest_node_less_than_or_equal_to(target, node.left) + + def _find_lowest_node_greater_than_or_equal_to( self, target: ComparableNodeValue, node: Optional[Node] ) -> Optional[Node]: """Find helper that returns the lowest node that is greater than or equal to the target value. Returns None if target is - greater than the highest node in the tree. + higher than the greatest node in the tree. >>> t = BinarySearchTree() >>> t.insert(50) @@ -156,21 +219,21 @@ class BinarySearchTree(object): ├──66 └──85 - >>> t._find_lowest_value_greater_than_or_equal_to(48, t.root).value + >>> t._find_lowest_node_greater_than_or_equal_to(48, t.root).value 50 - >>> t._find_lowest_value_greater_than_or_equal_to(55, t.root).value + >>> t._find_lowest_node_greater_than_or_equal_to(55, t.root).value 66 - >>> t._find_lowest_value_greater_than_or_equal_to(1, t.root).value + >>> t._find_lowest_node_greater_than_or_equal_to(1, t.root).value 13 - >>> t._find_lowest_value_greater_than_or_equal_to(24, t.root).value + >>> t._find_lowest_node_greater_than_or_equal_to(24, t.root).value 25 - >>> t._find_lowest_value_greater_than_or_equal_to(20, t.root).value + >>> t._find_lowest_node_greater_than_or_equal_to(20, t.root).value 22 - >>> t._find_lowest_value_greater_than_or_equal_to(72, t.root).value + >>> t._find_lowest_node_greater_than_or_equal_to(72, t.root).value 75 - >>> t._find_lowest_value_greater_than_or_equal_to(78, t.root).value + >>> t._find_lowest_node_greater_than_or_equal_to(78, t.root).value 85 - >>> t._find_lowest_value_greater_than_or_equal_to(95, t.root) is None + >>> t._find_lowest_node_greater_than_or_equal_to(95, t.root) is None True """ @@ -182,12 +245,12 @@ class BinarySearchTree(object): return node elif target > node.value: - return self._find_lowest_value_greater_than_or_equal_to(target, node.right) + return self._find_lowest_node_greater_than_or_equal_to(target, node.right) # If target < this node's value, either this node is the # answer or the answer is in this node's left subtree. else: - if below := self._find_lowest_value_greater_than_or_equal_to( + if below := self._find_lowest_node_greater_than_or_equal_to( target, node.left ): return below @@ -714,7 +777,7 @@ class BinarySearchTree(object): 50 66 """ - node: Optional[Node] = self._find_lowest_value_greater_than_or_equal_to( + node: Optional[Node] = self._find_lowest_node_greater_than_or_equal_to( lower, self.root ) while node: -- 2.45.0