From 62895f70e1dbcfc9f5e03db0f1d9bac55fdcbc91 Mon Sep 17 00:00:00 2001 From: ouuan Date: Sat, 13 Jul 2019 21:52:13 +0800 Subject: [PATCH] fix: delete double mathrm --- docs/ds/leftist-tree.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/ds/leftist-tree.md b/docs/ds/leftist-tree.md index 8889ad5e..24a62684 100644 --- a/docs/ds/leftist-tree.md +++ b/docs/ds/leftist-tree.md @@ -107,7 +107,7 @@ void pushup(int x) 1. $x$ 是 $y$ 的右儿子,此时 $y$ 的初始 $\mathrm{dist}$ 为 $x$ 的初始 $\mathrm{dist}$ 加一。 2. $x$ 是 $y$ 的左儿子,只有 $y$ 的左右儿子初始 $\mathrm{dist}$ 相等时(此时左儿子 $\mathrm{dist}$ 减一会导致左右儿子互换)才会继续递归下去,因此 $y$ 的初始 $\mathrm{dist}$ 仍然是 $x$ 的初始 $\mathrm{dist}$ 加一。 -所以,我们得到,除了第一次 `pushup`(因为被删除节点的父亲的初始 $\mathrm{dist}$ 不一定等于被删除节点左右儿子合并后的初始 $\mathrm{dist}$ 加一),每递归一层 $x$ 的初始 $\mathrm{$\mathrm{dist}$}$ 就会加一,因此最多递归 $\mathcal O(\log n)$ 层。 +所以,我们得到,除了第一次 `pushup`(因为被删除节点的父亲的初始 $\mathrm{dist}$ 不一定等于被删除节点左右儿子合并后的初始 $\mathrm{dist}$ 加一),每递归一层 $x$ 的初始 $\mathrm{dist}$ 就会加一,因此最多递归 $\mathcal O(\log n)$ 层。 ### 整个堆加上 / 减去一个值、乘上一个正数 -- 2.11.0