AVL trees in 5 minutes - Intro & Search

Introduction to AVL trees including the search method.
Code: github.com/msambol/dsa/tree/m...
Sources:
1. UW-Madison Data Structures 2011 [web.archive.org/web/201907311...]
2. Ben Pfaff, Performance Analysis of BSTs in System Software [web.stanford.edu/~blp/papers/...]
3. Shivali Bhadaniya & FavTutor, AVL Tree in Python [favtutor.com/blogs/avl-tree-p...]
4. en.wikipedia.org/wiki/AVL_tree
LinkedIn: / michael-sambol

[@Nickdabulder]

Thank you so much, idk why I was struggling so much with other explanations

[@sarvarbazarov8858]

thanks a lot for your videos, they are quite simple and informative !

[@imnotme9757]

I just discover this channel and u, thanks a lot for this video so clean. Big up for u!!!!

[@zivmax]

Great video, brilliant teacher

[@DominicI1]

Awesome video, thanks.

[@bennikllr5509]

Nice Video! i like your short videos.
isn`t the height defined as number of edges from the root node to the leaf node, so in your example it would be 4 at 50?

[@slightly_trash5173]

Heyy just in time🎉

[@migueltmpereira]

My professor shows us some of your videos sometimes during class ( algortithms and data structures). Big up!

[@MichaelSambol]

love it

[@NZ-bg9ec]

in 02:35 in the not avl tree, is it not avl tree to becuase the left child (25) and the right child (75) differs also more than 1? as 3-1=2

[@VaibhavS28]

Thanks!

[@ayoub8393]

To calculate the Balance factor, dont we need to use "Right subtree - Left subtree"? Because in ur example it seems like ur calculating it with "Left subtree - Right subtree". Thats the values are inverted when it comes to positive or negative. Or am I just tripping??
Still very nice playlist, the RB Tree one was very useful.

[@MichaelSambol]

can go either way! just requires some code changes. github.com/msambol/dsa/blob/master/trees/avl_tree.py

[@kvelez]

Perfect.

[@artem2060]

He is alive

[@MichaelSambol]

I'm back! :)

[@jamesclarit1619]

why is height not zero at leaf nodes?

[@triple7triple3zero]

Am I tweaking? I thought the height was the number of edges. Like if you had A->B->C, the height would be 2.

[@fredericoamigo]

Great vid! But why is the height variable set to 1 upon instantiation?

[@aghaaslam9575]

Most of the time you would set height of the leaf to 0 but you could say leaf height is 1 if you actually count Null-Nodes (meaning: in this case both of children are null, because we are talking about leaf) as height of 0. Nevertheless if we are trying to calculate the balance factor, we only need the difference between the height of right children and left children.
I encourage you to try to visualize your self (draw a tree, and calculate the balance tree. Try to change the leaf default heights), you will see that both cases will result in the same balance factor if by both cases you are using the same tree. I hope it explained your concern. If you still have doubts, try to ask someone or use AI to have it visualize for you.

[@oanminhquan1217]

Is there any difference between the big-O with the "-" in the middle with the big-O without it?

[@David-hl9iv]

Yes, there is a significant difference. The big-O complexity gives you the upper bound on time complexity of your function given an input of size n, for example O(n^2), meaning that the function will perform at most c*n^2 operations.
Big-Theta on the other hand gives you both the upper and the lower bound for the time complexity. That means that if the function runs in big-Theta of n^2 then you have to perform a minimum of c_0*n^2 operations and a maximum of c_1*n^2 operations. In time complexity analysis though the constants are ignored because the primary goal of analyzing time complexity is finding out how much slower we get as we make the input larger and not the precise number of operations. If you are interested in learning more I would suggest you read the Wikipedia article on Big O notation where each notation is explained and where you can see more examples, as well as the mathematical definitions of big-O and such.

[@oanminhquan1217]

​@@David-hl9iv Thanks a lot. Really appreciate your explanation!

[@skatlag]

@@David-hl9iv, well is it possible to go from log(n) insert and delete operations, to constant? 2:50

[@Vincent-qh4rg]

🐐

[@ccs8766]

shouldn't the height of the first node will be 4?

[@JM-nn4oe]

yes the height of the root should be 4. the height of an empty tree is -1, leaf nodes is 0. he still gets the same balance factors though via his approach.

[@rahilhil1085]

Plz do the root insertion

[@jimj2683]

Wrong! The height of leaf nodes is always 0. Not 1.

[@epotnwarlock]

What does this change?

[@jwine1957]

​@@epotnwarlockwhen you compute the total height of the tree you get the correct value instead of the wrong value 😂

[@epotnwarlock]

crazy i guess 2 - 1 is different than 1 - 0 @@jwine1957​

[@aghaaslam9575]

It depends on how you code (implement) this AVL-Tree. Most of the time you would set height of the leaf to 0 but you could say leaf height is 1 if you actually count Null-Nodes (meaning: in this case both of children are null, because we are talking about leaf) as height of 0. Nevertheless if we are trying to calculate the balance factor, we only need the difference between the height of right children and left children.
I encourage you to try to visualize your self (draw a tree, and calculate the balance tree. Try to change the leaf default heights), you will see that both cases will result in the same balance factor if by both cases you are using the same tree. I hope it explained your concern. If you still have doubts, try to ask someone or use AI to have it visualize for you.