Loading... ## 存树 结点结构： 1. 左子节点 2. 右子节点 3. 以当前节点为根的子树大小（含权重） 4. 当前节点权重（节点值出现的次数） 5. 节点值 ## 插入节点 局部问题：已知“树组”的总节点数，在当前子树中插入`x` - Case 1 - 当前为空根（即，树组为空，或是已经位于叶子节点的空儿子处） 若当前根为空，则在“树组”的末尾开一个节点作为树的根（注意特例：若是整个树组均为空，则说明没有大根，需要在`1位置`新建所需的树）（`0位置`留给空节点标记用）。 新节点的参数：左子为0（空节点），右子为0，值为`x`，子树大小为1，权重为1。 - Case 2 - 当前子树非空（有根） - 2.1 - 若根等于`x` 只需将根的权重加一即可，完成任务。 - 2.2 - 若根大于`x` 说明要在左子树中插入`x`。 将当前的根设为左子树根（允许为空），继续下一次判断。 - 2.3 - 若根小于`x` 说明要在右子树中插入`x`。 将当前的根设为右子树根（允许为空），继续下一次判断。 在新建节点后，还需要将父节点指向新建的节点（若是新建节点存在叶子节点的话）。 因此在上面每一步挪动根节点时，都需要保留其父节点的记录。 判断新建立的叶子节点位于左子还是右子，只需将其值与父节点值进行比较即可。 ## 查询排名 对于给定的子树根节点，查询值`x`在该子树中的排名等价于查询该子树中比`x`小的节点数量。 局部问题：查询局部子树中比`x`小的结点数量（含权） - Case 1 - 子树为空树（无节点） 若子树为空树，此时在该子树中比`x`小的节点数量为0。 - Case 2 - 子树非空 - 2.1 - 子树根节点值等于`x` 此时比`x`小的结点即为整个左子树，因此局部问题的解为左子树大小（含权） - 2.2 - 子树根节点值大于`x` 此时所有“可能小于`x`”的值都仅可能存在于左子树中， 因此只需在左子树中寻找小于`x`的节点数量即可， 局部问题的解为递归“在左子树中查询小于`x`的节点数量”。 - 2.3 - 子树根节点值小于`x` 此时左子树以及根节点的值均需要记在结果中， 且右子树中仍可能存在比`x`小的结点。 因此局部问题的解为：左子树大小（含权）+根节点大小（含权）+右子树中小于`x`的节点数量。 需要注意的是，此时局部问题获得的值为“小于`x`的结点数量”，按照题目要求需要加1才能够获得`x`的排名。 ## 按照排名查数 局部问题：在子树中查找排名为`x`的数 - Case 1 - 子树为空树（无节点） 若子树为空树，此时排名为`x`的数自然不存在，可以返回INF等无效值。 - Case 2 - 子树非空 - 2.1 - `x`>左子树大小 且 `x`<左子树大小+根节点权重 此时说明要找的第`x`个数就是根节点的值。 局部问题解：根节点值 - 2.2 - `x`<=左子树大小 说明第`x`个数在左子树中，直接去左子树中找即可。 局部问题解：在左子树中查找排名为`x`的数。 - 2.3 - `x`>左子树大小+根节点权重 此时第`x`个数在右子树中，在右子数中的排名为`x`-左子树大小-根权重。 局部问题解：在右子树中查找排名为`x-l.size-root.count`的数。 ## 查找前驱 题目已经给出了提示：“若未找到则输出`-2147483647`” 说明可以将当前找到的“最大前驱”作为局部状态进行传递。 局部问题：已知当前子树外部的最大的`x`的前驱，在当前子树中查找并更新`x`的前驱。 - Case 1 - 当前子树为空树（无节点） 由于已有子树外部的前驱，因此只需要将其输出即可。 - Case 2 - 当前子树非空 - 2.1 - 当前子树根节点值等于`x` 说明`x`的前驱可能存在于左子树中。 - 2.2 - 当前子树根节点值大于`x` 说明`x`的前驱可能存在于左子树中。 - 2.3 - 当前子树根节点值小于`x` 说明`x`的前驱可能存在于右子树中，或者等于根节点。 <u>注意：若是当前根节点比已有的前驱大，则需更新已有的前驱值。</u> 对于上面的三种子情况，若左子树/右子树为空，只需输出当前已有的前驱值即可。 ## 查找后驱 同查找前驱，不再赘述。 最后修改：2022 年 03 月 26 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得这篇文章对你有用，请随意赞赏~
