P5076 二叉搜索树（未优化）

博主：枫亚
发布时间：2022 年 03 月 26 日
1232 次浏览
暂无评论
1280字数
分类：

## 存树

结点结构：

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 日

如果觉得这篇文章对你有用，请随意赞赏~

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

ssf
看不到内容啊。
潜龙于渊
完美解决问题！感谢大佬！
123
感谢，配置成功
WetABQ
啊这（那可能，可能... 可能不是吧我是因为 Gyrojeff...
WetABQ
ADHD 大概率下是被迫的，几乎任何情况下都无法集中精力「对于...

在腾讯云Lighthouse中安装Typecho全过程
评论数： 0
OI-20210902
评论数： 0
学习方法探索 - 1
评论数： 0
跑步入门知识整理
评论数： 0
CSAPP-20210905
评论数： 0

P5076 二叉搜索树（未优化）

枫亚 • 2022 年 03 月 26 日

## 存树

结点结构：

1. 左子节点
2. 右子节点
3. 以当前节点为根的子树大小（含权重）
4. 当前节点权重（节点值出现的次数）
5. 节点值

## 插入节点

局部问题：已知“树组”的总节点数，在当前子树中插入`x`

- Case 1 - 当前为空根（即，树组为空，或是已经位于叶子节点的空儿子处）

新节点的参数：左子为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>

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

## 查找后驱

同查找前驱，不再赘述。

P5076 二叉搜索树（未优化）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Ubuntu环境下iBus-Rime小鹤双拼音形方案配置记录

死要面子活受罪

对学习焦虑的思考

茶铺开张啦

学习方法探索 - 1

在腾讯云Lighthouse中安装Typecho全过程

OI-20210902

学习方法探索 - 1

跑步入门知识整理

CSAPP-20210905

P5076 二叉搜索树（未优化）

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

P5076 二叉搜索树（未优化）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款