在一棵空的5阶B+树上依次插入11、4、10、7、20、19、2、12、13、0、18、17、15、9、8、1、16、3、5、6、14,设L=3,画出这棵B+树。
时间: 2023-12-28 18:26:17 浏览: 68
以下是在一棵空的5阶B+树上依次插入11、4、10、7、20、19、2、12、13、0、18、17、15、9、8、1、16、3、5、6、14后的B+树:
```
[10,15]
/ \
[2, 4, 7] [12, 13]
/ | \ / | \
[0, 1] [3] [5, 6] [8, 9] [11] [14, 16, 17, 18, 19, 20]
```
相关问题
在一棵空的二叉排序树中插入关键字序列为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。
设有一组关键字序列为(31,23,17,27,19,11,13,91,61,41),要求: (1)采用哈希函数: H ( key )= key mod 7。用链地址法解决冲突,试在0~6的散列地址空间对关键字序列构造哈希表。并计算出在等概率情况下查找成功的平均查找长度;(2)以该关键字序列中的各关键字为叶子构造一棵哈夫曼树,并计算出它的带权路径长度 WPL ; (3)按各关键字在该关键字序列中的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
好的,以下是对应的题解:
1. 哈希表构建
采用哈希函数 $H(key) = key \ mod \ 7$,对于每个关键字,计算出其散列地址并插入哈希表中。若发生冲突,则采用链地址法解决,即在对应散列地址的链表中插入该关键字。
关键字序列为(31,23,17,27,19,11,13,91,61,41),哈希表构建的过程如下:
| 地址 | 关键字 |
| --- | --- |
| 0 | 41 |
| 1 | 31,17 |
| 2 | 23,13 |
| 3 | 27,91 |
| 4 | 19 |
| 5 | 11 |
| 6 | 61 |
在等概率情况下查找成功的平均查找长度为:
$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$
其中 $n$ 为关键字数,$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于采用链地址法解决冲突,所以每个地址上的关键字出现的概率相等,即 $p_i = \frac{1}{n}$。而查找第 $i$ 个关键字时的查找长度与该关键字所在地址上的链表长度 $k_i$ 有关,即 $L_i = k_i + 1$。因此,可以得到:
$$ASL = \frac{1}{n}\sum_{i=1}^n(k_i + 1) = \frac{1}{n}\sum_{i=0}^6(k_i + 1)$$
其中 $k_i$ 表示地址 $i$ 上链表的长度。
2. 哈夫曼树构建
按照哈夫曼树构建的方法,可以得到如下哈夫曼树:
```
289
/ \
125 164
/ \ / \
53 72 82 82
/ \ / \
27 26 30 42
```
其中,每个叶子节点的权值即为对应的关键字,带权路径长度 WPL 为:
$$WPL = 27 \times 1 + 26 \times 2 + 30 \times 2 + 42 \times 2 + 53 \times 3 + 72 \times 3 + 82 \times 3 + 82 \times 3 = 707$$
3. 二叉排序树构建
按照给定的关键字序列,依次插入一棵初始为空的二叉排序树中,可以得到以下二叉排序树:
```
31
/ \
23 91
/ \ \
17 27 41
/ \
19 61
\
13
```
在等概率的情况下查找成功的平均查找长度为:
$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$
其中 $n$ 为关键字数,$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于二叉排序树中各节点的结构与关键字的插入顺序有关,因此 $L_i$ 的值也与插入顺序有关,无法通过概率论的方法进行计算。在一般情况下,二叉排序树的查找成功时间复杂度为 $O(h)$,其中 $h$ 为树的高度。因此,二叉排序树的平均查找长度与树的高度有关,即:
$$ASL = O(h)$$
由于一棵 $n$ 个节点的随机构造的二叉排序树的平均高度为 $O(\log n)$,因此在等概率情况下,该二叉排序树的平均查找长度为 $O(\log n)$。
相关推荐
![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)
![](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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)