How Big Can Balanced Trees Get?

Подписаться 8 тыс.

Просмотров 5 тыс.

50% 1

Follow-up article: / finding-the-index-of-f...
Solving for the bounds on the height of a balanced binary tree, deriving a proof for Binet's formula, and finding room for improvement in Donald Knuth's "The Art of Computer Programming".
Corrections:
- 13:16 These are the first and ZEROTH Fibonacci numbers
Animated with:
The Manim Community Developers. (2021). Manim - Mathematical Animation Framework (Version v0.12.0) [Computer software]. www.manim.community/
Matt Parker's video on complex Fibonacci numbers: • Complex Fibonacci Numb...
Music: Erik Satie's Gnossienne No. 5 Performed by Cleo's Piano
Chapters:
00:00 Introduction
00:21 Some Quick Definitions
01:50 The Question
02:19 The Lower Bound
04:24 The Upper Bound
07:49 Deriving Binet's Formula
15:47 The Solution
17:07 The Discovery

Опубликовано:

31 дек 2021

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 43

@nubdotdev 2 года назад

I've gotten multiple comments regarding the famous $2.56 bounty for finding an error in one of Donald Knuth's books. I sent him an email with my correction and I'm currently waiting for a response, but I'll keep you all updated!

@nonconsensualopinion 2 года назад

For anyone who doesn't know, it can take a long time. Knuth only checks correspondence for "The Art Of Computer Programming" every six months or so. Sometimes it's years. Fortunately it makes it a great surprise when it comes in the mail!

@sageofsixpack226 8 месяцев назад

You haven't found any errors, so I highly doubt applying for the bounty makes any sense

@tk36_real 2 года назад

I love how a channel with 2 Videos has a quality-standard higher than most million-sub channels Keep up the great work Justin!

@zactron1997 2 года назад

Excellent video! Personally one of my favorite ways to tackle problems is to consider minimums and maximums, and narrow in on a true answer. Loved the recursive visualization for the minimum number of nodes in a balanced tree of height n.

@AntiFrenchman 2 года назад

Math for me is like coffee for some people, I love but it but keeps me up at night

@zasmit5232 2 года назад

Amazing video! Love the amazingly high quality of the descriptions, text and animations! Keep up the great work mate

@maheshprabhu 2 года назад

I guess the best way to put it is that you found a tighter bound on the maximum height of a balanced binary tree with N nodes. Knuth's answer isn't wrong, it's just a slightly weaker bound than yours.

@Sadiinso 2 года назад

I was pleasantly surprised by the quality of your first video, and was looking forward to the next one, and I must say that I am not disappointed.

@avanes2694 2 года назад

Glad to see another video here! Love the content and the production quality.

@farbodshahinfar4246 2 года назад

Great job. Thank you for the video.

@ACLNM 2 года назад

Very interesting! Good thing I subscribed and hit the bell. Waiting for your next videos!

@mag2XYZ 2 года назад

Awesome video!

@tecci5502 2 года назад

Wow, you should keep making more videos, they're really interesting!

@nubdotdev 2 года назад

Thank you so much! I’ve got some projects in the works right now so stay tuned!

@tecci5502 2 года назад

@@nubdotdev i'm definitely staying tuned, your editing is phenomenal imo

@matthewjames7513 2 года назад

im glad you're getting the recognition you deserve :)

@tk36_real 2 года назад

13:16 subtle error, but I think you misspoke: x¹=1x+0 corresponds to the first and zeroth fibonacci number

@nubdotdev 2 года назад

You’re absolutely right! I’ll make a note in the description

@theBestInvertebrate Год назад

Looking forward to the next video.

@farianderson168 2 года назад

oh god the sound of piano is awesome being heard through the speech

@CrazyMineCuber 2 года назад

Wow!

@kaylacunningham4417 2 года назад

U did that king go off slay

@Asdayasman 2 года назад

6:41 paused, {0,1,2,4,7,12} the differences between these numbers are the Fibonacci sequence, I wonder if that intuition holds later into the video.

@RisetotheEquation 2 года назад

Great job on video #2. I'll keep you posted if that hack channel steals your content again.

@daboffey 3 дня назад

What are the bounds for a red-black tree?

@plshalpme173 2 года назад

engagement for the algorithm

@CallMeCarlos1 2 года назад

Thanks for the black background

@mrameswari9034 Год назад

shall we get code for this video

@grumpyparsnip 2 года назад

Nice. Just a remark: TeX is pronounced "tek."

@airxperimentboom 2 года назад

I dont understand the expansion at 10:52 Can someone give me more details?

@nubdotdev 2 года назад

Sorry, I should’ve kept it on screen. These expansions follow from repeatedly using the fact that x^n = x^(n-1) + x^(n-2).

@airxperimentboom 2 года назад

@@nubdotdev Oh I understood this part but for instance x^3 = x^2 + x Therefore x^3 = x(x^2+1) How do you get X^3 = 2x + 1 ? It's look like you took the derivative.

@airxperimentboom 2 года назад

Ohh I understood you only did a substitution of the previous expression!

@jamieoglethorpe 2 года назад

Did you get your $2.56 bounty cheque from Donald Knuth? He pays it to whoever points out an error in any of the books.

@nubdotdev 2 года назад

I sent him an email and I'm waiting for a response!

@SuperbonyTheCat 2 года назад

😺

@sekyroww3115 2 года назад

Music is erik satie, correct?

@blokyk 2 года назад

Yep, it's in the description now :)

@kotourn Месяц назад

x^(n-1) + x^(n-2) isn't equal to x^n for example : 2^2 + 2^3 ≠ 2^4 So then the interpretation of the minimun possible size is canceled .. Please correct me if I am wrong .

@c_rem 23 дня назад

He is not claiming that the equation x^n = x^(n-1) + x^(n-2) is valid for all possible values of x and n. He is solving it for a specific value of x so that the equation is valid for all possible values of n, which is true for x={φ, 1-φ} where φ = (1+sqrt(5))/2.