c - 使用 AVL 树在笛卡尔平面上优化搜索的方法

Question

使用C语言的几何问题

我需要根据笛卡尔平面上的 x 位置执行在 AVL 树（自平衡树）上存储矩形的任务，以便稍后执行一些搜索功能（例如，打印给定内部矩形的名称区域）

我的老师建议在两个子树的每个节点上存储最小值（原始 x）和最大值（x + 宽度），以优化区域搜索。

例如，在上图中，红色节点（根）的最小值是黑色矩形的 x，最大值是绿色矩形的 x + 宽度。

老师给出的条件如下：

（PS：请考虑 search_rect 为矩形在区域上搜索）

1. if (current_node->left->max) >= (search_rect->x) AND (current_node->left->min) <= (search_rect->x)：转到左子树
2. if (current_node->right->max) >= (search_rect->x) AND (current_node->right->min) <= (search_rect->x): 去右子树
3. 如果当前节点上存储的整个矩形都在 search_rect 内，则返回这个矩形

还有其他建议来优化此搜索吗？我的意思是，如果我们只比较矩形的 x 而不是 min x 和 max x 会更容易吗？

标签： csearchoptimizationgeometryavl-tree