依次输入关键字16,3,7,11,9,26,18,14,15,插入初始状态为空的平衡二叉树,请依次画出每次插入后所形成的平衡二叉树。
时间: 2024-05-30 17:04:34 浏览: 26
以下是每次插入后形成的平衡二叉树:
1. 插入关键字16,树根为16。
```
16
```
2. 插入关键字3,与树根16比较,比16小,到左子树中查找,左子树为空,插入此位置,检查祖先未发现失衡,如下图所示。
```
16
/
3
```
3. 插入关键字7,与树根16比较,比16小,到左子树中查找,比3大,到右子树中查找,右子树为空,插入此位置,检查祖先未发现失衡,如下图所示。
```
16
/ \
3 7
```
4. 插入关键字11,与树根16比较,比16小,到左子树中查找,比3大,到右子树中查找,比7大,到右子树中查找,右子树为空,插入此位置,检查祖先未发现失衡,如下图所示。
```
16
/ \
3 7
\
11
```
5. 插入关键字9,与树根16比较,比16小,到左子树中查找,比3大,到右子树中查找,比7小,到左子树中查找,左子树为空,插入此位置,检查祖先未发现失衡,如下图所示。
```
16
/ \
3 7
\ \
11 9
```
6. 插入关键字26,与树根16比较,比16大,到右子树中查找,右子树为空,插入此位置,检查祖先未发现失衡,如下图所示。
```
16
/ \
3 7
\ \
11 9
\
26
```
7. 插入关键字18,与树根16比较,比16大,到右子树中查找,比26小,到左子树中查找,左子树为空,插入此位置,25节点失衡,从不平衡节点到新节点路径前两个是LR,做LR型旋转调整平衡,如下图所示。
```
16
/ \
3 18
\ / \
11 7 26
\
9
```
8. 插入关键字14,与树根16比较,比16小,到左子树中查找,比18小,到左子树中查找,比11大,到右子树中查找,右子树为空,插入此位置,检查祖先未发现失衡,如下图所示。
```
16
/ \
3 18
\ / \
11 7 26
/ \
9 14
```
9. 插入关键字15,与树根16比较,比16小,到左子树中查找,比18小,到左子树中查找,比11大,到右子树中查找,比14大,到右子树中查找,右子树为空,插入此位置,25节点失衡,从不平衡节点到新节点路径前两个是RL,做RL型旋转调整平衡,如下图所示。
```
16
/ \
3 15
\ / \
11 14 18
/ / \
9 7 26
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)