存树
结点结构:
- 左子节点
- 右子节点
- 以当前节点为根的子树大小(含权重)
- 当前节点权重(节点值出现的次数)
- 节点值
插入节点
局部问题:已知“树组”的总节点数,在当前子树中插入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
的前驱可能存在于右子树中,或者等于根节点。注意:若是当前根节点比已有的前驱大,则需更新已有的前驱值。
对于上面的三种子情况,若左子树/右子树为空,只需输出当前已有的前驱值即可。
-
查找后驱
同查找前驱,不再赘述。