$2.$ AVL Trees $(40$ points$)$

$-$ Which of the trees shown below are balanced? Fill in the code with the ids for the balanced trees. $($e$.$g$.,$ if a was a balanced tree, you should return a list with $\text{'}$a$\text{'}$ included$).$ Back up your decision by determining the balance factor of the root node in each of these trees! $(8$ points$)$

class Question$2$:

$$ @staticmethod

$$ def balancedTrees$()$:

$"""$

$$ Return the list of trees that are balanced.

$$

$$ Choose all that applies from $"$a$","$b$","$c$",$ and $"$d$"$

$$

$$ For example, if you think a$,$ c are balanced and b$,$ d

$$ are unbalanced, you should return $["$a$","$c$"]$

$"""$

$$

$$ return $[]$

$$

$$ @staticmethod

$$ def balanceFactors$()$:

$"""$

$$ Return the balance factor of each tree $($at root$).$

$$ When calculating the balance factor, using left height $-$ right height.

$"""$

$$

$$ return $\{$

$"$a$"$: $0,$ # balance factor for root node for tree $($a$)$

$"$b$"$: $0,$ # balance factor for root node for tree $($b$)$

$"$c$"$: $0,$ # balance factor for root node for tree $($c$)$

$"$d$"$: $0$# balance factor for root node for tree $($d$)$

$\}$

$$

$$ @staticmethod

$$ def insertion$()$:

$"""$

$$ Fill in the AVL tree list after inserting

$10,20,15,25,30,16,18,19$

$$ according to the question.

$$ First two steps is done for you.

$"""$

$$ AVL$\_$tree$\_$lists $=[$

$[10],$

$[10,$ None, $20],$

$$

$]$

$$

$"""$

$$ Fill in the balance factor lists

$$ for each steps of the AVL$\_$tree$\_$lists above.

$$ First two steps is done for you.

$"""$

$$ balance$\_$factors $=[$

$[0],$

$[-1,$ None, $0],$

$$

$]$

$$

$$ return $\{$

$$ "AVL$\_$tree$\_$lists": AVL$\_$tree$\_$lists,

$$ "balance$\_$factors": balance$\_$factors

$\}$

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

$$ pass