已知长度为12的表:{Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec}。请按首字母顺序,依次插入一棵初始为空的二叉树,试画出插入完成之后的二叉排序树,并求平均查找长度。
时间: 2023-08-18 16:09:18 浏览: 181
按首字母顺序插入后的二叉排序树如下图所示:
```
May
/ \
/ \
Apr Oct
/ \ / \
Aug Dec Jan Nov
/ / \ \
Jul Feb Mar Sep
```
平均查找长度为:
`ASL = (1+2+2+3+3+3+3+3+4+4+4+4)/12 = 2.917`
相关问题
已知如下所示长度为12的表:(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) ①试按表中元素的顺序依次插入一棵初始 为空的二叉排序树,画出插入完成之后的二叉排 序树,并求其在等概率的情况下查找成功的平均 查找长度。 ③按表中元素顺序构造一棵平衡二叉排序 树,并求其在等概率的情况下查找成功的平均查 找长度。
好的,我会尽力回答您的问题。
① 按照元素顺序插入二叉排序树的过程如下:
首先,将 Jan 插入根节点,得到如下的二叉排序树:
```
Jan
/ \
None None
```
接着,将 Feb 插入根节点的右子树,得到如下的二叉排序树:
```
Jan
\
Feb
/ \
None None
```
继续插入 Mar,Apr,May,June,July,Aug,Sep,Oct 和 Nov,最终得到如下的二叉排序树:
```
Jan
/ \
None Feb
/ \
Apr Mar
/ \ / \
July June May Aug
/ \ / \
None Oct Sep Nov
```
在等概率的情况下查找成功的平均查找长度为(1+2+2+3+3+3+3+4+4+4+4+4)/12 = 2.92。
③ 按照元素顺序构造平衡二叉排序树的过程如下:
首先,从表中间取出 July 作为根节点,得到如下的平衡二叉排序树:
```
July
/ \
Apr Nov
/ \ / \
Jan June Oct Dec
\ / /
Feb May Aug
```
在等概率的情况下查找成功的平均查找长度为(1+2+2+3+3+3+3+4+4+4+4+4)/12 = 2.92,与①中的结果相同。
希望这个答案能够对您有所帮助。如果您还有其他问题,请随时问我。
已知一个长度为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)