Otdfbt

Multi tool use

Is "Busen" just the area between the breasts?

Why does Linux list NVMe drives as /dev/nvme0 instead of /dev/sda?

Can humans ever directly see a few photons at a time? Can a human see a single photon?

Has there been any indication at all that further negotiation between the UK and EU is possible?

Do I need a shock-proof watch for cycling?

Trainee keeps passing deadlines for independent learning

Does a vocal melody have any rhythmic responsibility to the underlying arrangement in pop music?

Does the monk's Step of the Wind feature activate the benefit of the Mobile feat?

Do I have to explain the mechanical superiority of the player-character within the fiction of the game?

Shooting someone's past self using special relativity

"Correct me if I'm wrong"

Understanding the reasoning of the woman who agreed with Shlomo to "cut the baby in half"

Why isn't my calculation that we should be able to see the sun well beyond the observable universe valid?

How would modern naval warfare have to have developed differently for battleships to still be relevant in the 21st century?

What is "industrial ethernet"?

Can White Castle?

Should I include an appendix for inessential, yet related worldbuilding to my story?

Prime sieve in Python

UK - Working without a contract. I resign and guy wants to sue me

Dates on degrees don’t make sense – will people care?

Cut the gold chain

What is appropriate short form for "laboratoires" in French?

Loss of power when I remove item from the outlet

Story about hunting giant lizards for hides on privately owned planet

Do height-balanced binary trees have logarithmic depth?

Not all Red-Black trees are balanced?Two definitions of balanced binary treesFor AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient?AVL Trees Height-Balance PropertyExample of height-balanced tree that is not weight-balancedIs there an O(logN) optimal weight balanced binary search tree where weights/sizes of left and right subtree differ at most by 1?Balanced Binary TreeNumber of possible balanced binary treesBVL Balanced TreeThe number of balanced trees with N node and L leaves

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

2

$begingroup$

A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( log n)$.

Given a family of trees such that for every tree $t$ in the family, for every node $v$ in $t$, the height difference between the right subtree of $v$ and the left subtree of $v$ is at most $c$, where $c$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.

data-structures binary-trees

share|cite|improve this question

edited Jun 4 at 13:28

Yuval Filmus

202k15197359

asked Jun 4 at 11:23

Neo182Neo182

113

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What is the claim you're trying to prove? Do you want to show that such a family is height balanced?
  $endgroup$
  – Steven
  Jun 4 at 13:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes Steven. Exactly. We need to prove that this family is height balanced.
  $endgroup$
  – Neo182
  Jun 4 at 13:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is this an infinite family? Big-O notation applies to asymptotic behavior, which doesn't apply to finite cases.
  $endgroup$
  – Acccumulation
  Jun 4 at 21:40
  

  
  
  
  

add a comment | 

2

$begingroup$

A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( log n)$.

Given a family of trees such that for every tree $t$ in the family, for every node $v$ in $t$, the height difference between the right subtree of $v$ and the left subtree of $v$ is at most $c$, where $c$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.

data-structures binary-trees

share|cite|improve this question

edited Jun 4 at 13:28

Yuval Filmus

202k15197359

asked Jun 4 at 11:23

Neo182Neo182

113

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What is the claim you're trying to prove? Do you want to show that such a family is height balanced?
  $endgroup$
  – Steven
  Jun 4 at 13:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes Steven. Exactly. We need to prove that this family is height balanced.
  $endgroup$
  – Neo182
  Jun 4 at 13:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is this an infinite family? Big-O notation applies to asymptotic behavior, which doesn't apply to finite cases.
  $endgroup$
  – Acccumulation
  Jun 4 at 21:40
  

  
  
  
  

add a comment | 

$begingroup$

A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( log n)$.

Given a family of trees such that for every tree $t$ in the family, for every node $v$ in $t$, the height difference between the right subtree of $v$ and the left subtree of $v$ is at most $c$, where $c$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.

data-structures binary-trees

share|cite|improve this question

edited Jun 4 at 13:28

Yuval Filmus

202k15197359

asked Jun 4 at 11:23

Neo182Neo182

113

$endgroup$

share|cite|improve this question

edited Jun 4 at 13:28

Yuval Filmus

202k15197359

asked Jun 4 at 11:23

Neo182Neo182

113

share|cite|improve this question

edited Jun 4 at 13:28

Yuval Filmus

202k15197359

