在一个空的二叉排序树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉排序树。
时间: 2023-09-13 09:06:28 浏览: 107
依次插入关键字序列12,7,17,11,16,2,13,9,21,4,得到的二叉排序树如下图所示:
```
12
/ \
7 17
/ \ / \
2 11 13 21
/ \
9 16
/
4
```
解释:首先将12作为根节点插入,然后7比12小,所以插入7的左子树中,17比12大,所以插入17的右子树中,11比7大但比12小,所以插入11的左子树中,16比12大但比17小,所以插入16的右子树中,2比7小,所以插入2的左子树中,13比12大但比17小,所以插入13的右子树中,9比7大但比11小,所以插入9的左子树中,21比17大,所以插入21的右子树中,4比2大,所以插入4的右子树中。最终得到的二叉排序树满足左子树中的所有关键字均小于根节点,右子树中的所有关键字均大于根节点。
相关问题
在一棵空的二叉排序树中插入关键字序列为12,7,17,11,16,2,13,9,21,4请画出所得到的avl树
### 回答1:
首先,我们按照题目给出的关键字序列依次插入到空的二叉排序树中,得到如下的树:
```
12
/ \
7 17
/ \
2 21
\
4
\
11
/ \
9 16
/
13
```
然后,我们需要对这棵树进行平衡操作,使其成为 AVL 树。
第一步,从最底层开始,计算每个节点的平衡因子:
```
0
/ \
-1 1
/ \
-2 1
\
-1
\
0
/ \
-1 0
/
-1
```
第二步,从最底层开始,对每个平衡因子不为 0 的节点进行旋转操作。
对于平衡因子为 -2 的节点 4,我们对它进行右旋操作,得到:
```
12
/ \
7 17
/ \
2 21
\
11
/ \
4 16
/ /
2 13
/
9
```
此时,树的平衡因子为:
```
0
/ \
0 1
/ \
0 1
/
-1
```
对于平衡因子为 -1 的节点 13,我们对它进行左旋操作,得到:
```
12
/ \
7 17
/ \
2 21
\
11
/ \
4 16
/ /
2 9
/ \
13 15
```
此时,树的平衡因子为:
```
1
/ \
0 1
/ \
0 0
/ \
0 -1
```
对于平衡因子为 1 的节点 17,我们对它进行左旋操作,得到:
```
12
/ \
7 16
/ / \
2 13 17
\ \
11 21
/ \
4 9
/ / \
2 8 15
```
此时,树的平衡因子为:
```
0
/ \
0 0
/ \
0 -1
/ \
0 -1
```
最终,我们得到了一棵 AVL 树,如下图所示:
```
12
/ \
7 16
/ / \
2 13 17
\ \
11 21
/ \
4 9
/ / \
2 8 15
```
### 回答2:
在空的二叉排序树中插入关键字序列为12,7,17,11,16,2,13,9,21,4可以按照以下步骤画出对应的AVL树:
1. 首先,将根节点设置为12。
12
2. 插入7,因为7小于12,所以插入为根节点的左子节点:
12
/
7
3. 插入17,因为17大于12,所以插入为根节点的右子节点:
12
/ \
7 17
4. 插入11,因为11小于12,所以将其插入根节点的左子树。发现此时左子树的平衡因子为2,需要进行旋转操作。
首先,对以7为根节点的子树进行右旋转:
12
/ \
11 17
/
7
然后,对以12为根节点的子树进行左旋转:
11
/ \
7 12
\
17
5. 插入16,因为16大于11,所以将其插入根节点的右子树。发现此时根节点的左子树高度为3,右子树高度为2,需要进行旋转操作。
首先,对以12为根节点的子树进行左旋转:
11
/ \
7 16
/ \
12 17
然后,对以11为根节点的子树进行右旋转:
16
/ \
11 17
/ \
7 12
6. 插入2,因为2小于16,所以将其插入根节点的左子树。此时左子树的高度为3,右子树的高度为1,需要进行旋转操作。
首先,对以11为根节点的子树进行右旋转:
16
/ \
11 17
/ \
7 12
/
2
然后,对以16为根节点的子树进行左旋转:
11
/ \
7 16
/ \ / \
2 12 13 17
7. 插入13,因为13大于11,所以将其插入根节点的右子树:
11
/ \
7 16
/ \ / \
2 12 13 17
8. 插入9,因为9小于11,所以将其插入根节点的左子树。
11
/ \
7 16
/ \ / \
2 9 13 17
/
12
9. 插入21,因为21大于11,所以将其插入根节点的右子树。
11
/ \
7 16
/ \ / \
2 9 13 17
\
21
10. 插入4,因为4小于11,所以将其插入根节点的左子树。此时左子树的高度为4,右子树的高度为2,需要进行旋转操作。
首先,对以7为根节点的子树进行右旋转:
11
/ \
4 16
/ \ / \
2 9 13 17
/ \
7 21
\
12
然后,对以11为根节点的子树进行左旋转:
9
/ \
4 11
/ \ / \
2 7 13 16
\
17
\
21
就这样,我们得到了通过插入关键字序列12,7,17,11,16,2,13,9,21,4而得到的AVL树。
### 回答3:
AVL树是一种平衡二叉搜索树,它的每个节点的平衡因子的绝对值不超过1。根据给定的关键字序列,我们可以通过依次插入节点来构建AVL树。
首先,插入关键字12,它作为根节点。接着插入7,由于节点12与节点7之间的高度差为1,它们的平衡因子的绝对值均小于等于1,因此树仍然平衡。
然后插入关键字17,它大于根节点12,因此成为根节点的右子节点。接着插入11,它小于根节点12,成为根节点的左子节点。
继续插入16,它大于11小于17,成为11的右子节点。接下来插入2,它小于11,成为11的左子节点。
再插入13,它大于11小于16,成为16的左子节点。然后插入9,它小于11大于2,成为2的右子节点。
最后插入21和4,它们分别成为17和2的右子节点。
根据上述插入操作所构造的AVL树如下:
12
/ \
7 17
/ \ / \
2 11 16 21
\ /
4 13
\
9
在一棵空的二叉排序树中依次插入关键字序列为49,38,65,97,76,13,27,44,82,35,50,请画出所得到的二叉排序树。求在等概率的情况下进行二叉排序树查找成功的平均查找长度
二叉排序树如下图所示:
```
49
/ \
38 65
/ \ \
13 44 97
/ \ /
27 35 76
\
82
\
50
```
在等概率的情况下进行二叉排序树查找成功的平均查找长度为:
```
平均查找长度 = (1/n) * (1 + 2 + ... + n)
其中,n为二叉排序树中的节点数
```
此处n=12,代入公式得:
```
平均查找长度 = (1/12) * (1 + 2 + ... + 12) = 2.92
```
因此,在等概率的情况下进行二叉排序树查找成功的平均查找长度为2.92。
相关推荐
![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)
![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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)