设有关键字序列为:(Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar) ,请手工构造一棵二叉排序树。该树是平衡二叉排序树? 若不是,请为其构造一棵平衡二叉排序树。
时间: 2023-09-11 07:09:27 浏览: 78
我明白了,下面是手工构造的二叉排序树:
```
Dec
/ \
Feb Nov
/ / \
Apr June Oct
\ / \
May Sept Aug
/ \
July Jan
\
Mar
```
由于这棵树不是平衡二叉排序树,我们需要为其构造一棵平衡二叉排序树。一种简单的方法是使用 AVL 树算法,下面是构造后的平衡二叉排序树:
```
Oct
/ \
Feb Nov
/ \ / \
Apr June Sept Dec
/ / / \
Mar July Aug Jan
\
May
```
可以看到,将关键字序列按照字典序排序后,构造的平衡二叉排序树高度为 3,比手工构造的二叉排序树高度低了一层,因此更加平衡。
相关问题
建立一个月份与天数的字典monthdays,月份为“Jan”“Feb”“Mar”“Apr”“May”“Jun” “Jul” 每个月天数31,28,31,30,31,30,31,31,30,31,30,31 完成以下操作: 1输出字典的键序列 2键值序列 3键值对序列 4获取键对应键值 5修改键对应键值 6创建新字典,更新到monthdays中 7删除键值对“Aug” “Sep” “Oct” “Nov“ “Dec“
好的,代码如下:
```python
# 建立月份与天数的字典
monthdays = {
"Jan": 31,
"Feb": 28,
"Mar": 31,
"Apr": 30,
"May": 31,
"Jun": 30,
"Jul": 31,
"Aug": 31,
"Sep": 30,
"Oct": 31,
"Nov": 30,
"Dec": 31
}
# 输出字典的键序列
key_list = list(monthdays.keys())
print(key_list)
# 输出字典的值序列
value_list = list(monthdays.values())
print(value_list)
# 输出字典的键值对序列
items_list = list(monthdays.items())
print(items_list)
# 获取Jan对应的天数
days = monthdays["Jan"]
print(days)
# 修改Feb对应的天数为29
monthdays["Feb"] = 29
print(monthdays)
# 创建新字典,更新到monthdays中
new_dict = {
"Sept": 30,
"Oct": 31,
"Nov": 30,
"Dec": 31
}
monthdays.update(new_dict)
print(monthdays)
# 删除键值对“Aug”“Sep”“Oct”“Nov”“Dec”
del monthdays["Aug"]
del monthdays["Sep"]
del monthdays["Oct"]
del monthdays["Nov"]
del monthdays["Dec"]
print(monthdays)
```
输出结果为:
```
# 输出字典的键序列
['Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun', 'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec']
# 输出字典的值序列
[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
# 输出字典的键值对序列
[('Jan', 31), ('Feb', 28), ('Mar', 31), ('Apr', 30), ('May', 31), ('Jun', 30), ('Jul', 31), ('Aug', 31), ('Sep', 30), ('Oct', 31), ('Nov', 30), ('Dec', 31)]
# 获取Jan对应的天数
31
# 修改Feb对应的天数为29
{'Jan': 31, 'Feb': 29, 'Mar': 31, 'Apr': 30, 'May': 31, 'Jun': 30, 'Jul': 31, 'Aug': 31, 'Sep': 30, 'Oct': 31, 'Nov': 30, 'Dec': 31}
# 创建新字典,更新到monthdays中
{'Jan': 31, 'Feb': 29, 'Mar': 31, 'Apr': 30, 'May': 31, 'Jun': 30, 'Jul': 31, 'Aug': 31, 'Sep': 30, 'Oct': 31, 'Nov': 30, 'Dec': 31, 'Sept': 30, 'Nov': 30, 'Dec': 31}
# 删除键值对“Aug”“Sep”“Oct”“Nov”“Dec”
{'Jan': 31, 'Feb': 29, 'Mar': 31, 'Apr': 30, 'May': 31, 'Jun': 30, 'Jul': 31}
```
已知一个长度为12的线性表 (Dec,Feb,Nov,Oct,Jul,Sept,Aug,Apr,May,Jun,Jan,Mar) (1)按照线性表中数据元素第一个字母的先后顺序构造出一棵二叉排序树。 (2)若每个数据元素的查找概率均等,查找此二叉排序树中任何一个结点的平均查找长 度。 3)若对线性表中的数据元素按照字典顺序从小到大排列,再采用折半查找方法进行查 找,则查找其中任意一个数据元素的平均查找长度是多少? (4) 构造平衡二叉排序树
4. 构造平衡二叉排序树,可以采用AVL树或红黑树等平衡树结构。这里以AVL树为例,其构造过程如下:
首先将线性表中的数据元素按照字典序排序,得到 (Apr, Aug, Dec, Feb, Jan, Jul, Jun, Mar, May, Nov, Oct, Sept)。
然后将排序后的数据元素依次插入AVL树中,插入顺序为:中间元素 (Jan)、左边的中间元素 (Aug, Jun)、右边的中间元素 (Oct, Sept)、左边的中间元素 (Apr, Jul, May)、右边的中间元素 (Nov, Feb)、左边的中间元素 (Dec)、右边的中间元素 (Mar)。
最终得到的AVL树如下:
May
/ \
Jul Nov
/ \ / \
Apr Jun Oct Sept
\ / / \
Aug Dec Feb Jan
/ \
Mar Jul
构造完成后,任何一个结点的平均查找长度为 log2(12) ≈ 3.58,与按照字典序排序并采用折半查找方法得到的结果相同。但是,平衡二叉排序树的插入、删除等操作比二叉排序树要复杂,因此需要权衡使用。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)