en/chapter_tree/avl_tree/

[giscus[bot]]

en/chapter_tree/avl_tree/

Data Structures and Algorithms Crash Course with Animated Illustrations and Off-the-Shelf Code

https://www.hello-algo.com/en/chapter_tree/avl_tree/

[K3v123]

for anyone trying to figure out rather the tree is balanced or not and how to mark the values:
balance in height of LHS - height of RHS.
so if its 0 then it means it is balanced. if its "-" that means the RHS is too heavy and if its "+" then the LHS is too heavy, so then we can decide which rotation method to use.

for marking all the AVL values I like to start at the very end again. using Figure 7-24, as an example:
node 1, 3 is 0 since they don't have a child. 2 is 0 since its balanced. 5 is 0.

another example:
Figure 7-27 the first image ("step 1")
node 0 is 0, 1 is +1 since the RHS don't have a child.
node 4 is 0.
3 is 1 since height of 3 - height of 1 (from node 4).
node 6 is 0.
and 3-1 is 2 so root node 5 is +2.
therefore the left is too heavy.

please note it is the max height of that specific node LHS and RHS. that's why it is 3-1 for root node. (if anyone is wondering).

hope this helps.

[Akane0238]

If there will be more types of BST likes B-Tree, Splay Tree or Red-Black Tree, it will be greater!!

[krahets]

Merged into #1086