asked Jun 4 at 11:23

Neo182Neo182

113

edited Jun 4 at 13:28

Yuval Filmus

202k15197359

edited Jun 4 at 13:28

Yuval Filmus

202k15197359

asked Jun 4 at 11:23

Neo182Neo182

113

asked Jun 4 at 11:23

Neo182Neo182

113

3 Answers
3

active

oldest

votes

3

$begingroup$

Let us denote by $N_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N_0 = 1$, and
$$ N_h = N_h-1 + min_0 leq d leq c N_h-1-d. $$
(Here $N_h = 0$ if $h < 0$.) You can prove inductively that $N_h$ is monotone, and so for $h geq c+1$,
$$ N_h = N_h-1 + N_h-1-c. $$
This is a recurrence relation whose solution is $N_h = Theta(alpha^h)$, where $alpha$ is the maximal real root of $x^c+1 - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $Omega(alpha^h)$, it follows that a tree containing $n$ leaves has height $O(log n)$.

share|cite|improve this answer

edited Jun 4 at 16:15

answered Jun 4 at 13:33

Yuval FilmusYuval Filmus

202k15197359

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hey Yuval. Thank you. I have few questions: 1. Why we want to show that Nh is monotone? And to show that I need to prove that Nh+1 >= Nh? 2. How do I reach the expression a^h?
  $endgroup$
  – Neo182
  Jun 4 at 16:06
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  We want to show that $N_h$ is monotone so we could get a simpler recurrence relation for it. We can then solve it using classical techniques to get the answer $Theta(alpha^h)$. See for example Wikipedia.
  $endgroup$
  – Yuval Filmus
  Jun 4 at 16:18
  

  
  
  
  

add a comment | 

1

$begingroup$

Let $T_h$ be any tree that satisfies your property and has height at least $h$. Let $|T_h|$ be the number of its nodes.

For $0 le h le c$, $|T_h| ge 1$.
For $h > c cdot i$, with $i in mathbbN^+$, you have:
$$
|T_h| ge 1 + | T_c cdot i | + | T_ c cdot (i-1)| ge 2 | T'_ c cdot (i-1)|,
$$
where $T_c cdot i$, $T_ c cdot (i-1)$, and $T'_ c cdot (i-1)$ are trees of height at least $c cdot i$, $ c cdot (i-1)$, and $ c cdot (i-1)$, respectively, that also satisfy your property.

Let $T$ be a tree of height $H$ from your family. From the above observations (choosing $h=H$) it follows that $|T| ge 2^leftlfloor fracHc+1 rightrfloor ge 2^fracHc+1 - 1$, or equivalently, $H le (c+1)( 1+ log |T|) = O(log |T|)$.

share|cite|improve this answer

edited Jun 4 at 14:13

answered Jun 4 at 13:52

StevenSteven

42339

$endgroup$

add a comment | 

0

$begingroup$

Thanks everyone for the answers.
Finally I decided to take the proof of AVL tree has a height of O (log n ) and implenent the recurrence with the constant c.
Basically Avl is a special case of this claim so taking the proof of AVL using the same idea led me to the proof.
Instead of N(h) = N (h-1) + N (h-2) + 1
I used
N(h) = N ( h -1) + N ( h - 1 - c) + 1

share|cite|improve this answer

edited Jun 4 at 21:48

Yuval Filmus

202k15197359

answered Jun 4 at 21:45

Neo182Neo182

113

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f110223%2fdo-height-balanced-binary-trees-have-logarithmic-depth%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

Let us denote by $N_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N_0 = 1$, and
$$ N_h = N_h-1 + min_0 leq d leq c N_h-1-d. $$
(Here $N_h = 0$ if $h < 0$.) You can prove inductively that $N_h$ is monotone, and so for $h geq c+1$,
$$ N_h = N_h-1 + N_h-1-c. $$
This is a recurrence relation whose solution is $N_h = Theta(alpha^h)$, where $alpha$ is the maximal real root of $x^c+1 - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $Omega(alpha^h)$, it follows that a tree containing $n$ leaves has height $O(log n)$.

share|cite|improve this answer

edited Jun 4 at 16:15

answered Jun 4 at 13:33

Yuval FilmusYuval Filmus

