AVL树，以下说法是否正确？大O
AVL tree, Is the following claim true? BIG O
我看到了以下声明：
令T为AVL树，TL为根的左子树中的节点数，而TR为根的右子树中的节点数。然后： TL = Big Theta (TR) 这两个意思是： TL = O(TR) 和 TL = Big Omega (TR)
起初我虽然很简单是真的但是如果左儿子有0个节点而右儿子有1个节点怎么办？这仍然是一个合法的 avl 树，与声明相矛盾。
有人可以确认并看看我在这里做错了什么吗？
该说法是错误的，但这不是有效的证据。 1 确实不是 O(0)；然而，这个事实是不相关的，因为定义所讨论序列的习惯方法是让 TL(n) 是根节点左侧的最大（对于 big-O）或最小（对于 big-Omega）节点数给定右子树有 n 个节点的子树。由于 AVL 平衡 属性，一棵有效的 AVL 树不可能有一个空的左子树和一个以上的节点，所以这个退化的例子不是我们需要推理的无限族渐近行为。
f(n) = O(g(n)) 的量词结构是存在 n0 和 c 使得对于所有 n ≥ n0，我们有 f(n) ≤ c g(n)。当我们否定这个陈述时，量词翻转，所以对于所有 n0和c，存在n≥n0 使得 f(n) > c g(n)。如果我们取 n0 大，那么它排除了你的例子。
AVL 树的良构要求是每个子树都是±1 高度平衡的。在最极端的情况下，左子树的高度为 k+1，而右子树的节点最少，高度为 k。我们得到递归数TL(k)，高度为k，
的完整子树中的节点数
TL(0) = 1
TL(k+1) = 2 TL(k) + 1,
求解 TL(k) = 2^(k+1) - 1 和 TR(k)，高度为 k，
的最小 AVL 树中的节点数
TR(0) = 1
TR(1) = 2
TR(k+1) = TR(k) + TR(k-1) + 1,
求解为 TL(k) = Fib(k+1) - 1，即 O(1.7^k)，因此不是 Omega(2^k)。
声明不正确。为了反驳这个说法，你的反例确实足够了，因为 1 is not O(0):
不能有任何（常数）c
1 <= c * 0.
请注意，要证明这一说法，必须同时确保两者
TL = O(TR) and TR = O(TL)
不管 TL 和 TR 是什么（只要它们是有效 AVL 树中的可能数字）。
当前接受的答案具有误导性。请注意，要证明该声明是错误的，不需要证据。
请注意，原始问题中的声明并未说明等式适用于 足够大 有效的 TL 和 TR。相反，它指出等式适用于 any 有效的 TL 和 TR。这就是问题的作者 MrCalc 寻求对他的反例进行确认的原因。这是我的确认：
MrCalc's counterexample TL=0 and TR=1 indeed disproves the claim.
我不同意当前接受的答案中关于不等式 1 is not O(0) 无关紧要的说法。
相反，这是原问题中提出的一个关键点，不等式确实反驳了这一说法。
我看到了以下声明：
令T为AVL树，TL为根的左子树中的节点数，而TR为根的右子树中的节点数。然后： TL = Big Theta (TR) 这两个意思是： TL = O(TR) 和 TL = Big Omega (TR)
起初我虽然很简单是真的但是如果左儿子有0个节点而右儿子有1个节点怎么办？这仍然是一个合法的 avl 树，与声明相矛盾。
有人可以确认并看看我在这里做错了什么吗？
该说法是错误的，但这不是有效的证据。 1 确实不是 O(0)；然而，这个事实是不相关的，因为定义所讨论序列的习惯方法是让 TL(n) 是根节点左侧的最大（对于 big-O）或最小（对于 big-Omega）节点数给定右子树有 n 个节点的子树。由于 AVL 平衡 属性，一棵有效的 AVL 树不可能有一个空的左子树和一个以上的节点，所以这个退化的例子不是我们需要推理的无限族渐近行为。
f(n) = O(g(n)) 的量词结构是存在 n0 和 c 使得对于所有 n ≥ n0，我们有 f(n) ≤ c g(n)。当我们否定这个陈述时，量词翻转，所以对于所有 n0和c，存在n≥n0 使得 f(n) > c g(n)。如果我们取 n0 大，那么它排除了你的例子。
AVL 树的良构要求是每个子树都是±1 高度平衡的。在最极端的情况下，左子树的高度为 k+1，而右子树的节点最少，高度为 k。我们得到递归数TL(k)，高度为k，
TL(0) = 1
TL(k+1) = 2 TL(k) + 1,
求解 TL(k) = 2^(k+1) - 1 和 TR(k)，高度为 k，
TR(0) = 1
TR(1) = 2
TR(k+1) = TR(k) + TR(k-1) + 1,
求解为 TL(k) = Fib(k+1) - 1，即 O(1.7^k)，因此不是 Omega(2^k)。
声明不正确。为了反驳这个说法，你的反例确实足够了，因为 1 is not O(0):
1 <= c * 0.
请注意，要证明这一说法，必须同时确保两者
TL = O(TR) and TR = O(TL)
不管 TL 和 TR 是什么（只要它们是有效 AVL 树中的可能数字）。
当前接受的答案具有误导性。请注意，要证明该声明是错误的，不需要证据。
请注意，原始问题中的声明并未说明等式适用于 足够大 有效的 TL 和 TR。相反，它指出等式适用于 any 有效的 TL 和 TR。这就是问题的作者 MrCalc 寻求对他的反例进行确认的原因。这是我的确认：
MrCalc's counterexample TL=0 and TR=1 indeed disproves the claim.
我不同意当前接受的答案中关于不等式 1 is not O(0) 无关紧要的说法。
相反，这是原问题中提出的一个关键点，不等式确实反驳了这一说法。