Create an AVL tree for the data
給資料建立AVL樹
資料 20、30、10、50、60、40、45、5 請建立成一棵 AVL 樹，（6 分）請依序
刪除 60 及 30，在推導過程需註明旋轉的類別。（6 分
首先，建立一棵 AVL 樹並插入給定的資料：20、30、10、50、60、40、45、5。 AVL 樹的平衡操作包括旋轉，這些旋轉有LL旋轉、LR旋轉、RR旋轉和RL旋轉。
1. 插入 20，樹變成：
```
20
```
2. 插入 30，樹變成：
```
20
\
30
```
3. 插入 10，需要進行旋轉（RR旋轉），樹變成：
```
20
\
30
/
10
```
4. 插入 50，樹變成：
```
20
\
30
/ \
10 50
```
5. 插入 60，需要進行旋轉（LL旋轉），樹變成：
```
30
/ \
20 50
/ / \
10 40 60
```
6. 插入 40，需要進行旋轉（LR旋轉），樹變成：
```
30
/ \
20 50
/ / \
10 40 60
/
45
```
7. 插入 5，需要進行旋轉（RR旋轉），樹變成：
```
30
/ \
20 50
/ / \
10 45 60
/
40
```
AVL 樹現在已經平衡了。
接下來，我們依序刪除節點 60 和 30：
刪除 60：
```
30
/ \
20 50
/ / \
10 45 -
/
40
```
刪除 30，需要進行旋轉（LL旋轉）：
```
40
/ \
20 50
/ /
10 45
```
現在，AVL 樹仍然是平衡的。
Comments
Post a Comment