在一棵空的二叉排序树中插入关键字序列为12,7,17,11,16,2,13,9,21,4请画出所得到的avl树
时间: 2023-09-21 11:06:27 浏览: 167
### 回答1:
很抱歉,由于我是一个纯文本AI,无法提供图片或图形的绘制。但是我可以简单地描述一下这棵AVL树的构建过程。
首先,我们按照给出的关键字序列依次插入二叉排序树中。插入顺序为12,7,17,11,16,2,13,9,21,4。
插入12后,这棵树只有一个根节点12。
接着插入7,树变成了:
```
12
/
7
```
再插入17,树变成了:
```
12
/ \
7 17
```
继续插入11,树发生不平衡,需要旋转调整:
```
12
/ \
11 17
/ /
7 13
```
继续插入16,树变成了:
```
12
/ \
11 17
/ / \
7 13 16
```
接着插入2,树又发生不平衡,需要双旋转调整:
```
12
/ \
11 17
/ / \
2 13 16
\
7
```
继续插入13,树变成了:
```
12
/ \
11 17
/ / \
2 13 16
/
7
```
接着插入9,树又发生不平衡,需要旋转调整:
```
12
/ \
11 17
/ / \
2 13 16
/ \
7 9
```
最后插入21和4,树变成了:
```
12
/ \
11 17
/ / \
2 13 21
\ /
7 16
\
9
```
这就是按照给出的关键字序列所得到的AVL树。
### 回答2:
首先,根据插入的关键字序列{12, 7, 17, 11, 16, 2, 13, 9, 21, 4} ,我们可以按照二叉排序树的插入规则,逐个将关键字插入到空的二叉树中。
第一步,插入关键字12,作为根结点,得到如下树:
12
第二步,插入关键字7,小于根结点12,插入到根结点的左子树上,得到如下树:
12
/
7
第三步,插入关键字17,大于根结点12,插入到根结点的右子树上,得到如下树:
12
/ \
7 17
第四步,插入关键字11,小于根结点12,大于结点7,插入到结点7的右子树上,得到如下树:
12
/ \
7 17
\
11
第五步,插入关键字16, 大于根结点12,小于结点17,插入到结点17的左子树上,得到如下树:
12
/ \
7 17
\ /
11 16
第六步,插入关键字2,小于根结点12,小于结点7,插入到结点7的左子树上,得到如下树:
12
/ \
7 17
/ /
2 16
\
11
第七步,插入关键字13, 大于根结点12,大于结点7,小于结点17,插入到结点17的左子树上,得到如下树:
12
/ \
7 17
/ / \
2 16 21
\
11
\
13
第八步,插入关键字9,小于根结点12,大于结点7,小于结点2,插入到结点2的右子树上,得到如下树:
12
/ \
7 17
/ / \
2 16 21
\ /
11 13
/
9
第九步,插入关键字21, 大于根结点12,大于结点17,插入到结点17的右子树上,得到如下树:
12
/ \
7 17
/ / \
2 16 21
\ /
11 13
/
9
第十步,插入关键字4,小于根结点12,小于结点7,小于结点2,插入到结点2的左子树上,得到如下树:
12
/ \
7 17
/ / \
2 16 21
/ \ /
1 4 13
/
9
所得到的AVL树如上所示。
### 回答3:
AVL树是一种自平衡的二叉搜索树,它的特点是每个节点的左子树和右子树的高度差最多为1。下面是根据关键字序列12,7,17,11,16,2,13,9,21,4构建的AVL树:
首先,我们将12插入空的二叉排序树中,得到如下树结构:
12
然后,将7插入到12的左子树中,得到如下树结构:
12
/
7
接着,将17插入到12的右子树中,得到如下树结构:
12
/ \
7 17
继续,将11插入到7的右子树中,得到如下树结构:
12
/ \
7 17
/
11
然后,将16插入到17的左子树中,得到如下树结构:
12
/ \
7 17
/ \
11 16
接下来,将2插入到7的左子树中,得到如下树结构:
12
/ \
7 17
/ \
2 11
\
16
继续,将13插入到17的右子树中,得到如下树结构:
12
/ \
7 17
/ \ \
2 11 13
\
16
然后,将9插入到7的右子树中,得到如下树结构:
12
/ \
7 17
/ \ \
2 11 13
\ \
9 16
最后,将21插入到17的右子树中,得到如下树结构:
12
/ \
7 17
/ \ \
2 11 13
\ \ \
9 16 21
得到的这棵树就是根据关键字序列构建的AVL树。在这棵树中,每个节点的左右子树高度差都为1,满足AVL树的平衡性质。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)