202k15197359

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hey Yuval. Thank you. I have few questions: 1. Why we want to show that Nh is monotone? And to show that I need to prove that Nh+1 >= Nh? 2. How do I reach the expression a^h?
  $endgroup$
  – Neo182
  Jun 4 at 16:06
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  We want to show that $N_h$ is monotone so we could get a simpler recurrence relation for it. We can then solve it using classical techniques to get the answer $Theta(alpha^h)$. See for example Wikipedia.
  $endgroup$
  – Yuval Filmus
  Jun 4 at 16:18
  

  
  
  
  

add a comment | 

3

$begingroup$

Let us denote by $N_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N_0 = 1$, and
$$ N_h = N_h-1 + min_0 leq d leq c N_h-1-d. $$
(Here $N_h = 0$ if $h < 0$.) You can prove inductively that $N_h$ is monotone, and so for $h geq c+1$,
$$ N_h = N_h-1 + N_h-1-c. $$
This is a recurrence relation whose solution is $N_h = Theta(alpha^h)$, where $alpha$ is the maximal real root of $x^c+1 - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $Omega(alpha^h)$, it follows that a tree containing $n$ leaves has height $O(log n)$.

share|cite|improve this answer

edited Jun 4 at 16:15

answered Jun 4 at 13:33

Yuval FilmusYuval Filmus

202k15197359

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hey Yuval. Thank you. I have few questions: 1. Why we want to show that Nh is monotone? And to show that I need to prove that Nh+1 >= Nh? 2. How do I reach the expression a^h?
  $endgroup$
  – Neo182
  Jun 4 at 16:06
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  We want to show that $N_h$ is monotone so we could get a simpler recurrence relation for it. We can then solve it using classical techniques to get the answer $Theta(alpha^h)$. See for example Wikipedia.
  $endgroup$
  – Yuval Filmus
  Jun 4 at 16:18
  

  
  
  
  

add a comment | 

$begingroup$

Let us denote by $N_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N_0 = 1$, and
$$ N_h = N_h-1 + min_0 leq d leq c N_h-1-d. $$
(Here $N_h = 0$ if $h < 0$.) You can prove inductively that $N_h$ is monotone, and so for $h geq c+1$,
$$ N_h = N_h-1 + N_h-1-c. $$
This is a recurrence relation whose solution is $N_h = Theta(alpha^h)$, where $alpha$ is the maximal real root of $x^c+1 - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $Omega(alpha^h)$, it follows that a tree containing $n$ leaves has height $O(log n)$.

share|cite|improve this answer

edited Jun 4 at 16:15

answered Jun 4 at 13:33

Yuval FilmusYuval Filmus

202k15197359

$endgroup$

share|cite|improve this answer

edited Jun 4 at 16:15

answered Jun 4 at 13:33

Yuval FilmusYuval Filmus

202k15197359

answered Jun 4 at 13:33

Yuval FilmusYuval Filmus

202k15197359

answered Jun 4 at 13:33

Yuval FilmusYuval Filmus

202k15197359

1

$begingroup$

Let $T_h$ be any tree that satisfies your property and has height at least $h$. Let $|T_h|$ be the number of its nodes.

For $0 le h le c$, $|T_h| ge 1$.
For $h > c cdot i$, with $i in mathbbN^+$, you have:
$$
|T_h| ge 1 + | T_c cdot i | + | T_ c cdot (i-1)| ge 2 | T'_ c cdot (i-1)|,
$$
where $T_c cdot i$, $T_ c cdot (i-1)$, and $T'_ c cdot (i-1)$ are trees of height at least $c cdot i$, $ c cdot (i-1)$, and $ c cdot (i-1)$, respectively, that also satisfy your property.

Let $T$ be a tree of height $H$ from your family. From the above observations (choosing $h=H$) it follows that $|T| ge 2^leftlfloor fracHc+1 rightrfloor ge 2^fracHc+1 - 1$, or equivalently, $H le (c+1)( 1+ log |T|) = O(log |T|)$.

share|cite|improve this answer

edited Jun 4 at 14:13

answered Jun 4 at 13:52

StevenSteven

42339

$endgroup$

add a comment | 

1

$begingroup$

Let $T_h$ be any tree that satisfies your property and has height at least $h$. Let $|T_h|$ be the number of its nodes.

