prices map 是什么：撮合、红黑和 O(log 档数)

上一篇说红黑树只管价档。接着会撞上几个词：prices map、最值、后继、红或黑、O(log 档数)。它们对着同一件事：价格档位怎么找、怎么从上往下吃。

用一个具体盘口串起来。假设卖盘现在有三档：

价格 100：卖 3 手
价格 101：卖 5 手
价格 103：卖 2 手

---

prices map 是什么

就是「价格 → 这一档的队列」的字典，查已知价格用。

prices["100"] → 100 那一档的 OrderQueue
prices["101"] → 101 那一档
prices["103"] → 103 那一档

有人再挂一笔「101 卖 1 手」：用 "101" 直接拿到那一档，把单接到队尾。不用树。
档空了：delete(prices, "101")，同时从树上删掉 101。

map 不知道谁最便宜。键是打乱的，不能问「最小的价格是谁」。这件事交给树。

---

撮合时在干什么（用买单举例）

市价买入 6 手：不管价格，先吃最便宜的卖单。

1. Best() = MinPriceQueue() → 先拿到 100 这一档，吃掉 3 手，还剩 3 手。
2. 100 空了。Next(100) = GreaterThan(100) → 比 100 大一点点的下一档，也就是 101。
3. 在 101 再吃 3 手。101 还剩 2 手。买够了，停。

卖单反过来：先吃买盘最高价（MaxPriceQueue），吃完一档再找「比它低一点点」的下一档（LessThan）。

所以撮合就是两步反复做：

• 最值：当前最好的一档（卖盘最低价 / 买盘最高价）
• 后继：这一档吃完后，按价格顺序的下一档

---

「最值」「后继」是什么意思

• 最值：一组数里的最小或最大。卖盘最值 = 最低卖价 100；买盘最值 = 最高买价。
• 后继：排序后紧挨着的下一个。100 的后继是 101，101 的后继是 103（没有 102 这一档）。

O(log 档数) 里的「档数」是不同价格有几个，不是订单有几笔。上面只有 3 档，不是 10 笔订单。

---

为什么是 O(log 档数)，为什么还提「左 < 自己 < 右」

树按价格排好，每个节点左边更小、右边更大：

    101
   /   \
100     103

• 找最小：一直往左走 → 100。不用看完全部档。
• 找最大：一直往右走 → 103。
• 找 100 的后继：从根出发比较，「比 100 大的最近一个」→ 101。

每走一步，大概丢掉一半节点，所以步数大约是 log2(档数)。
100 档大约比 7 次；100 万档大约比 20 次。这就是 O(log 档数)。

如果没有「左小右大」，就只能把档位扫一遍，那是 O(档数)。提到这条规则，只是为了说明：最值和后继能走这么快，全靠树是按价格排好的。

---

红或黑是什么意思

每个节点多涂一种颜色，红或黑，只给树自己做平衡用。

价格如果按 100、101、102、103 依次挂上去，普通二叉搜索树会歪成一条链，找最小也要从头走到尾。红黑规则会在插入时旋转、改色，让树不要太歪，高度一直接近 log 档数。

对读订单簿来说：红/黑不是买卖方向，也不是价格高低。只要知道树上能 GetMin / GetMax / 找下一档，并且不会退化成慢扫描。具体怎么涂色、怎么旋转，可以先不看。

---

对照：prices 回答「101 这一档在哪」；树回答「最好的一档是谁、下一档是谁」。撮合只用后两个问题。