content_views"
c lass="markdown_views prism-atom-one-light">
cap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-bloc k" style="-webkit-tap-highlight-c olor: rgba(0, 0, 0, 0);">
在上周的文章中c ;我们了解了二叉搜索树 这一强大的数据结构 ：
数据结构 与c lass="tags" href="/tags/SuanFa.html" title=算法>算法-二叉搜索树的定义和插入实现
上次c ;我们已经实现了插入节点的功能
要想具体应用到c lass="tags" href="/tags/SuanFa.html" title=算法>算法的整体设计中c ;我们还需要根据运用场景进行改动
让我们先从一个经典的问题开始
[题目传送门]here
有一个初始为空的数列
现在总共有class="katex--inline">class="katex">class="katex-mathml">
T
T
class="katex-html">class="base">class="strut" style="height: 0.6833em;"> class="mord mathnormal" style="margin-right: 0.1389em;">T 个操作c ;每个都是以下两种之一：
class="katex--inline">class="katex">class="katex-mathml">
1
k
1\ \ k
class="katex-html">class="base">class="strut" style="height: 0.6944em;"> class="mord">1 class="mspac e"> class="mspac e"> class="mord mathnormal" style="margin-right: 0.0315em;">k ：向数列中添加一个数class="katex--inline">class="katex">class="katex-mathml">
k
k
class="katex-html">class="base">class="strut" style="height: 0.6944em;"> class="mord mathnormal" style="margin-right: 0.0315em;">k class="katex--inline">class="katex">class="katex-mathml">
2
k
2\ \ k
class="katex-html">class="base">class="strut" style="height: 0.6944em;"> class="mord">2 class="mspac e"> class="mspac e"> class="mord mathnormal" style="margin-right: 0.0315em;">k ：查询第class="katex--inline">class="katex">class="katex-mathml">
k
k
class="katex-html">class="base">class="strut" style="height: 0.6944em;"> class="mord mathnormal" style="margin-right: 0.0315em;">k 小的数
（时间限制1000ms）
首先我们想到的暴力做法就是每次数据进来之后就排序
但是很明显c ;数据规模在class="katex--inline">class="katex">class="katex-mathml">
1
0
5
10^5
class="katex-html">class="base">class="strut" style="height: 0.8141em;"> class="mord">1 class="mord">class="mord">0 class="msupsub">class="vlist-t">class="vlist-r">class="vlist" style="height: 0.8141em;">class="" style="top: -3.063em; margin-right: 0.05em;">class="pstrut" style="height: 2.7em;"> class="sizing reset-size6 size3 mtight">class="mord mtight">5 量级c ;
题目要求的时间复杂度显然是在class="katex--inline">class="katex">class="katex-mathml">
O
(
n
l
o
g
n
)
O(nlogn)
class="katex-html">class="base">class="strut" style="height: 1em; vertic al-align: -0.25em;"> class="mord mathnormal" style="margin-right: 0.0278em;">O class="mopen">( class="mord mathnormal">n class="mord mathnormal" style="margin-right: 0.0197em;">l class="mord mathnormal">o class="mord mathnormal" style="margin-right: 0.0359em;">g class="mord mathnormal">n class="mc lose">) 左右
如果直接使用sort肯定会超时
假设询问次数为class="katex--inline">class="katex">class="katex-mathml">
n
n
class="katex-html">class="base">class="strut" style="height: 0.4306em;"> class="mord mathnormal">n c ;什么数据结构 能以class="katex--inline">class="katex">class="katex-mathml">
l
o
g
n
logn
class="katex-html">class="base">class="strut" style="height: 0.8889em; vertic al-align: -0.1944em;"> class="mord mathnormal" style="margin-right: 0.0197em;">l class="mord mathnormal">o class="mord mathnormal" style="margin-right: 0.0359em;">g class="mord mathnormal">n 的复杂度完成查询呢
我们想到了二叉搜索树
假如现在有这么一棵二叉搜索树（数字为对应节点的权值）：c sdnimg.c n/direc t/9c dad0495c 04442883a3aac e04c d6a47.png" alt="在这里插入图片描述" />c ;怎么办？
这时候就需要引入一个新的参数来表示每个节点子树的大小了
至于为何c ;往下看便是
我们的插入部分代码成了这样：
<c ode c lass="prism language-c pp">class="token keyword">struc t class="token c lass-name">Node class="token punc tuation">{
class="token keyword">int keyclass="token punc tuation">, lclass="token punc tuation">, rclass="token punc tuation">, szclass="token punc tuation">, c ntclass="token punc tuation">;
class="token punc tuation">} trclass="token punc tuation">[ MaxNclass="token punc tuation">] class="token punc tuation">;
class="token keyword">void class="token func tion">ins class="token punc tuation">( class="token keyword">int class="token operator">& posclass="token punc tuation">, class="token keyword">int xclass="token punc tuation">) class="token punc tuation">{
class="token keyword">if class="token punc tuation">( pos class="token operator">== class="token number">0 class="token punc tuation">) class="token punc tuation">{
pos class="token operator">= class="token operator">++ nclass="token punc tuation">;
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. key class="token operator">= xclass="token punc tuation">;
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. sz class="token operator">= trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. c nt class="token operator">= class="token number">1 class="token punc tuation">;
class="token keyword">return class="token punc tuation">;
class="token punc tuation">}
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. szclass="token operator">++ class="token punc tuation">;
class="token keyword">if class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. key class="token operator">== xclass="token punc tuation">) class="token punc tuation">{
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. c ntclass="token operator">++ class="token punc tuation">;
class="token keyword">return class="token punc tuation">;
class="token punc tuation">}
class="token keyword">if class="token punc tuation">( x class="token operator">< trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. keyclass="token punc tuation">) class="token func tion">ins class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. lclass="token punc tuation">, xclass="token punc tuation">) class="token punc tuation">;
class="token keyword">else class="token func tion">ins class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. rclass="token punc tuation">, xclass="token punc tuation">) class="token punc tuation">;
class="token punc tuation">}
code>
首先我们以人类的思维思考一种简单的情况：
c nt1_71">c nt全为1我们模拟一下过程如下图：
c sdnimg.c n/direc t/0125efd455724a3586f7e1b76b5c 5867.png" alt="在这里插入图片描述" />
我们要查找的是第三小的数c ;发现左子树 有多于3个节点
又因为左子树上的数一定小于根节点
所以目标必然是左子树上第三小的数c ;往左找！
接下来c ;发现新的节点左边只有一个节点
即便是加上它自己也不可能有第三小
所以就往右找！
但是一定要注意c ;在右子树找的时候找的并不是第三小的数
而是要除去左子树和根节点的所有数 c ;因为它们都比第三小的数更小！
依次一直递归c ;直到在大小为1的子树中找第1小的数c ;我们就找到了答案！
同理c ;c nt不全为1是时也可以用上面的思路
一般地c ;对于节点class="katex--inline">class="katex">class="katex-mathml">
n
n
class="katex-html">class="base">class="strut" style="height: 0.4306em;"> class="mord mathnormal">n c ;需要分几种情况讨论：
若class="katex--inline">class="katex">class="katex-mathml">
t
r
[
n
.
l
]
.
s
z
≤
k
tr[n.l].sz \leq k
class="katex-html">class="base">class="strut" style="height: 1em; vertic al-align: -0.25em;"> class="mord mathnormal">t class="mord mathnormal" style="margin-right: 0.0278em;">r class="mopen">[ class="mord mathnormal">n class="mord">. class="mord mathnormal" style="margin-right: 0.0197em;">l class="mc lose">] class="mord">. class="mord mathnormal" style="margin-right: 0.044em;">sz class="mspac e" style="margin-right: 0.2778em;"> class="mrel">≤ class="mspac e" style="margin-right: 0.2778em;"> class="base">class="strut" style="height: 0.6944em;"> class="mord mathnormal" style="margin-right: 0.0315em;">k ：目标在左子树c ;往左找
否则若class="katex--inline">class="katex">class="katex-mathml">
t
r
[
n
.
l
]
.
s
z
+
n
.
c
n
t
tr[n.l].sz + n.c nt
class="katex-html">class="base">class="strut" style="height: 1em; vertic al-align: -0.25em;"> class="mord mathnormal">t class="mord mathnormal" style="margin-right: 0.0278em;">r class="mopen">[ class="mord mathnormal">n class="mord">. class="mord mathnormal" style="margin-right: 0.0197em;">l class="mc lose">] class="mord">. class="mord mathnormal" style="margin-right: 0.044em;">sz class="mspac e" style="margin-right: 0.2222em;"> class="mbin">+ class="mspac e" style="margin-right: 0.2222em;"> class="base">class="strut" style="height: 0.6151em;"> class="mord mathnormal">n class="mord">. class="mord mathnormal">c class="mord mathnormal">n class="mord mathnormal">t ：要找的数就是根节点
否则目标在右子树c ;往右找
到这里c ;正解就呼之欲出了——
<c ode c lass="prism language-c pp">class="token mac ro property">class="token direc tive-hash"># class="token direc tive keyword">inc lude class="token string"><iostream>
class="token keyword">using class="token keyword">namespac e stdclass="token punc tuation">;
class="token mac ro property">class="token direc tive-hash"># class="token direc tive keyword">define class="token mac ro-name">MaxN class="token expression">class="token number">100005
class="token mac ro property">class="token direc tive-hash"># class="token direc tive keyword">define class="token mac ro-name func tion">For class="token expression">class="token punc tuation">( iclass="token punc tuation">, jclass="token punc tuation">, kclass="token punc tuation">) class="token keyword">for class="token punc tuation">( class="token keyword">int i class="token operator">= jclass="token punc tuation">; i class="token operator"><= kclass="token punc tuation">; iclass="token operator">++ class="token punc tuation">)
class="token keyword">int nclass="token punc tuation">, qclass="token punc tuation">, rtclass="token punc tuation">;
class="token keyword">struc t class="token c lass-name">Node class="token punc tuation">{
class="token keyword">int keyclass="token punc tuation">, lclass="token punc tuation">, rclass="token punc tuation">, szclass="token punc tuation">, c ntclass="token punc tuation">;
class="token punc tuation">} trclass="token punc tuation">[ MaxNclass="token punc tuation">] class="token punc tuation">;
class="token keyword">void class="token func tion">ins class="token punc tuation">( class="token keyword">int class="token operator">& posclass="token punc tuation">, class="token keyword">int xclass="token punc tuation">) class="token punc tuation">{ class="token c omment">//插入节点x
class="token keyword">if class="token punc tuation">( pos class="token operator">== class="token number">0 class="token punc tuation">) class="token punc tuation">{
pos class="token operator">= class="token operator">++ nclass="token punc tuation">;
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. key class="token operator">= xclass="token punc tuation">;
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. sz class="token operator">= trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. c nt class="token operator">= class="token number">1 class="token punc tuation">;
class="token keyword">return class="token punc tuation">;
class="token punc tuation">}
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. szclass="token operator">++ class="token punc tuation">;
class="token keyword">if class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. key class="token operator">== xclass="token punc tuation">) class="token punc tuation">{
trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. c ntclass="token operator">++ class="token punc tuation">;
class="token keyword">return class="token punc tuation">;
class="token punc tuation">}
class="token keyword">if class="token punc tuation">( x class="token operator">< trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. keyclass="token punc tuation">) class="token func tion">ins class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. lclass="token punc tuation">, xclass="token punc tuation">) class="token punc tuation">;
class="token keyword">else class="token func tion">ins class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. rclass="token punc tuation">, xclass="token punc tuation">) class="token punc tuation">;
class="token punc tuation">}
class="token keyword">int class="token func tion">query class="token punc tuation">( class="token keyword">int posclass="token punc tuation">, class="token keyword">int kclass="token punc tuation">) class="token punc tuation">{ class="token c omment">//在根节点编号pos处找第k小的数
class="token keyword">if class="token punc tuation">( trclass="token punc tuation">[ trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. lclass="token punc tuation">] class="token punc tuation">. sz class="token operator">>= kclass="token punc tuation">) class="token punc tuation">{ class="token c omment">//分类
class="token keyword">return class="token func tion">query class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. lclass="token punc tuation">, kclass="token punc tuation">) class="token punc tuation">; class="token c omment">//左子树
class="token punc tuation">} class="token keyword">else class="token keyword">if class="token punc tuation">( trclass="token punc tuation">[ trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. lclass="token punc tuation">] class="token punc tuation">. sz class="token operator">+ trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. c nt class="token operator">>= kclass="token punc tuation">) class="token punc tuation">{
class="token keyword">return trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. keyclass="token punc tuation">; class="token c omment">//根节点
class="token punc tuation">} class="token keyword">else class="token punc tuation">{ class="token c omment">//右子树
class="token keyword">return class="token func tion">query class="token punc tuation">( trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. rclass="token punc tuation">, kclass="token operator">- trclass="token punc tuation">[ trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. lclass="token punc tuation">] class="token punc tuation">. szclass="token operator">- trclass="token punc tuation">[ posclass="token punc tuation">] class="token punc tuation">. c ntclass="token punc tuation">) class="token punc tuation">;
class="token punc tuation">}
class="token punc tuation">}
class="token keyword">int class="token func tion">main class="token punc tuation">( class="token punc tuation">)
class="token punc tuation">{
c in class="token operator">>> qclass="token punc tuation">;
class="token keyword">while class="token punc tuation">( qclass="token operator">-- class="token punc tuation">) class="token punc tuation">{
class="token keyword">int opclass="token punc tuation">, xclass="token punc tuation">;
c in class="token operator">>> op class="token operator">>> xclass="token punc tuation">;
class="token keyword">if class="token punc tuation">( op class="token operator">== class="token number">1 class="token punc tuation">) class="token punc tuation">{
class="token func tion">ins class="token punc tuation">( rtclass="token punc tuation">, xclass="token punc tuation">) class="token punc tuation">;
class="token punc tuation">} class="token keyword">else class="token punc tuation">{
class="token keyword">if class="token punc tuation">( x class="token operator">> trclass="token punc tuation">[ class="token number">1 class="token punc tuation">] class="token punc tuation">. szclass="token punc tuation">) c out class="token operator"><< class="token operator">- class="token number">1 class="token operator"><< endlclass="token punc tuation">;
class="token keyword">else c out class="token operator"><< class="token func tion">query class="token punc tuation">( class="token number">1 class="token punc tuation">, xclass="token punc tuation">) class="token operator"><< endlclass="token punc tuation">;
class="token punc tuation">}
class="token punc tuation">}
class="token keyword">return class="token number">0 class="token punc tuation">;
class="token punc tuation">}
code>
在这篇文章中c ;我们通过经典的第k小问题 了解了二叉搜索树的运用
实际上c ;它还有更加丰富的拓展和运用c ;比如treap, AVLtree 等
更多内容敬请期待下期数据结构 与c lass="tags" href="/tags/SuanFa.html" title=算法>算法！
最后c ;制作实在不易。如果你喜欢这篇文章c ;可以点个免费的关注 和免费的赞
非常感谢大家的支持c ;你的支持是作者最大的动力！
我们下期再见！
