{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实验 06：基数树与圣诞树——前缀共享与\"描述符\"的递归细分\n",
    "\n",
    "## 为什么做这个实验\n",
    "\n",
    "- **要验证的现象**：前面几个实验的索引都按\"一个完整的键\"组织（B+ 树按键排序，位图按取值建位）。本实验看另一类结构 **Trie（前缀树）**：把键拆成一段一段，从根往下每一层消费一段。**查找代价是 $O(\\text{键长})$，与表里有几行无关**——这是它相对 B+ 树（$O(\\log n)$）的本质差别。\n",
    "- **反直觉之处一**：Trie 省了比较次数，却很费空间。每个字符一个节点，长键会拉出很长的链，其中大量\"只有一个孩子的链\"是纯粹的浪费。**Radix Trie（基数树）**用路径压缩把这些链并成一条边、边上记完整片段。本仓库实测：插入 `CAR`、`CAT`、`CATS`、`DOG`、`DOGS`、`DOT` 这 6 个共享前缀的键，标准 Trie **11** 个节点，压缩后 **9** 个。\n",
    "- **反直觉之处二**：本仓库把\"逐字符比较\"抽象成了\"**把一个描述符（descriptor）递归细分**\"。换掉描述符，同一套 Trie 代码就从字符串索引变成了二维空间索引——这就是标题里的**圣诞树**。\n",
    "- **一处需要你自己动手查的地方**：本机实测 `Triangle.split_into_sub_descriptors()` 的细分结果**不符合**\"取三边中点分成 4 个全等小三角形\"的预期（详见后文\"值得探究的问题\"）。不要因为它是仓库自带的代码就默认它是对的。\n",
    "- **学完能回答**：给定扇出 $c$ 与层数 $L$，这棵树有多少内部节点、多少叶子？为什么真实的空间索引（R-tree）不预先细分到固定深度？\n",
    "\n",
    "## 运行前准备\n",
    "\n",
    "本实验依赖仓库自带的 `system/` 模块，需要额外安装四个包：\n",
    "\n",
    "```bash\n",
    "python -m pip install ipycanvas graphviz deprecation faker\n",
    "```\n",
    "\n",
    "| 包 | 被谁需要 | 说明 |\n",
    "|---|---|---|\n",
    "| `ipycanvas` | `system/utils.py` | 在 notebook 里画三角形与树（顶层导入，**必须安装**） |\n",
    "| `graphviz` | `system/indexes/btree.py` | B+ 树可视化，测试模块会间接导入 |\n",
    "| `deprecation` | `system/interfaces/stores.py` | 弃用标记 |\n",
    "| `faker` | `system/tests/test_indexing.py` | 生成测试数据 |\n",
    "\n",
    "另外全局需要 `pandas` `numpy` `matplotlib` `seaborn`。验证：\n",
    "\n",
    "```python\n",
    "from system.utils import Vector, Triangle\n",
    "from system.indexes.radix_trie import RadixTrie\n",
    "from system.indexes.christmas_tree import ChristmasTree\n",
    "print(\"环境就绪\")\n",
    "```\n",
    "\n",
    "> **注意**：绘图部分（`ipycanvas` 的 `Canvas`）只能在 Jupyter 前端里显示，在纯 `.py` 脚本中不会有输出；逻辑部分（构建、`show()`、`contains()`）在脚本里照常可用。\n",
    "> 如果 `import system` 失败，先运行下一个代码格——它会自动把仓库根目录（含 `system/` 的那一层）加入 `sys.path`。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys, pathlib\n",
    "\n",
    "# Put the repo root (the directory containing `system/`) on sys.path so\n",
    "# `from system...` works whether this notebook is opened from its own\n",
    "# folder or from the repo root.\n",
    "for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):\n",
    "    if (_p / \"system\").is_dir():\n",
    "        if str(_p) not in sys.path:\n",
    "            sys.path.insert(0, str(_p))\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**A Christmas Trie**\n",
    "\n",
    "本笔记本演示一棵\"圣诞树\"（christmas trie）的主要特性。在往下走之前，先把三个概念理清楚。\n",
    "\n",
    "### 标准 Trie：按前缀走，不比较整个键\n",
    "\n",
    "Trie 把键拆成一段一段，从根往下每一层消费一段。以 `CAR`、`CAT`、`CATS` 为例：\n",
    "\n",
    "```text\n",
    "        (root)\n",
    "         /  \\\n",
    "        C    D...\n",
    "       /      \\\n",
    "      A        O\n",
    "     / \\      / \\\n",
    "    R   T    G   T\n",
    "           /  \\\n",
    "          S    (end)\n",
    "```\n",
    "\n",
    "**Trie 的查找代价是 $O(\\text{键长})$，与表里有几行无关。** 代价在**空间**：每个字符一个节点，长键会拉出很长的链，而且很多链上只有一个孩子——这些\"单孩子链\"是纯粹的浪费。\n",
    "\n",
    "### Radix Trie：把单孩子链压成一条边\n",
    "\n",
    "**路径压缩（path compression）**：如果一条边上只有一个孩子，就把这条边和它的孩子合并，边上记下完整的字符串片段。压缩后边上的标签不再是一个字符，而可以是任意长度的串。这就是 **Radix Trie（基数树）**，也叫压缩 Trie。\n",
    "\n",
    "本仓库的实测（插入 `CAR`、`CAT`、`CATS`、`DOG`、`DOGS`、`DOT` 六个共享前缀的键）：\n",
    "\n",
    "| | 节点数 |\n",
    "|---|---|\n",
    "| 标准 Trie | **11** |\n",
    "| Radix Trie（路径压缩后） | **9** |\n",
    "\n",
    "省下 2 个节点。键越长、共享前缀越多，省得越多。\n",
    "\n",
    "### 描述符：把\"逐字符\"换成\"递归细分\"\n",
    "\n",
    "本仓库的 `RadixTrie` 有一个关键抽象：**键映射（key mapping）**，它决定\"一个键在第 $i$ 层被切成哪一段、这一段映射到第几个孩子\"。\n",
    "\n",
    "- 用 `PrefixDigitMapping`，键 `110` 在第 1 层取第 1 个字符 `'1'` → 走 1 号孩子；第 2 层取 `'1'` → 走 1 号孩子；第 3 层取 `'0'` → 走 0 号孩子。这就是普通的二进制 Trie。\n",
    "- **换成别的映射，同一棵树就能索引别的东西。**\n",
    "\n",
    "圣诞树把映射换成了**几何描述符的递归细分**：根节点持有一个三角形，把它细分成 4 个子三角形，每个孩子持有一个；再各自细分……于是\"从根走到叶\"等价于\"不断判断一个点落在哪个子三角形里\"。**这就是空间索引**：把二维平面递归划分成嵌套的区域，区域的编号就是索引键。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 1：三角形描述符与\"包含\"判定\n",
    "\n",
    "描述符（descriptor）要提供两件事：\n",
    "\n",
    "1. `contains(point)` —— 判断一个点是否落在自己内部；\n",
    "2. `split_into_sub_descriptors()` —— 把自己细分成 $c$ 个更小的描述符。\n",
    "\n",
    "有了这两个方法，Trie 的\"往下走一层\"就等价于\"判断点落在哪个子描述符里\"。本仓库的 `Triangle.contains()` 用重心坐标实现。\n",
    "\n",
    "下面这段代码做两件事：\n",
    "\n",
    "- 构造一个三角形 `t = Triangle((0,0), (120,0), (60,120))`，并定义 `recursive_draw()`：`rec_depth` 控制递归到第几层，每层先把当前三角形画出来，再对它的 4 个子三角形递归；\n",
    "- 画一排图（`rec_depth` 从 1 到 7），直观展示\"递归细分\"长什么样。\n",
    "\n",
    "**预期看到什么**：一排越来越密的三角形。第 1 层是 1 个大三角形，第 2 层是它细分后的 4 个小三角形……\n",
    "\n",
    "紧接着的下一格用 `contains()` 打点验证：在 $0 \\le x, y < 300$ 的网格上逐点判断，落在三角形内的点画成白色，落在外的画成品红色。**预期看到**：一个三角形的轮廓被清晰地\"点\"出来——这说明 `contains()` 在边界附近也判得对。\n",
    "\n",
    "> 浮点边界要留心：`(0,0)`、`(300,0)`、`(150,300)` 是三个顶点，`(150,0)` 在底边上。不同实现对边界的归属可能不同，这是空间索引里一个真实的坑。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-20T08:03:09.784902Z",
     "start_time": "2024-12-20T08:03:09.503604Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "0ed73da80e874bf9844c80622a637a80",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(height=120, sync_image_data=True, width=960)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from system.utils import Vector, Triangle\n",
    "from ipycanvas import Canvas, hold_canvas\n",
    "\n",
    "x_width: int = 120\n",
    "y_width: int = x_width\n",
    "t: Triangle = Triangle(Vector(0, 0), Vector(x_width, 0), Vector(x_width / 2, x_width))\n",
    "\n",
    "\n",
    "def recursive_draw(\n",
    "    t: Triangle, canvas: Canvas, canvas_height: int, rec_depth: int, x_offset: int = 0\n",
    "):\n",
    "    \"\"\"Draws recursive triangles.\"\"\"\n",
    "    if rec_depth == 0:\n",
    "        return\n",
    "    t.draw(canvas, canvas_height, x_offset, y_offset=0)\n",
    "    subs = t.split_into_sub_descriptors()\n",
    "    for t_sub in subs:\n",
    "        recursive_draw(t_sub, canvas, canvas_height, rec_depth - 1, x_offset)\n",
    "\n",
    "\n",
    "# draw sub-triangles for different depths:\n",
    "max_rec_level: int = 8\n",
    "canvas = Canvas(width=x_width * max_rec_level, height=y_width, sync_image_data=True)\n",
    "\n",
    "for rec_depth in range(1, max_rec_level):\n",
    "    with hold_canvas(canvas):\n",
    "        recursive_draw(t, canvas, y_width, rec_depth, x_offset=rec_depth * x_width)\n",
    "display(canvas)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-20T08:03:10.943290Z",
     "start_time": "2024-12-20T08:03:09.810350Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "65efdbdf0b0440d0ace4f072643b9b45",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(height=120, sync_image_data=True, width=120)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# check and visualize containment in triangle:\n",
    "canvas = Canvas(width=x_width, height=y_width, sync_image_data=True)\n",
    "with hold_canvas(canvas):\n",
    "    display(canvas)\n",
    "    recursive_draw(t, canvas, y_width, 1)\n",
    "    for i in range(100):\n",
    "        for x in range(0, 300, 7):\n",
    "            for y in range(0, 300, 7):\n",
    "                contained: bool = t.contains(Vector(x, y))\n",
    "                if contained:\n",
    "                    canvas.fill_style = \"#FFFFFF\"\n",
    "                else:\n",
    "                    canvas.fill_style = \"#ff0066\"\n",
    "\n",
    "                canvas.fill_rect(x, y_width - y, 2, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 2：一棵简单的 Radix Trie\n",
    "\n",
    "下面构造一棵**固定扇出**的二进制 Radix Trie：\n",
    "\n",
    "```python\n",
    "trie = RadixTrie[str, str](\n",
    "    key_mapping=prefix_mapping,      # 决定\"键的第 i 位映射到第几个孩子\"\n",
    "    children_per_inner_node=2,       # 扇出 c = 2\n",
    "    number_of_inner_node_levels=3,   # 层数 L = 3\n",
    ")\n",
    "```\n",
    "\n",
    "两个参数的含义：\n",
    "\n",
    "- `children_per_inner_node = c`：每个内部节点有几个孩子；\n",
    "- `number_of_inner_node_levels = L`：内部节点有几层（叶子在第 $L+1$ 层）。\n",
    "\n",
    "**固定扇出 Trie 的规模公式**（这是本实验要背下来的公式）：\n",
    "\n",
    "$$\\text{内部节点数} = \\sum_{i=0}^{L-1} c^{i}, \\qquad \\text{叶子数} = c^{L}$$\n",
    "\n",
    "代入 $c = 2$、$L = 3$：内部节点 $1 + 2 + 4 = 7$，叶子 $2^3 = 8$。\n",
    "\n",
    "**注意**：这是\"满树\"的规模，与实际存了多少个键无关。下面存入 5 个键（`110`→a、`101`→b、`010`→c、`011`→d、`111`→e），8 个叶子里就会有 **3 个是空的**。这正是固定扇出 Trie 的空间代价，也是路径压缩要解决的问题。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RadixTrie:\n",
      "\tInnerNode {\n",
      "\t\tInnerNode {\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: [('010', 'c')]\n",
      "\t\t\t\t},\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: [('011', 'd')]\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t}\n",
      "\t\tInnerNode {\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: [('101', 'b')]\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: [('110', 'a')]\n",
      "\t\t\t\t},\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: [('111', 'e')]\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t}\n",
      "\t}\n"
     ]
    }
   ],
   "source": [
    "from system.indexes.radix_trie import RadixTrie\n",
    "from system.tests.test_indexing import PrefixDigitMapping\n",
    "\n",
    "prefix_mapping: PrefixDigitMapping = PrefixDigitMapping()\n",
    "trie: RadixTrie[str, str] = RadixTrie[str, str](\n",
    "    key_mapping=prefix_mapping,\n",
    "    children_per_inner_node=2,\n",
    "    number_of_inner_node_levels=3,\n",
    ")\n",
    "trie.put(\"110\", \"a\")\n",
    "trie.put(\"101\", \"b\")\n",
    "trie.put(\"010\", \"c\")\n",
    "trie.put(\"011\", \"d\")\n",
    "trie.put(\"111\", \"e\")\n",
    "trie.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**预期看到什么**：`trie.show()` 打印出的结构应当满足——\n",
    "\n",
    "- **7 个内部节点 + 8 个叶子**，与公式 $1+2+4=7$、$2^3=8$ 完全一致；\n",
    "- 8 个叶子里只有 **5 个非空**（前缀 `000`、`001`、`100` 对应的 3 个叶子是空的）；\n",
    "- 非空叶子的分布：`010`→c、`011`→d 在\"首位 0\"一侧；`101`→b、`110`→a、`111`→e 在\"首位 1\"一侧。\n",
    "\n",
    "请对照输出**亲手数一遍**节点，这是验证你真的读懂了公式的唯一办法。\n",
    "\n",
    "如果想直接验证公式，可以另起一格跑：\n",
    "\n",
    "```python\n",
    "def sizes(c, L):\n",
    "    return sum(c ** i for i in range(L)), c ** L\n",
    "\n",
    "for c, L in [(2, 3), (2, 4), (4, 3), (4, 4), (8, 3)]:\n",
    "    inner, leaves = sizes(c, L)\n",
    "    print(f\"c={c} L={L}: 内部节点 {inner:4d}  叶子 {leaves:5d}  合计 {inner+leaves:5d}\")\n",
    "```\n",
    "\n",
    "期望输出：`c=2 L=3: 7/8`、`c=2 L=4: 15/16`、`c=4 L=3: 21/64`、`c=4 L=4: 85/256`、`c=8 L=3: 73/512`。\n",
    "\n",
    "**读这张表**：层数每 +1，叶子数乘 $c$。空间索引要覆盖一个大区域，代价增长得非常快——这解释了为什么真实的空间索引（R-tree）**不预先细分到固定深度**，而是按需分裂。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 3：圣诞树——只换描述符，不换结构\n",
    "\n",
    "```python\n",
    "triangle = Triangle(Vector(0, 0), Vector(300, 0), Vector(150, 300))\n",
    "christmas_trie = ChristmasTree[Vector, str](\n",
    "    children_per_inner_node=4,        # 三角形细分成 4 个子三角形\n",
    "    descriptor=triangle,              # ← 这里是关键：换成几何描述符\n",
    "    number_of_inner_node_levels=3,\n",
    ")\n",
    "```\n",
    "\n",
    "请盯住这里**换了什么、没换什么**：\n",
    "\n",
    "- **换了描述符**：`key_mapping=PrefixDigitMapping` → `descriptor=triangle`；\n",
    "- **换了扇出**：2 → 4（一个三角形细分成 4 个子三角形）；\n",
    "- **没换结构**：仍然是\"每层把描述符细分，每个孩子持有一份\"。\n",
    "\n",
    "同一套 Trie 代码，换一个描述符就从字符串索引变成了空间索引——这是本实验最值得体会的一点。\n",
    "\n",
    "下一格用 `ipycanvas` 把这棵树画出来（只在 Jupyter 里可见）。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-20T08:03:11.011155Z",
     "start_time": "2024-12-20T08:03:11.005167Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Christmas tree:\n",
      "∆((0, 0), (300, 0), (150, 300))\n",
      "RadixTrie:\n",
      "\tInnerNode {\n",
      "\t\tdescriptor:  ∆((0, 0), (150.0, 0.0), (75.0, 150.0))\n",
      "\t\tInnerNode {\n",
      "\t\t\tdescriptor:  ∆((0, 0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((0, 0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((18.75, 37.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((37.5, 0.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((56.25, 37.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((37.5, 75.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((37.5, 75.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((56.25, 112.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((75.0, 75.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((93.75, 112.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((75.0, 0.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((75.0, 0.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((93.75, 37.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((112.5, 0.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((131.25, 37.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((112.5, 75.0), (-75.0, -0.0), (-37.5, -75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((112.5, 75.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((93.75, 37.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((75.0, 75.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((56.25, 37.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t}\n",
      "\t\tdescriptor:  ∆((75.0, 150.0), (150.0, 0.0), (75.0, 150.0))\n",
      "\t\tInnerNode {\n",
      "\t\t\tdescriptor:  ∆((75.0, 150.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((75.0, 150.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((93.75, 187.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((112.5, 150.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((131.25, 187.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((112.5, 225.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((112.5, 225.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((131.25, 262.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((150.0, 225.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((168.75, 262.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((150.0, 150.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((150.0, 150.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((168.75, 187.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((187.5, 150.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((206.25, 187.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((187.5, 225.0), (-75.0, -0.0), (-37.5, -75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((187.5, 225.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((168.75, 187.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((150.0, 225.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((131.25, 187.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t}\n",
      "\t\tdescriptor:  ∆((150.0, 0.0), (150.0, 0.0), (75.0, 150.0))\n",
      "\t\tInnerNode {\n",
      "\t\t\tdescriptor:  ∆((150.0, 0.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((150.0, 0.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((168.75, 37.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((187.5, 0.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((206.25, 37.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((187.5, 75.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((187.5, 75.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((206.25, 112.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((225.0, 75.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((243.75, 112.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((225.0, 0.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((225.0, 0.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((243.75, 37.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((262.5, 0.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((281.25, 37.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((262.5, 75.0), (-75.0, -0.0), (-37.5, -75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((262.5, 75.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((243.75, 37.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((225.0, 75.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((206.25, 37.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t}\n",
      "\t\tdescriptor:  ∆((225.0, 150.0), (-150.0, -0.0), (-75.0, -150.0))\n",
      "\t\tInnerNode {\n",
      "\t\t\tdescriptor:  ∆((225.0, 150.0), (-75.0, -0.0), (-37.5, -75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((225.0, 150.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((206.25, 112.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((187.5, 150.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((168.75, 112.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((187.5, 75.0), (-75.0, -0.0), (-37.5, -75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((187.5, 75.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((168.75, 37.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((150.0, 75.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((131.25, 37.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((150.0, 150.0), (-75.0, -0.0), (-37.5, -75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((150.0, 150.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((131.25, 112.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((112.5, 150.0), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((93.75, 112.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t\tdescriptor:  ∆((112.5, 75.0), (75.0, 0.0), (37.5, 75.0))\n",
      "\t\t\tInnerNode {\n",
      "\t\t\t\tdescriptor:  ∆((112.5, 75.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((131.25, 112.5), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((150.0, 75.0), (37.5, 0.0), (18.75, 37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t\tdescriptor:  ∆((168.75, 112.5), (-37.5, -0.0), (-18.75, -37.5))\n",
      "\t\t\t\tLeafNode {\n",
      "\t\t\t\t  values: []\n",
      "\t\t\t\t},\n",
      "\t\t\t}\n",
      "\t\t}\n",
      "\t}\n"
     ]
    }
   ],
   "source": [
    "from system.indexes.christmas_tree import ChristmasTree\n",
    "\n",
    "triangle: Triangle = Triangle(Vector(0, 0), Vector(300, 0), Vector(150, 300))\n",
    "christmas_trie: ChristmasTree[Vector, str] = ChristmasTree[Vector, str](\n",
    "    children_per_inner_node=4,\n",
    "    descriptor=triangle,\n",
    "    number_of_inner_node_levels=3,\n",
    ")\n",
    "christmas_trie.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**预期看到什么**：同样的公式，取 $c = 4$、$L = 3$：\n",
    "\n",
    "$$\\text{内部节点} = 1 + 4 + 16 = 21, \\qquad \\text{叶子} = 4^3 = 64$$\n",
    "\n",
    "64 个叶子就是把大三角形递归细分 3 层后得到的 64 个子区域。\n",
    "\n",
    "### 验证\"包含\"判定\n",
    "\n",
    "本机实测（`Triangle((0,0), (300,0), (150,300))`）：\n",
    "\n",
    "| 点 | `contains` |\n",
    "|---|---|\n",
    "| (150, 100) | True |\n",
    "| (10, 10) | True |\n",
    "| (150, 290) | True |\n",
    "| (299, 1) | True |\n",
    "| (1, 299) | False |\n",
    "\n",
    "（150, 290）靠近顶点仍在内部，（1, 299）明显在三角形外——判定正确。\n",
    "\n",
    "### 值得探究的问题：细分结果不符合预期\n",
    "\n",
    "下面这段值得你自己跑一遍：\n",
    "\n",
    "```python\n",
    "subs = list(triangle.split_into_sub_descriptors())\n",
    "print(\"子描述符个数:\", len(subs))\n",
    "for i, s in enumerate(subs):\n",
    "    print(f\"  {i}: {s}\")\n",
    "```\n",
    "\n",
    "**本机实测输出**：\n",
    "\n",
    "```text\n",
    "子描述符个数: 4\n",
    "  0: ∆((0, 0), (150.0, 0.0), (75.0, 150.0))\n",
    "  1: ∆((75.0, 150.0), (150.0, 0.0), (75.0, 150.0))\n",
    "  2: ∆((150.0, 0.0), (150.0, 0.0), (75.0, 150.0))\n",
    "  3: ∆((225.0, 150.0), (-150.0, -0.0), (-75.0, -150.0))\n",
    "```\n",
    "\n",
    "**本机实测结果与预期不符，请查看源码并判断。** 两处值得追问：\n",
    "\n",
    "1. 第 1、2 个子三角形出现**重复顶点**（第 1 个的第 1、3 个顶点都是 `(75,150)`；第 2 个的前两个顶点都是 `(150,0)`），即它们是**退化三角形**（面积为 0）；\n",
    "2. 第 3 个子三角形出现**负坐标** `(-150, 0)`、`(-75, -150)`，落在大三角形之外。\n",
    "\n",
    "**正确的做法**应当是取三条边的中点，把三角形分成 4 个全等的小三角形，全部落在原三角形内部。设顶点 $A(0,0)$、$B(300,0)$、$C(150,300)$，三边中点为：\n",
    "\n",
    "- $M_{AB}(150, 0)$\n",
    "- $M_{AC}(75, 150)$\n",
    "- $M_{BC}(225, 150)$\n",
    "\n",
    "4 个子三角形应为：\n",
    "\n",
    "1. $\\triangle(A,\\ M_{AB},\\ M_{AC})$ = `((0,0), (150,0), (75,150))`\n",
    "2. $\\triangle(M_{AB},\\ B,\\ M_{BC})$ = `((150,0), (300,0), (225,150))`\n",
    "3. $\\triangle(M_{AC},\\ M_{BC},\\ C)$ = `((75,150), (225,150), (150,300))`\n",
    "4. $\\triangle(M_{AB},\\ M_{BC},\\ M_{AC})$ = `((150,0), (225,150), (75,150))` —— 中间那个**倒置**的三角形\n",
    "\n",
    "这 4 个都非退化、都落在原三角形内，面积各为原三角形的 1/4。\n",
    "\n",
    "**为什么这件事重要**：`contains()` 用重心坐标实现，在退化三角形上会除零或给出无意义结果；落在原三角形外的子描述符则会让整棵树的区域划分出错。所以细分的正确性完全由描述符的实现者负责。\n",
    "\n",
    "请打开 `system/utils.py` 里 `Triangle.split_into_sub_descriptors()` 的源码，画出它的取点逻辑，判断问题出在哪，并尝试改成取三边中点的版本，再重跑验证。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-20T08:03:11.051945Z",
     "start_time": "2024-12-20T08:03:11.048272Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "5d321be7060f4fd88263ee55ff13ea26",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(height=300, sync_image_data=True, width=300)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "canvas = Canvas(width=300, height=300, sync_image_data=True)\n",
    "display(canvas)\n",
    "with hold_canvas(canvas):\n",
    "    christmas_trie.draw(canvas, canvas_height=300)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Animated tree：动态地往树里插点**\n",
    "\n",
    "上一格看到的是一棵**空树**的 64 个区域划分。这一格做一件更有意思的事：**随机往三角形里撒点，每撒一批就重画一次**，看这棵树被\"填充\"的过程。\n",
    "\n",
    "```python\n",
    "inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](config=\"crystalball\")\n",
    "```\n",
    "\n",
    "这一行是三种节点工厂配置之一，控制\"子描述符什么时候被算出来\"：\n",
    "\n",
    "| 配置 | 做法 | 取舍 |\n",
    "|---|---|---|\n",
    "| `inner` | 按需计算，不缓存 | 内存最省，重复访问要重算 |\n",
    "| `buffered` | 第一次算完缓存起来 | 空间换时间，适合反复访问 |\n",
    "| `crystalball` | 预先算好并持有 | 访问最快，构建时一次性付出全部代价 |\n",
    "\n",
    "逐层细分时越深的层持有的描述符越多（$c=4, L=3$ 时第 3 层有 16 个内部节点、叶子 64 个），如果每次访问都重新计算子描述符，代价很高——所以才有这三种策略。\n",
    "\n",
    "**预期看到什么**：20 帧动画（每帧间隔 0.2 秒），点逐渐填满三角形，越填越密。`crystalball` 配置下构建会稍慢一点，但后续每帧绘制不需要重算。\n",
    "\n",
    "**没有\"最好\"的配置，只有\"匹配访问模式\"的配置**——这是本实验要传达的一个工程判断。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "start_time": "2024-12-20T08:03:11.072356Z"
    },
    "jupyter": {
     "is_executing": true
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "533daad21f874ed59b4e2e955244c44d",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(height=300, sync_image_data=True, width=300)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "number_of_trees: int = 20\n",
    "size: int = 300\n",
    "canvas = Canvas(width=size, height=size, sync_image_data=True)\n",
    "import random as rnd\n",
    "from time import sleep\n",
    "\n",
    "triangle: Triangle = Triangle(Vector(0, 0), Vector(size, 0), Vector(size / 2, size))\n",
    "christmas_trie: ChristmasTree[Vector, str] = ChristmasTree[Vector, str](\n",
    "    children_per_inner_node=4,\n",
    "    descriptor=triangle,\n",
    "    number_of_inner_node_levels=3,\n",
    "    # inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](config=\"inner\")\n",
    "    # inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](config=\"buffered\")\n",
    "    inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](\n",
    "        config=\"crystalball\"\n",
    "    ),\n",
    ")\n",
    "\n",
    "display(canvas)\n",
    "\n",
    "for tree in range(number_of_trees):\n",
    "    with hold_canvas(canvas):\n",
    "        canvas.clear()\n",
    "        for i in range(size):\n",
    "            v: Vector\n",
    "            while True:\n",
    "                v = Vector(rnd.randint(0, size), rnd.randint(0, size))\n",
    "                if triangle.contains(v):\n",
    "                    break\n",
    "            christmas_trie.put(v, str(i))\n",
    "        christmas_trie.draw(canvas, canvas_height=size, x_offset=0)\n",
    "        sleep(0.2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Each phase of the tree shown separately：把各个阶段并排画出来**\n",
    "\n",
    "与上一格的区别是：这里**不清空画布**（`canvas.clear()` 被注释掉了），而是把每一批插入的结果画在画布的不同横向位置上（`x_offset = tree * size + space_in_between * tree`）。于是 5 个阶段从左到右并排显示，可以直接比较\"点越来越多时，树长什么样\"。\n",
    "\n",
    "每批插入 1000 个点，随机采样的写法是\"先随机取点，若不在三角形内就重取\"（拒绝采样）：\n",
    "\n",
    "```python\n",
    "while True:\n",
    "    v = Vector(rnd.randint(0, size), rnd.randint(0, size))\n",
    "    if triangle.contains(v):\n",
    "        break\n",
    "christmas_trie.put(v, str(i))\n",
    "```\n",
    "\n",
    "**预期看到什么**：5 幅并排的图，从左到右逐渐变密。注意观察：**无论撒多少个点，区域划分（64 个叶子）始终不变**——这正是\"固定细分\"的特征，也是它与 R-tree 最本质的差别（见思考题）。\n",
    "\n",
    "最后两格分别做收尾：`flush_all_buffers()` 把缓冲的绘制指令刷出，再单独重画一次。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-19T08:04:19.874796Z",
     "start_time": "2024-12-11T08:29:34.763115Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "81bd819c130a47c6bf863135b0612173",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(height=200, sync_image_data=True, width=1080)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "number_of_trees: int = 5\n",
    "size: int = 200\n",
    "space_in_between: int = 20\n",
    "canvas = Canvas(\n",
    "    width=size * number_of_trees + (number_of_trees - 1) * space_in_between,\n",
    "    height=size,\n",
    "    sync_image_data=True,\n",
    ")\n",
    "import random as rnd\n",
    "from time import sleep\n",
    "\n",
    "triangle: Triangle = Triangle(Vector(0, 0), Vector(size, 0), Vector(size / 2, size))\n",
    "christmas_trie: ChristmasTree[Vector, str] = ChristmasTree[Vector, str](\n",
    "    children_per_inner_node=4,\n",
    "    descriptor=triangle,\n",
    "    number_of_inner_node_levels=3,\n",
    "    # inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](config=\"inner\")\n",
    "    # inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](config=\"buffered\")\n",
    "    inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](\n",
    "        config=\"crystalball\"\n",
    "    ),\n",
    ")\n",
    "\n",
    "display(canvas)\n",
    "\n",
    "for tree in range(number_of_trees):\n",
    "    with hold_canvas(canvas):\n",
    "        # canvas.clear()\n",
    "        for i in range(1000):\n",
    "            v: Vector\n",
    "            while True:\n",
    "                v = Vector(rnd.randint(0, size), rnd.randint(0, size))\n",
    "                if triangle.contains(v):\n",
    "                    break\n",
    "            christmas_trie.put(v, str(i))\n",
    "        christmas_trie.draw(\n",
    "            canvas, canvas_height=size, x_offset=tree * size + space_in_between * tree\n",
    "        )\n",
    "        # sleep(0.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-19T08:04:19.874929Z",
     "start_time": "2024-12-11T08:29:41.591579Z"
    }
   },
   "outputs": [],
   "source": [
    "christmas_trie.flush_all_buffers()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-19T08:04:19.875001Z",
     "start_time": "2024-12-11T08:29:41.597610Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "75e11fdd6f1d45d4a2603d99f29fd2d1",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(height=200, sync_image_data=True, width=200)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "canvas = Canvas(width=size, height=size, sync_image_data=True)\n",
    "display(canvas)\n",
    "with hold_canvas(canvas):\n",
    "    christmas_trie.draw(canvas, canvas_height=size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-19T08:04:19.875076Z",
     "start_time": "2024-12-11T08:29:41.629045Z"
    }
   },
   "outputs": [],
   "source": [
    "# christmas_trie.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-19T08:04:19.875138Z",
     "start_time": "2024-12-11T08:29:41.638372Z"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 思考题与详解\n",
    "\n",
    "> 建议先自己写一遍答案，再展开对照。\n",
    "\n",
    "**1. 标准 Trie 的查找代价是 $O(\\text{键长})$，B+ 树是 $O(\\log n)$。当表里有 100 万行、键长固定为 10 时，哪个更快？请说明理由，并指出这个比较里隐含了什么假设。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "键长固定为 10 时，Trie 的查找是 10 步指针跳转，与行数无关；B+ 树要 $\\log_F n$ 次比较（$F$ 为扇出，取 $F \\approx 100$、$n = 10^6$ 时约 3 次）。**单看比较次数，Trie 未必占优**；Trie 的真正优势是**代价不随数据量增长**——数据涨到 10 亿行时 B+ 树要 4~5 次，Trie 还是 10 步。\n",
    "\n",
    "**隐含的假设**（必须点明）：\n",
    "\n",
    "- 假设每次指针跳转代价相同。实际上 Trie 的 10 次跳转访问 10 个不同节点，**几乎每次都 cache miss**；B+ 树的前几层常驻 cache，实际可能更快。\n",
    "- 假设键长真的固定且很短。键长可变且很长（如 URL）时，Trie 的层数被最长键拉高，代价迅速恶化。\n",
    "\n",
    "**结论**：复杂度阶相同不代表实际性能相同，必须把\"指针跳转 vs 顺序比较\"\"cache 命中率\"这些常数因子算进去。本案例库实验 07 的 RMI 也踩过同一个坑——算法更优，但常数因子输给了语言内建实现。\n",
    "\n",
    "</details>\n",
    "\n",
    "**2. 本实验的二进制 Trie（$c=2, L=3$）存 5 个键却用了 8 个叶子（3 个空）。若改用路径压缩，叶子数会变成多少？请画出来。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "5 个键：`110`→a、`101`→b、`010`→c、`011`→d、`111`→e。\n",
    "\n",
    "压缩后：\n",
    "\n",
    "```text\n",
    "(root)\n",
    " ├── \"01\" → { 0 → c, 1 → d }        # 010, 011 共享前缀 01\n",
    " └── \"1\"  → { 01 → b,               # 101\n",
    "              10 → a,               # 110\n",
    "              11 → e }              # 111\n",
    "```\n",
    "\n",
    "叶子数从 8 降到 **5**（正好等于键的个数，一个空叶子都不剩）；内部节点从 7 降到 3 个（根 + `\"01\"` + `\"1\"`）。\n",
    "\n",
    "**这就是路径压缩的价值**：把\"满树\"变成\"按需生长的树\"，空间与**键的数量**成正比，而不是与 $c^L$ 成正比。\n",
    "\n",
    "</details>\n",
    "\n",
    "**3. 圣诞树把扇出从 2 提到 4、层数保持 3，叶子数从 8 变成 64。如果目标是\"把 300×300 的区域划分成边长约 10 的小格\"，需要多少层、多少叶子？这个数字说明什么？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "每次细分把边长减半（三角形分成 4 个全等小三角形，边长为原来的一半）。要从 300 降到约 10：\n",
    "\n",
    "$$300 / 2^{L} \\approx 10 \\ \\Longrightarrow\\ 2^{L} \\approx 30 \\ \\Longrightarrow\\ L \\approx 5$$\n",
    "\n",
    "5 层：叶子数 $4^5 = 1024$，内部节点 $\\sum_{i=0}^{4} 4^i = 341$，**合计 1365 个节点**。\n",
    "\n",
    "6 层（边长降到 4.7）：叶子 $4^6 = 4096$，合计 5461 个节点。\n",
    "\n",
    "**这个数字说明**：靠固定细分去追求\"精细\"，代价是**指数级**的。真实的空间索引（R-tree、四叉树）从不预先细分到固定深度——它们按需分裂，数据稀疏的地方保持大区域，数据密集的地方才继续分。\n",
    "\n",
    "</details>\n",
    "\n",
    "**4. 描述符（descriptor）这个抽象带来了什么好处？如果不用描述符、直接写死\"按字符走\"，圣诞树还能实现吗？代价是什么？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "描述符带来的是**\"如何把一个键切成段、每段映射到哪个孩子\"的策略与树结构解耦**：\n",
    "\n",
    "- 用 `PrefixDigitMapping`：按字符切，是字符串 Trie；\n",
    "- 用 `Triangle`：按几何细分，是空间 Trie。\n",
    "\n",
    "树本身只关心\"每个内部节点有 $c$ 个孩子，孩子各自持有一个子描述符\"。\n",
    "\n",
    "如果不用描述符、直接写死\"按字符走\"，要实现圣诞树就得**再写一套树**——两套代码各自维护、各自出 bug。用了描述符，只需要提供一个实现 `contains` 与 `split_into_sub_descriptors` 的类。\n",
    "\n",
    "**代价是抽象成本**：描述符必须是不可变的（细分后原描述符不能被改），否则父节点持有的区域会与孩子的区域不一致；而且细分逻辑的正确性完全由描述符的实现者负责——本笔记本\"值得探究的问题\"一节发现的细分结果异常，问题就出在这里。\n",
    "\n",
    "</details>\n",
    "\n",
    "**5. `buffered` 与 `crystalball` 都在\"预计算\"上做文章。请设想两种访问模式，分别说明哪种配置更合适；再设想一种两种都不合适的模式。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "- **适合 `crystalball`**：构建一次、查询极多，且各层访问频率均匀（如长期服务的空间索引）。预先算好全部子描述符，查询时零计算。\n",
    "- **适合 `buffered`**：查询分布不均匀，只有部分区域被频繁访问（如城市 POI 检索，市中心热、郊区冷）。按需缓存，冷区域永远不付计算代价。\n",
    "- **适合 `inner`**：构建后只查询很少几次（如临时的一次性分析），或内存极度紧张。预计算的成本收不回来。\n",
    "\n",
    "**两种都不合适的模式**：构建后一次都不查（纯浪费），或查询模式完全随机且每个区域只查一次。后者用 `buffered` 会不断触发首次计算，缓存命中率为 0，白白付出缓存管理的开销——此时 `inner` 反而最好。\n",
    "\n",
    "**这三类配置的实际耗时差别需自行实测确认**（可分别构建 $c=4, L=4$ 的圣诞树测构建耗时，再随机查询 10,000 个点测总耗时）。\n",
    "\n",
    "</details>\n",
    "\n",
    "**6. 本机实测 `split_into_sub_descriptors()` 的结果与预期不符。若改成\"取三边中点\"，4 个子三角形的顶点坐标分别是什么？改完之后 `contains()` 还需要改吗？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "设三角形顶点 $A(0,0)$、$B(300,0)$、$C(150,300)$。三边中点：\n",
    "\n",
    "- $M_{AB}(150, 0)$\n",
    "- $M_{AC}(75, 150)$\n",
    "- $M_{BC}(225, 150)$\n",
    "\n",
    "4 个子三角形为：\n",
    "\n",
    "1. $\\triangle(A,\\ M_{AB},\\ M_{AC})$ = `((0,0), (150,0), (75,150))`\n",
    "2. $\\triangle(M_{AB},\\ B,\\ M_{BC})$ = `((150,0), (300,0), (225,150))`\n",
    "3. $\\triangle(M_{AC},\\ M_{BC},\\ C)$ = `((75,150), (225,150), (150,300))`\n",
    "4. $\\triangle(M_{AB},\\ M_{BC},\\ M_{AC})$ = `((150,0), (225,150), (75,150))` —— 中间那个**倒置**的三角形\n",
    "\n",
    "4 个都非退化、都落在原三角形内，面积各为原三角形的 $1/4$。\n",
    "\n",
    "**`contains()` 不需要改。** 重心坐标法对任意方向的三角形都成立，倒三角形也一样——关键是三个顶点不能共线（不能退化）。这也反证了退化三角形的危害：`contains()` 在退化三角形上会除零或给出无意义结果。\n",
    "\n",
    "</details>\n",
    "\n",
    "**7. 圣诞树递归细分得到的是**固定**的区域划分，而 R-tree 是**按需**分裂。请比较两者在\"数据分布极不均匀\"（例如 90% 的点挤在 5% 的面积里）时的表现。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "- **固定细分（圣诞树）**：无论数据怎么分布，都把区域划成同样大小的 $4^L$ 块。数据挤在 5% 面积里时，那 5% 里的块塞满了点（查找退化成在块内线性扫描），另外 95% 的块全是空的（白白占用节点）。$L$ 小则热点太挤，$L$ 大则空块太多——**永远两头不讨好**。\n",
    "- **按需分裂（R-tree / 四叉树）**：数据密集的地方继续分裂，稀疏的地方保持大块。节点数与**数据量**成正比，而不是与\"区域面积 / 最小粒度\"成正比。热点区域自动获得更细的划分。\n",
    "\n",
    "这正是 R-tree（Guttman, SIGMOD 1984）成为空间索引主流的原因，也是 PostgreSQL 的 GiST / SP-GiST 与 PostGIS 采用它的原因（出处：Guttman, *R-trees: A Dynamic Index Structure for Spatial Searching*, SIGMOD 1984）。\n",
    "\n",
    "**不过固定细分并非一无是处**：Geohash、H3、S2 这些\"网格编码\"本质上就是固定细分，它们的优势是**编码可以直接比较、可以用普通 B+ 树索引**，实现简单、分布式友好（见实验 16）。\n",
    "\n",
    "</details>\n",
    "\n",
    "**8. 本笔记本里\"固定扇出\"的规模公式是 $\\sum c^i$ 与 $c^L$。请说明：为什么即使一个键都没存，这棵树也已经有这么多节点？这和\"路径压缩\"解决的正是同一个问题吗？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "因为构造函数是按参数**预先把树建满**的：给定 $c$ 和 $L$，它就生成 $\\sum_{i=0}^{L-1} c^i$ 个内部节点和 $c^L$ 个叶子，每个内部节点一开始就持有 $c$ 个子描述符。这与存了多少键无关——存 0 个键时，64 个叶子全是空的。\n",
    "\n",
    "这与路径压缩解决的是**同一个问题的两个侧面**，但机制不同：\n",
    "\n",
    "- 固定扇出的问题是\"**预留了用不上的节点**\"：空间与 $c^L$ 成正比，而不是与实际键数成正比。\n",
    "- 路径压缩的做法是\"**把单孩子链合并**\"：它不预留空节点，而是让树随键一起生长，空间与键的数量成正比。\n",
    "\n",
    "所以严格说，路径压缩解决的是\"链太长\"，而\"预先建满\"要靠\"按需生长\"（不为不存在的键创建分支）来解决。二者在真实实现里通常一起出现：**基数树既做路径压缩，也按需创建节点**。本仓库为了把\"固定扇出的规模公式\"讲清楚，选择了预先建满的写法——这正是你在输出里看到 3 个空叶子的原因。\n",
    "\n",
    "</details>\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.6"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}