存树

结点结构:

  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的前驱可能存在于右子树中,或者等于根节点。

      注意:若是当前根节点比已有的前驱大,则需更新已有的前驱值。

    对于上面的三种子情况,若左子树/右子树为空,只需输出当前已有的前驱值即可。

查找后驱

同查找前驱,不再赘述。

最后修改:2022 年 03 月 26 日 02 : 32 PM
如果觉得这篇文章对你有用,请随意赞赏~