利用关键字序列{3,2,1,4,5,6,7,10,9,8}练习4种平衡树旋转方法 例如: 1) 依次插入3,2,1,插入第三个点1的时候BF(i)=?,属于什么失衡,对最小不平衡树{3,2,1}进行什么旋转。
时间: 2024-03-20 12:44:27 浏览: 26
这是一个很好的练习题,让我们来一步步分析。
首先,让我们将关键字序列{3,2,1,4,5,6,7,10,9,8}插入到一个平衡树中。由于这里没有具体指定平衡树的种类,我们假设使用的是AVL树。插入过程如下:
```
插入3: 3
/ \
- -
插入2: 3
/ \
2 -
/ \
- -
插入1: 2
/ \
1 3
/ \
- -
插入4: 2
/ \
1 3
/ \
- 4
插入5: 2
/ \
1 4
/ \
3 5
插入6: 4
/ \
2 5
/ \ \
1 3 6
插入7: 4
/ \
2 6
/ \ / \
1 3 5 7
插入10: 4
/ \
2 6
/ \ / \
1 3 5 7
\
10
插入9: 4
/ \
2 7
/ \ / \
1 3 5 9
/ \
6 10
插入8: 4
/ \
2 7
/ \ / \
1 3 6 9
/ / \
5 8 10
```
现在我们来回答问题。当插入第三个点1的时候,它会被插入到节点2的左子树中,导致节点2的平衡因子为2,即BF(i)=2。它属于左失衡,因为左子树比右子树高2层。对于最小不平衡树{3,2,1}进行左旋转,得到如下结果:
```
2
/ \
1 3
/ \
- -
```
左旋转后,平衡树恢复了平衡。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)