依次将结点(56 31 11 49 41 43 73 63 79 99)插入初始状态为空的平衡二叉排序树,使得在每次插入后保持该树仍然是平衡二叉树。请依次画出每次插入后所形成的平衡二叉排序树。
时间: 2024-09-11 09:10:40 浏览: 41
平衡二叉排序树(AVL树)是一种自平衡的二叉搜索树,任何节点的两个子树的高度最多相差1。在每次插入新节点后,如果树不再平衡,需要通过旋转来恢复平衡。下面是依次将给定节点插入到初始为空的平衡二叉排序树中,并保持树平衡的过程。
1. 插入56,树中只有一个节点,自然平衡:
```
56
```
2. 插入31,树不平衡,进行右旋转:
```
56 31
/ / \
31 -> / 56
/ 31
/
```
3. 插入11,树不平衡,进行右左双旋转:
```
31 31 11
/ \ / \ / \
56 11 -> 56 31 -> 31 56
/ \ / \
/ 56 11 49
/
49
```
4. 插入49,树平衡:
```
11 11
/ \ / \
31 56 31 56
/ \ / / \
/ 49 49 49 73
11 31
/
49
```
5. 插入41,树平衡:
```
11 11
/ \ / \
31 56 31 56
/ \ / / \
/ 49 41 49 73
41 31 / \ / / \
11 49 11 31 41 63 73
/ / / /
/ / / /
41 49 / /
```
6. 插入43,树平衡:
```
11 11
/ \ / \
31 56 31 56
/ \ / / \
/ 49 41 49 73
41 31 / \ / / \
43 49 11 31 43 63 73
/ \ / \ /
/ / / / /
11 43 43 63 73
```
7. 插入73,树平衡:
```
11 11
/ \ / \
31 56 31 56
/ \ / / \
/ 49 41 49 73
41 31 / \ / / \
43 49 11 31 43 63 99
/ \ / \ /
/ / / / /
11 43 43 63 73
```
8. 插入63,树平衡:
```
11 11 11
/ \ / \ / \
31 56 31 56 31 56
/ \ / / \ / / \
/ 49 41 49 63 41 63 73
41 31 / \ / / / \
43 49 11 31 43 11 49 73
/ \ / \ / \ /
/ / / / / /
11 43 43 63 43 56
```
9. 插入79,树不平衡,进行左旋转:
```
11 11 11 11
/ \ / \ / \ / \
31 56 31 56 31 56 31 63
/ \ / / \ / / \ / \ \
/ 49 41 49 63 41 63 41 56 73
41 31 / \ / \ / \ / \ / \ /
43 49 11 31 43 56 43 56 73 11 49 56
/ \ / \ / / \ / /
/ / / / / / /
11 43 43 63 43 56 73
```
10. 插入99,树不平衡,进行右旋转:
```
11 11 11 11
/ \ / \ / \ / \
31 56 31 63 31 63 31 63
/ \ / \ / \ / \ / \
/ 49 41 56 41 56 41 73 56 99
41 31 / \ / \ / \ / \
43 49 11 31 11 31 11 49 56 73 99
/ \ / / / \
/ / / / /
11 43 43 43 49
```
阅读全文