[Root]
           /      \
        [hAB]    [hCD]
        /   \    /   \
      [hA] [hB][hC] [hD]
       |    |    |    |
       A    B    C    D

            [Root']  ← 对比已知 Root
           /      \
        [hAB]    [hCD']  ← 计算
        /   \    /    \
      [hA] [hB][hC']  [hD]
       ↑Proof  ↑计算   ↑Proof
              C 的余额

                root
               /    \
              a      d
              |      |
              3      e
              |      |
              f      1
             / \     |
            7   9    2
            |   |    |
            b   d    c
            |   |    |
           10  20   30

                root [a,d; nil] <- Branch
                     /   \
Extension -> [3,f; next] [e,1,2,c; 30] <- Leaf
                     |
                [7,9; nil] <- Branch
                /   \
          [b; 10]   [d; 20] <- Leaf

[Nibble 编码的分支节点]
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ a │ b │ c │ d │ e │ f │ value │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───────┘
  16 个槽位，每个对应一个 nibble 值

叶子节点的 nibble 数组: [n1, n2, ..., nk, 0x10]
                                          ↑
                                        终止符
表示：路径到这里结束，后面跟着的是实际的值

扩展节点的 nibble 数组: [n1, n2, ..., nk]
表示：路径还没有结束，后面跟着的是另一个节点的引用

Nibble 数组 A: [0xa]         （长度 1，奇数）
          ↓ 补零
          [0x0, 0xa]
          ↓ 打包
          字节: 0x0a

Nibble 数组 B: [0x0, 0xa]    （长度 2，偶数）
          ↓ 打包
          字节: 0x0a

解码时拿到 0x0a，无法知道原来是一个 nibble 还是两个 nibble！

叶子节点原始数组: [0xa, 0x3, 0xf, 0x10]
          ↓ 移除终止符
          [0xa, 0x3, 0xf]（长度 3，奇数）
          ↓ 补零
          [0x0, 0xa, 0x3, 0xf]
          ↓ 打包
          字节: 0x0a 0x3f

扩展节点原始数组: [0xa, 0x3, 0xf]（长度 3，奇数）
          ↓ 补零
          [0x0, 0xa, 0x3, 0xf]
          ↓ 打包
          字节: 0x0a 0x3f

解码时拿到 0x0a 0x3f，无法知道是叶子节点还是扩展节点！

标志 nibble: b3 b2 b1 b0
             │  │  │  │
             │  │  │  └─ 长度奇偶位: 0 = 偶数，1 = 奇数
             │  │  └──── 节点类型位: 0 = 扩展节点，1 = 叶子节点
             │  └─────── 保留位: 始终为 0
             └────────── 保留位: 始终为 0

原来两个冲突的情况，加上标志后不再冲突：

长度奇偶歧义解决：
  [0xa]（奇数扩展）→ 标志 0x1 → [0x1, 0xa]         → 打包: 0x1a
  [0x0, 0xa]（偶数扩展）→ 标志 0x0 → [0x0, 0x0, 0xa] → 补零 → 打包: 0x00 0x0a

节点类型歧义解决：
  叶子 [0xa, 0x3, 0xf] → 标志 0x3 → [0x3, 0xa, 0x3, 0xf] → 打包: 0x3a 0x3f
  扩展 [0xa, 0x3, 0xf] → 标志 0x1 → [0x1, 0xa, 0x3, 0xf] → 打包: 0x1a 0x3f

原始叶子节点，nibble 数组: [0xa, 0x3, 0xf, 0x7, 0xb, 0x10]
                                                     ↑
                                                   终止符

步骤 1: 去掉终止符
        [0xa, 0x3, 0xf, 0x7, 0xb]（长度 5，奇数）

步骤 2: 确定标志值
        叶子节点 + 奇数长度 → 标志 = 0x3

步骤 3: 构造第一个字节
        高 4 位: 标志 0x3；低 4 位: 第一个 nibble 0xa（奇数长度）→ 0x3a
        剩余 nibble: [0x3, 0xf, 0x7, 0xb]

步骤 4: 剩余 nibble 打包
        [0x3a, 0x3f, 0x7b]

原始扩展节点，nibble 数组: [0x3, 0xf]（长度 2，偶数）

步骤 1: 不需要去掉终止符（扩展节点没有终止符）

步骤 2: 确定标志值
        扩展节点 + 偶数长度 → 标志 = 0x0

步骤 3: 构造第一个字节
        高 4 位: 标志 0x0；低 4 位: 0x0（偶数长度，填零）→ 0x00
        剩余 nibble: [0x3, 0xf]

步骤 4: 剩余 nibble 打包
        [0x00, 0x3f]

步骤 1: 拆成 nibble 数组
        [0x3, 0xa, 0x3, 0xf, 0x7, 0xb]

步骤 2: 提取标志
        0x3 → 二进制 0011 → 叶子节点，原始长度奇数

步骤 3: 去掉标志（奇数长度只去掉 1 个 nibble）
        [0xa, 0x3, 0xf, 0x7, 0xb]

步骤 4: 因为是叶子节点，添加终止符
        [0xa, 0x3, 0xf, 0x7, 0xb, 0x10]

原结构（单个 Leaf 节点）：

[a,3,f,7,b; A] <- Leaf

    ↓ 插入 0xa3f9d → B，路径在 [a,3,f] 后分裂

Extension -> [a,3,f; next]
                       |
                    [7, 9; nil] <- Branch
                    /    \
                [b; A]  [d; B] <- Leaf

原结构（删除 0xa3f9d 后，Branch 只剩一个子节点，自身无值）：

Extension -> [a,3,f; next]
                  |
                [7; nil] <- Branch（只剩一个子节点，自身无值）
                /
            [b; A] <- Leaf

    ↓ Branch 只有一个子节点且自身无值，合并为 Leaf

[a,3,f,7,b; A] <- Leaf

Branch 自身有值 D，只有一个子节点 [0x7]：

Extension -> [a,3,f; next]
                  |
                [7; D] <- Branch（有值，不能合并）
                /
            [b; A] <- Leaf

    ✗ 不能合并为 [a,3,f,7,b; A]（<- Leaf）
      因为这样会丢失 Branch 自身存储的值 D

// get: 在以 node 为根的子树中查找 key 对应的值
// 参数:
//   node - 当前节点
//   key  - 完整的 nibble 数组
//   pos  - 当前已消耗的 nibble 数量（即 key 中下一个待匹配的位置）
// 返回值: 目标值（存在时）或 nil（不存在时）
function get(node, key, pos):
    if node is nil:
        return nil  // 空节点，键不存在

    switch node.type:
        case Branch:
            if pos == len(key):
                return node.value  // key 所有 nibble 已消耗完毕，返回 Branch 自身的值
            nibble = key[pos]  // 取当前待匹配的 nibble
            return get(node.children[nibble], key, pos + 1)  // 进入对应槽位，消耗 1 个 nibble

        case Extension:
            prefix = node.encodedPath
            if !matchPrefix(key, pos, prefix):
                return nil  // key 在 pos 位置开始的部分与扩展前缀不匹配，键不存在
            return get(node.next, key, pos + len(prefix))  // 前缀匹配，跳过整个前缀长度，递归进入子节点

        case Leaf:
            suffix = node.encodedPath
            if matchSuffix(key, pos, suffix):
                return node.value  // 剩余部分完全匹配，返回 Leaf 存储的值
            return nil  // 剩余部分不匹配，键不存在

步骤 1: 从根 Branch 开始，pos = 0
        nibble = key[0] = 0xa
        递归查找 children[0xa] → Extension

步骤 2: 在 Extension 节点，pos = 1
        prefix = [0x3, 0xf]
        匹配 key[1:3] = [0x3, 0xf] ✓
        递归查找 next → Branch，pos = 3

步骤 3: 在 Branch 节点，pos = 3
        nibble = key[3] = 0x9
        递归查找 children[0x9] → Leaf

步骤 4: 在 Leaf 节点，pos = 4
        suffix = [0xd]
        匹配 key[4:5] = [0xd] ✓
        返回值 B

// insert: 在以 node 为根的子树中插入或更新 key → value
// 参数:
//   node  - 当前节点
//   key   - 待插入的 nibble 数组（当前位置到末尾的剩余部分）
//   value - 待关联的值
// 返回值: 插入/更新后的子树根节点
function insert(node, key, value):
    if node is nil:
        return Leaf(key, value)  // 空位置，直接创建 Leaf

    switch node.type:
        case Leaf:
            if key == node.encodedPath:
                return Leaf(key, value)  // 路径完全匹配，用新值替换
            // 路径分叉：找到共同前缀长度，创建 Branch 在分叉点分岔
            commonLen = prefixLen(key, node.encodedPath)
            branch = new Branch()

            // 将原 Leaf 的分叉 nibble 之后的剩余路径插入 Branch
            oldSuffix = node.encodedPath[commonLen+1:]
            if len(oldSuffix) == 0:
                branch.value = node.value  // 原路径在分叉点结束，值存入 Branch 的 value 槽位
            else:
                branch.children[oldSuffix[0]] = Leaf(oldSuffix[1:], node.value)  // 消耗分叉 nibble，剩余作为 Leaf

            // 将新 key 的分叉 nibble 之后的剩余路径插入 Branch
            newSuffix = key[commonLen+1:]
            if len(newSuffix) == 0:
                branch.value = value  // 新路径在分叉点结束，值存入 Branch 的 value 槽位
            else:
                branch.children[newSuffix[0]] = Leaf(newSuffix[1:], value)  // 消耗分叉 nibble，剩余作为 Leaf

            // 如果有共同前缀，用 Extension 包装 Branch
            if commonLen > 0:
                return Extension(key[:commonLen], branch)
            return branch

        case Extension:
            extKey = node.encodedPath
            commonLen = prefixLen(key, extKey)

            if commonLen == len(extKey):
                // key 完全匹配扩展前缀，递归插入子节点
                newChild = insert(node.next, key[commonLen:], value)
                return Extension(extKey, newChild)
            else:
                // key 仅部分匹配扩展前缀，需要分裂 Extension
                branch = new Branch()

                // 保留原 Extension 的分叉 nibble 之后的路径
                oldSuffix = extKey[commonLen+1:]
                if len(oldSuffix) == 0:
                    branch.children[extKey[commonLen]] = node.next  // 原路径在分叉点直接连接子节点
                else:
                    branch.children[extKey[commonLen]] = Extension(oldSuffix, node.next)  // 剩余部分仍为 Extension

                // 插入新 key 的分叉 nibble 之后的路径
                newSuffix = key[commonLen+1:]
                if len(newSuffix) == 0:
                    branch.value = value  // 新路径在分叉点结束
                else:
                    branch.children[newSuffix[0]] = Leaf(newSuffix[1:], value)

                // 如果有共同前缀，用 Extension 包装 Branch
                if commonLen > 0:
                    return Extension(key[:commonLen], branch)
                return branch

        case Branch:
            if len(key) == 0:
                node.value = value  // key 所有 nibble 已消耗完毕，更新 Branch 自身的值
                return node
            nibble = key[0]  // 取当前待匹配的 nibble
            node.children[nibble] = insert(node.children[nibble], key[1:], value)  // 递归插入，消耗 1 个 nibble
            return node

原结构：nil
插入 0xa3f7b → A 后：
[a,3,f,7,b; A] <- Leaf

原结构（单个 Leaf 节点）：

[a,3,f,7,b; A] <- Leaf

    ↓ 插入 0xa3f9d → B，路径在 [a,3,f] 后分裂

Extension -> [a,3,f, next]
                       |
                    [7, 9; nil] <- Branch
                    /    \
                [b; A]  [d; B] <- Leaf

// delete: 在以 node 为根的子树中删除 key 对应的键值对
// 参数:
//   node - 当前节点
//   key  - 待删除的 nibble 数组（当前位置到末尾的剩余部分）
// 返回值: (更新后的子树根节点, 是否删除成功)
function delete(node, key):
    if node is nil:
        return nil, false  // 空节点，删除失败

    switch node.type:
        case Leaf:
            if key == node.encodedPath:
                return nil, true  // 路径完全匹配，删除节点（返回 nil 表示节点已移除）
            return node, false  // 路径不匹配，删除失败

        case Extension:
            extKey = node.encodedPath
            if !startsWith(key, extKey):
                return node, false  // key 不以扩展前缀开头，键不存在

            // 递归删除子节点，传入剥离前缀后的剩余 key
            newChild, deleted = delete(node.next, key[len(extKey):])
            if !deleted:
                return node, false  // 子树删除失败，整体不变

            if newChild is nil:
                return nil, true  // 子节点被完全移除，Extension 失去子节点，自身也移除

            // 子节点仍存在，检查是否可以合并（缩短路径）
            if newChild is Leaf:
                return Leaf(extKey + newChild.encodedPath, newChild.value), true  // Extension + Leaf 合并为新 Leaf
            if newChild is Extension:
                return Extension(extKey + newChild.encodedPath, newChild.next), true  // 两个 Extension 合并前缀

            return Extension(extKey, newChild), true  // 子节点是 Branch，无法合并，保持原结构

        case Branch:
            if len(key) == 0:
                node.value = nil  // key 所有 nibble 已消耗完毕，清除 Branch 自身的值
            else:
                nibble = key[0]  // 取当前待匹配的 nibble
                node.children[nibble], deleted = delete(node.children[nibble], key[1:])  // 递归删除，消耗 1 个 nibble
                if !deleted:
                    return node, false  // 子树删除失败，整体不变

            // 删除成功，检查删除后是否满足合并条件
            pos = -1
            for i from 0 to 15:  // 遍历 16 个子节点槽位
                if node.children[i] is not nil:
                    if pos == -1:
                        pos = i  // 记录第一个非空槽位的位置
                    else:
                        pos = -2  // 发现第二个非空槽位，不需要合并
                        break

            if pos == -1:
                return nil, true  // 所有子节点槽位为空且自身无值，移除整个 Branch
            if pos >= 0 and node.value is nil:
                // 只有一个子节点且自身无值，满足合并条件
                child = node.children[pos]
                if child is Leaf:
                    return Leaf([pos] + child.encodedPath, child.value), true  // Branch 的分叉 nibble + Leaf 路径合并为新 Leaf
                if child is Extension:
                    return Extension([pos] + child.encodedPath, child.next), true  // Branch 的分叉 nibble + Extension 前缀合并为新 Extension
                // child is Branch: 无法直接合并，用 Extension 包装分叉 nibble
                return Extension([pos], child), true

            return node, true  // 不满足合并条件，保持原结构

原结构：

Extension -> [a,3,f, next]
                      |
                   [7, 9; nil] <- Branch
                    /   \
                 [b; A] [d; B] <- Leaf

    ↓ 删除 0xa3f9d → B

Extension -> [a,3,f, next]
                  |
                [7; nil] <- Branch（只剩一个子节点，自身无值）
                /
              [b; A] <- Leaf

    ↓ Branch 只有一个子节点且自身无值，合并为 Leaf

[a,3,f,7,b; A] <- Leaf