已知一个长度为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，与按照字典序排序并采用折半查找方法得到的结果相同。但是，平衡二叉排序树的插入、删除等操作比二叉排序树要复杂，因此需要权衡使用。

相关问题

已知一个长度为12的线性表 (Dec,Feb,Nov,Oct,Jul,Sept,Aug,Apr,May,Jun,Jan,Mar) (1）按照线性表中数据元素第一个字母的先后顺序构造出一棵二叉排序树。 (2)若每个数据元素的查找概率均等，查找此二叉排序树中任何一个结点的平均查找长 度。 3)若对线性表中的数据元素按照字典顺序从小到大排列，再采用折半查找方法进行查 找，则查找其中任意一个数据元素的平均查找长度是多少?

1. 按照线性表中数据元素第一个字母的先后顺序构造出一棵二叉排序树，其结构如下：

Dec
\
Feb
\
Nov
/ \
Jul Oct
\
Sept
/
Aug
/ \
Apr May
/ \
Jun Jan
/
Mar

2. 若每个数据元素的查找概率均等，则查找此二叉排序树中任何一个结点的平均查找长度为：

(1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 5) / 12 = 2.92

3. 若对线性表中的数据元素按照字典顺序从小到大排列，再采用折半查找方法进行查找，则查找其中任意一个数据元素的平均查找长度为：

log2(12) ≈ 3.58