A node in a binary search tree. Uniform for root, subtree root, and leaf nodes.
| 117 | |
| 118 | |
| 119 | class _BinarySearchTree(object): |
| 120 | """ |
| 121 | A node in a binary search tree. Uniform for root, subtree root, and leaf |
| 122 | nodes. |
| 123 | """ |
| 124 | |
| 125 | def __init__(self, value): |
| 126 | self._value = value |
| 127 | self._lesser = None |
| 128 | self._greater = None |
| 129 | |
| 130 | def find_max(self, predicate, max_=None): |
| 131 | """ |
| 132 | Return the largest item in or under this node that satisfies |
| 133 | *predicate*. |
| 134 | """ |
| 135 | if predicate(self.value): |
| 136 | max_ = self.value |
| 137 | next_node = self._greater |
| 138 | else: |
| 139 | next_node = self._lesser |
| 140 | if next_node is None: |
| 141 | return max_ |
| 142 | return next_node.find_max(predicate, max_) |
| 143 | |
| 144 | @classmethod |
| 145 | def from_ordered_sequence(cls, iseq): |
| 146 | """ |
| 147 | Return the root of a balanced binary search tree populated with the |
| 148 | values in iterable *iseq*. |
| 149 | """ |
| 150 | seq = list(iseq) |
| 151 | # optimize for usually all fits by making longest first |
| 152 | bst = cls(seq.pop()) |
| 153 | bst._insert_from_ordered_sequence(seq) |
| 154 | return bst |
| 155 | |
| 156 | def insert(self, value): |
| 157 | """ |
| 158 | Insert a new node containing *value* into this tree such that its |
| 159 | structure as a binary search tree is preserved. |
| 160 | """ |
| 161 | side = "_lesser" if value < self.value else "_greater" |
| 162 | child = getattr(self, side) |
| 163 | if child is None: |
| 164 | setattr(self, side, _BinarySearchTree(value)) |
| 165 | else: |
| 166 | child.insert(value) |
| 167 | |
| 168 | def tree(self, level=0, prefix=""): |
| 169 | """ |
| 170 | A string representation of the tree rooted in this node, useful for |
| 171 | debugging purposes. |
| 172 | """ |
| 173 | text = "%s%s\n" % (prefix, self.value.text) |
| 174 | prefix = "%s└── " % (" " * level) |
| 175 | if self._lesser: |
| 176 | text += self._lesser.tree(level + 1, prefix) |
no outgoing calls
no test coverage detected
searching dependent graphs…