quadtree: Try to keep the tree in better balance.

When a tree node is removed, we now attempt to add the detached
subtree in more optimized order to the new tree. This is done so that
we walk down the detached tree and add a new node to the main tree
always when the tree is one quarter'th smaller than the previous node
that was added.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index a3315392f3ae3e9b669401946622cd66c5968e65..61a26997c1555a7ee5c3419633d67164051bee28 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -157,39 +157,72 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
 }
 
 /*
- * _quadtree_reposition_reqursively - Move everything under and
- * including a given node under the new root node
+ * _qt_optimal_del - Delete nodes from a detached subtree in optimal order
+ *
+ * All nodes are moved under the new parent node
  */
-
-static void
-_quadtree_reposition_reqursively(struct quadtree *root,
-                                struct quadtree *node,
-                                struct quadtree_ops *ops)
+static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
+                      struct quadtree_ops *ops, int parents)
 {
-       int i;
-
-       validate_tree(root);
-
-       /* First remove all children, if any */
+       struct quadtree *child[4] = {0};
+       int i, children = 0, max_c, max_i;
 
        for (i = 0; i < 4; i++) {
-               if (!node->child[i])
+               if (!node->child[i]) {
+                       child[i] = 0;
                        continue;
+               }
 
-               if (node->child[i] == node ||
-                   node->child[i] == node->parent)
-                       trap();
+               child[children] = node->child[i];
+               node->child[i] = NULL;
+               children++;
+       }
+
+       /*
+        * Try to remove the nodes in such order that the node which
+        * has child number one quarter of the parent's child numer
+        * gets deleted first.
+        */
 
-               _quadtree_reposition_reqursively(root, node->child[i], ops);
-               node->child[i] = 0;
+       if (node->children <= parents / 4) {
+               if (debug) {
+                       printf("%d: Moving node %p away from parent %p\n",
+                              __LINE__, node, parent);
+                       fflush(stdout);
+               }
+               validate_tree(parent);
+               quadtree_add(parent, node, ops);
+               node = NULL;
+               parents /= 4;
        }
 
-       /* There are no children left, reset stats */
-       node->depth = 0;
-       node->children = 0;
+       while(children) {
+               max_c = -1;
+               max_i = -1;
+               for (i = 0; i < 4; i++) {
+                       if (!child[i])
+                               continue;
+
+                       if (max_c < child[i]->children) {
+                               max_c = child[i]->children;
+                               max_i = i;
+                       }
+               }
 
-       /* Then remove this node under the new root. */
-       quadtree_add(root, node, ops);
+               _qt_optimal_del(parent, child[max_i], ops, parents / 4);
+               child[max_i] = 0;
+               children--;
+       }
+
+       if (node) {
+               validate_tree(parent);
+               if (debug) {
+                       printf("%d: Moving node %p away from parent %p\n",
+                              __LINE__, node, parent);
+                       fflush(stdout);
+               }
+               quadtree_add(parent, node, ops);
+       }
 }
 
 /*
@@ -225,9 +258,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
                                parent->parent = 0;
                                continue;
                        }
-                       _quadtree_reposition_reqursively(parent,
-                                                        node->child[i],
-                                                        ops);
+                       _qt_optimal_del(parent, node->child[i], ops,
+                                       node->children);
                        node->child[i] = 0;
                }
 
@@ -246,34 +278,28 @@ struct quadtree *quadtree_del(struct quadtree *node,
                        break;
                }
        }
-       if (i == 4) {
-               printf("%s:%d Fatal! Tree inconsistency detected\n",
-                      __func__, __LINE__);
+       if (i == 4)
                trap();
-       }
 
-       /* Fix parent stats */
-       quadtree_recalculate_parent_stats(node->parent, ops);
+       parent = node->parent;
 
        /*
-        * The sub branch is now detached from the main tree. Continue
-        * relocating the detached branch.
+        * The sub branch is now detached from the main tree. Fix the
+        * stats.
         */
+       quadtree_recalculate_parent_stats(node->parent, ops);
 
-       for (i = 0; i < 4; i++) {
-               if (!node->child[i])
-                       continue;
-
-               _quadtree_reposition_reqursively(node->parent, node->child[i],
-                                                ops);
-               node->child[i] = 0;
-       }
+       parent = quadtree_find_parent(parent);
 
-       parent = quadtree_find_parent(node);
-       node->parent = 0;
+       if (node->children) {
+               for (i = 0; i < 4; i++) {
+                       if (!node->child[i])
+                               continue;
 
-       node->children = 0;
-       node->depth = 0;
+                       _qt_optimal_del(parent, node->child[i], ops,
+                                       node->children);
+               }
+       }
 
        validate_tree(parent);
        return parent;