Improve insert

travisjungroth · Dec 19, 2022 · 5c54ed9 · 5c54ed9
1 parent c6a9ac4
commit 5c54ed9
Showing 1 changed file with 6 additions and 2 deletions.
diff --git a/mtree4.py b/mtree4.py
@@ -144,9 +144,13 @@ def insert(self, value: Value) -> None:
         if isinstance(self.children[0], ValueNode):
             self.add_child(ValueNode(self.tree, value))
         else:
+            self.children: list[ParentNode]
             self.radius = max(self.radius, self.distance(value))
-            node = random.choice(self.children)
-            node.insert(value)
+            distances = [(child, child.distance(value)) for child in self.children]
+            child, distance = min(distances, key=itemgetter(1))
+            if distance >= child.radius:
+                child, _ = min(distances, key=lambda x: x[1] - x[0].radius)
+            child.insert(value)
 
     def __len__(self):
         return len(self.children)