Please use Python to implement

$$ Binary Tree Traversal

$$ AVL Tree Insertion and Deletion

Please follow this guideline!

$$ The solution should contain exactly $1$ file: main.py for Python

$$ You should start your program by initializing an empty AVL tree.

Your program takes one line as input. The input line contains n $$modification moves$$ separated by spaces $(1<=$ n $<=100).$ The available modification moves are

$$ Aint $($Character A followed by an int value between $1$ and $100)$: A$3$ means insert value $3$ into the AVL tree. If $3$ is already in the tree, do nothing.

$$ Dint $($Character D followed by an int value between $1$ and $100)$: D$3$ means delete value $3$ into the AVL tree. If $3$ is not in the tree, do nothing.

Your input is then followed by exactly one finishing move $($PRE or POST or IN$)$: If the finishing move is PRE, then you should print out the tree $($in its current situation$)$ in pre$-$order. If the tree is empty, print out EMPTY. Otherwise, print out the values separated by spaces. POST and IN are handled similarly. You don$$t need to worry about invalid inputs.

need pass all the test cases!

need pass all

Sample input $1$: A$1$ A$2$ A$3$ IN

Sample output $1$: $123$

Sample input $2$: A$1$ A$2$ A$3$ PRE

Sample output $2$: $213$

Sample input $3$: A$1$ D$1$ POST

Sample output $3$: EMPTY

Important:

Test Case $13$

Input: A$69$ D$16$ A$31$ A$98$ A$45$ A$17$ A$50$ D$17$ D$44$ A$87$ D$100$ D$73$ D$95$ D$53$ D$75$ A$30$ D$6$ A$30$ A$46$ A$42$ D$33$ D$26$ D$78$ D$56$ D$79$ D$69$ A$87$ D$75$ A$74$ D$89$ D$89$ A$43$ D$23$ A$58$ D$82$ D$74$ A$90$ A$87$ D$98$ A$75$ D$60$ D$95$ D$35$ A$38$ A$63$ D$99$ A$3$ A$12$ A$81$ D$63$ A$83$ D$61$ D$57$ D$17$ A$65$ D$84$ A$43$ D$82$ A$92$ A$23$ A$74$ D$28$ A$11$ D$66$ D$83$ D$47$ A$88$ D$10$ D$56$ D$100$ A$100$ A$53$ A$93$ A$82$ D$52$ A$25$ D$34$ A$90$ A$43$ A$21$ D$94$ D$73$ A$29$ D$23$ A$93$ A$92$ D$92$ D$74$ D$19$ D$3$ D$56$ A$81$ A$43$ D$28$ A$72$ A$49$ A$20$ D$98$ A$97$ A$21$ PRE

Expected Output: $503021121120252942313845434649816558537572908782889793100$

Test Case $14$

Input: A$60$ D$39$ A$27$ A$5$ A$44$ A$17$ A$75$ A$69$ A$63$ A$50$ D$79$ A$92$ D$59$ D$72$ D$6$ D$17$ D$57$ D$58$ D$67$ A$67$ A$13$ A$61$ D$7$ D$21$ D$64$ D$69$ A$91$ D$26$ D$18$ D$81$ A$89$ D$20$ D$17$ D$6$ A$88$ D$2$ D$84$ D$26$ D$93$ A$96$ A$69$ D$89$ D$30$ D$12$ D$24$ A$60$ A$26$ A$17$ D$54$ D$52$ A$70$ A$88$ A$47$ D$94$ D$9$ D$43$ D$73$ D$33$ A$10$ A$72$ A$77$ A$61$ D$90$ D$22$ D$27$ D$6$ D$31$ A$100$ D$24$ A$78$ A$54$ D$57$ D$64$ A$27$ A$55$ A$73$ D$84$ D$100$ D$76$ D$13$ D$52$ D$43$ A$32$ D$12$ D$29$ D$78$ D$79$ A$31$ D$25$ D$25$ A$94$ D$100$ A$70$ A$6$ A$21$ D$52$ D$33$ D$12$ A$95$ D$76$ PRE

Expected Output: $6032261056172127314744545055706763616988757273779291959496$

Test Case $20$

Input: D$29$ D$7$ A$43$ D$28$ D$90$ A$82$ A$68$ D$56$ D$46$ A$58$ D$26$ D$34$ A$46$ A$56$ A$84$ A$55$ D$34$ D$98$ D$33$ D$45$ D$35$ A$52$ A$31$ D$73$ D$62$ D$61$ D$92$ A$43$ A$100$ A$81$ A$83$ D$10$ D$82$ D$58$ A$91$ D$20$ D$7$ D$90$ A$28$ A$93$ D$2$ A$50$ A$7$ A$9$ D$91$ A$5$ D$51$ A$66$ A$56$ A$40$ A$74$ D$66$ A$57$ D$35$ D$64$ A$95$ D$73$ A$24$ D$23$ A$13$ D$98$ D$1$ D$74$ A$22$ D$69$ A$24$ A$33$ A$71$ A$58$ A$9$ A$77$ A$29$ A$98$ A$64$ D$50$ D$47$ D$33$ A$72$ D$21$ D$93$ A$4$ A$79$ A$61$ D$61$ A$34$ D$82$ D$71$ D$65$ D$8$ A$96$ A$25$ A$62$ A$31$ A$87$ D$20$ A$13$ D$80$ A$36$ A$56$ D$51$ PRE

Expected Output: $5631954724132228252946403436435255816858576462777279958483879896100$

Test Case $26$

Input: A$63$ A$1$ A$40$ A$82$ A$67$ D$71$ A$49$ A$14$ D$31$ A$3$ D$87$ A$91$ A$52$ A$27$ A$39$ A$25$ A$97$ A$4$ A$65$ A$23$ D$13$ D$85$ A$40$ A$59$ D$44$ D$51$ A$25$ D$61$ A$16$ A$31$ A$92$ A$24$ D$14$ A$4$ D$54$ A$1$ A$29$ D$44$ D$99$ A$57$ D$52$ D$82$ A$6$ A$80$ D$30$ A$13$ D$27$ A$46$ D$5$ A$36$ A$53$ D$11$ A$60$ D$31$ A$86$ D$69$ A$37$ D$15$ D$27$ D$41$ D$79$ A$85$ A$8$ D$90$ D$59$ A$62$ D$32$ A$81$ A$56$ D$29$ D$78$ D$14$ D$99$ D$34$ A$17$ A$8$ A$94$ D$53$ D$55$ D$9$ A$68$ D$79$ D$43$ D$88$ A$94$ D$93$ A$60$ A$92$ A$5$ A$79$ D$92$ A$63$ D$45$ A$85$ A$87$ D$9$ A$53$ D$66$ A$5$ D$41$ POST

Expected Output: