(4) 构造平衡二叉排序树,将过程一步一步用图画出来
时间: 2023-12-02 18:23:06 浏览: 51
好的,下面我用图形的形式来展示构造平衡二叉排序树的过程。
首先将线性表中的数据元素按照字典序排序,得到 (Apr, Aug, Dec, Feb, Jan, Jul, Jun, Mar, May, Nov, Oct, Sept)。
![step1](https://i.imgur.com/1RgWtJ7.png)
然后将排序后的数据元素插入AVL树中,插入顺序为:中间元素 (Jan)、左边的中间元素 (Aug, Jun)、右边的中间元素 (Oct, Sept)、左边的中间元素 (Apr, Jul, May)、右边的中间元素 (Nov, Feb)、左边的中间元素 (Dec)、右边的中间元素 (Mar)。
1. 插入中间元素 Jan:
![step2](https://i.imgur.com/8VXw2wU.png)
2. 插入左边的中间元素 Aug:
![step3](https://i.imgur.com/l7wR9aZ.png)
3. 插入右边的中间元素 Oct:
![step4](https://i.imgur.com/S8Lw9cF.png)
4. 插入左边的中间元素 Apr:
![step5](https://i.imgur.com/1YH1aX4.png)
5. 插入左边的中间元素 Jul:
![step6](https://i.imgur.com/9LmzXqz.png)
6. 插入左边的中间元素 May:
![step7](https://i.imgur.com/MCZwMAy.png)
7. 插入右边的中间元素 Nov:
![step8](https://i.imgur.com/7J0C3YJ.png)
8. 插入右边的中间元素 Feb:
![step9](https://i.imgur.com/2YvQeTt.png)
9. 插入左边的中间元素 Dec:
![step10](https://i.imgur.com/Mi3vO5f.png)
10. 插入右边的中间元素 Mar:
![step11](https://i.imgur.com/9fL5rxM.png)
最终得到的AVL树如下:
May
/ \
Jul Nov
/ \ / \
Apr Jun Oct Sept
\ / / \
Aug Dec Feb Jan
/ \
Mar Jul
构造完成后,任何一个结点的平均查找长度为 log2(12) ≈ 3.58,与按照字典序排序并采用折半查找方法得到的结果相同。