For $0 le h le c$, $|T_h| ge 1$.
For $h > c cdot i$, with $i in mathbbN^+$, you have:
$$
|T_h| ge 1 + | T_c cdot i | + | T_ c cdot (i-1)| ge 2 | T'_ c cdot (i-1)|,
$$
where $T_c cdot i$, $T_ c cdot (i-1)$, and $T'_ c cdot (i-1)$ are trees of height at least $c cdot i$, $ c cdot (i-1)$, and $ c cdot (i-1)$, respectively, that also satisfy your property.

Let $T$ be a tree of height $H$ from your family. From the above observations (choosing $h=H$) it follows that $|T| ge 2^leftlfloor fracHc+1 rightrfloor ge 2^fracHc+1 - 1$, or equivalently, $H le (c+1)( 1+ log |T|) = O(log |T|)$.

share|cite|improve this answer

edited Jun 4 at 14:13

answered Jun 4 at 13:52

StevenSteven

42339

$endgroup$

add a comment | 

$begingroup$

Let $T_h$ be any tree that satisfies your property and has height at least $h$. Let $|T_h|$ be the number of its nodes.

For $0 le h le c$, $|T_h| ge 1$.
For $h > c cdot i$, with $i in mathbbN^+$, you have:
$$
|T_h| ge 1 + | T_c cdot i | + | T_ c cdot (i-1)| ge 2 | T'_ c cdot (i-1)|,
$$
where $T_c cdot i$, $T_ c cdot (i-1)$, and $T'_ c cdot (i-1)$ are trees of height at least $c cdot i$, $ c cdot (i-1)$, and $ c cdot (i-1)$, respectively, that also satisfy your property.

Let $T$ be a tree of height $H$ from your family. From the above observations (choosing $h=H$) it follows that $|T| ge 2^leftlfloor fracHc+1 rightrfloor ge 2^fracHc+1 - 1$, or equivalently, $H le (c+1)( 1+ log |T|) = O(log |T|)$.

share|cite|improve this answer

edited Jun 4 at 14:13

answered Jun 4 at 13:52

StevenSteven

42339

$endgroup$

share|cite|improve this answer

edited Jun 4 at 14:13

answered Jun 4 at 13:52

StevenSteven

42339

answered Jun 4 at 13:52

StevenSteven

42339

answered Jun 4 at 13:52

StevenSteven

42339

0

$begingroup$

Thanks everyone for the answers.
Finally I decided to take the proof of AVL tree has a height of O (log n ) and implenent the recurrence with the constant c.
Basically Avl is a special case of this claim so taking the proof of AVL using the same idea led me to the proof.
Instead of N(h) = N (h-1) + N (h-2) + 1
I used
N(h) = N ( h -1) + N ( h - 1 - c) + 1

share|cite|improve this answer

edited Jun 4 at 21:48

Yuval Filmus

202k15197359

answered Jun 4 at 21:45

Neo182Neo182

113

$endgroup$

add a comment | 

0

$begingroup$

Thanks everyone for the answers.
Finally I decided to take the proof of AVL tree has a height of O (log n ) and implenent the recurrence with the constant c.
Basically Avl is a special case of this claim so taking the proof of AVL using the same idea led me to the proof.
Instead of N(h) = N (h-1) + N (h-2) + 1
I used
N(h) = N ( h -1) + N ( h - 1 - c) + 1

share|cite|improve this answer

edited Jun 4 at 21:48

Yuval Filmus

202k15197359

answered Jun 4 at 21:45

Neo182Neo182

113

$endgroup$

add a comment | 

$begingroup$

Thanks everyone for the answers.
Finally I decided to take the proof of AVL tree has a height of O (log n ) and implenent the recurrence with the constant c.
Basically Avl is a special case of this claim so taking the proof of AVL using the same idea led me to the proof.
Instead of N(h) = N (h-1) + N (h-2) + 1
I used
N(h) = N ( h -1) + N ( h - 1 - c) + 1

share|cite|improve this answer

edited Jun 4 at 21:48

Yuval Filmus

202k15197359

answered Jun 4 at 21:45

Neo182Neo182

113

$endgroup$

share|cite|improve this answer

edited Jun 4 at 21:48

Yuval Filmus

202k15197359

answered Jun 4 at 21:45

Neo182Neo182

113

edited Jun 4 at 21:48

Yuval Filmus

202k15197359

edited Jun 4 at 21:48

Yuval Filmus

202k15197359

answered Jun 4 at 21:45

Neo182Neo182

113

answered Jun 4 at 21:45

Neo182Neo182

113