projects
/
python_utils.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Improve docstrings for sphinx.
[python_utils.git]
/
collect
/
bst.py
diff --git
a/collect/bst.py
b/collect/bst.py
index 9d6525946e8131728896d86f3400c38c5ba528e7..d39419494d3f482712f17e13a5ff6ce1e7c2ebcf 100644
(file)
--- a/
collect/bst.py
+++ b/
collect/bst.py
@@
-1,5
+1,9
@@
#!/usr/bin/env python3
#!/usr/bin/env python3
+# © Copyright 2021-2022, Scott Gasch
+
+"""Binary search tree."""
+
from typing import Any, Generator, List, Optional
from typing import Any, Generator, List, Optional
@@
-90,9
+94,7
@@
class BinarySearchTree(object):
return self._find(value, node.right)
return None
return self._find(value, node.right)
return None
- def _parent_path(
- self, current: Optional[Node], target: Node
- ) -> List[Optional[Node]]:
+ def _parent_path(self, current: Optional[Node], target: Node) -> List[Optional[Node]]:
if current is None:
return [None]
ret: List[Optional[Node]] = [current]
if current is None:
return [None]
ret: List[Optional[Node]] = [current]
@@
-520,12
+522,12
@@
class BinarySearchTree(object):
return x
path = self.parent_path(node)
return x
path = self.parent_path(node)
- assert path[-1]
+ assert path[-1]
is not None
assert path[-1] == node
path = path[:-1]
path.reverse()
for ancestor in path:
assert path[-1] == node
path = path[:-1]
path.reverse()
for ancestor in path:
- assert ancestor
+ assert ancestor
is not None
if node != ancestor.right:
return ancestor
node = ancestor
if node != ancestor.right:
return ancestor
node = ancestor
@@
-575,7
+577,11
@@
class BinarySearchTree(object):
return self.depth()
def repr_traverse(
return self.depth()
def repr_traverse(
- self, padding: str, pointer: str, node: Optional[Node], has_right_sibling: bool
+ self,
+ padding: str,
+ pointer: str,
+ node: Optional[Node],
+ has_right_sibling: bool,
) -> str:
if node is not None:
viz = f'\n{padding}{pointer}{node.value}'
) -> str:
if node is not None:
viz = f'\n{padding}{pointer}{node.value}'
@@
-590,9
+596,7
@@
class BinarySearchTree(object):
else:
pointer_left = "└──"
else:
pointer_left = "└──"
- viz += self.repr_traverse(
- padding, pointer_left, node.left, node.right is not None
- )
+ viz += self.repr_traverse(padding, pointer_left, node.left, node.right is not None)
viz += self.repr_traverse(padding, pointer_right, node.right, False)
return viz
return ""
viz += self.repr_traverse(padding, pointer_right, node.right, False)
return viz
return ""
@@
-628,9
+632,7
@@
class BinarySearchTree(object):
else:
pointer_left = "├──"
else:
pointer_left = "├──"
- ret += self.repr_traverse(
- '', pointer_left, self.root.left, self.root.left is not None
- )
+ ret += self.repr_traverse('', pointer_left, self.root.left, self.root.left is not None)
ret += self.repr_traverse('', pointer_right, self.root.right, False)
return ret
ret += self.repr_traverse('', pointer_right, self.root.right, False)
return ret