在一棵空的二叉排序树中依次插入关键字序列为49,38,65,97,76,13,27,44,82,35,50,请画出所得到的二叉排序树。求在等概率的情况下进行二叉排序树查找成功的平均查找长度
时间: 2023-07-27 11:32:22 浏览: 64
二叉排序树如下图所示:
```
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。
相关问题
在一个空的二叉排序树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉排序树。
依次插入关键字序列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树
首先,插入关键字序列到空的二叉排序树中,得到如下图所示的二叉排序树:
```
12
/ \
7 17
/ \
2 21
\
4
\
9
\
11
\
13
\
16
```
然后,我们需要对这棵二叉排序树进行平衡调整,以得到 AVL 树。具体过程如下:
1. 从最后一个被插入的节点开始,依次向上回溯,检查每个祖先节点是否失衡。如果一个节点失衡,则需要进行旋转操作。
2. 对于失衡的节点,分为四种情况:
- LL型:左子树的左子树上插入节点导致失衡,需要进行右旋操作。
- RR型:右子树的右子树上插入节点导致失衡,需要进行左旋操作。
- LR型:左子树的右子树上插入节点导致失衡,需要进行左右旋操作。
- RL型:右子树的左子树上插入节点导致失衡,需要进行右左旋操作。
经过平衡调整后,得到如下图所示的 AVL 树:
```
11
/ \
7 16
/ \ \
2 9 17
\ \ \
4 12 21
\ /
13 19
```
其中,节点的平衡因子为 -1、0、1。
相关推荐
![](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)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)