请根据关键字序列{23 12 9 26 36 17 14 32 15 20}创建平衡的BST(AVL),要求 1、画出创建后的AVL示意图; 2、计算该AVL查找成功的ASL;
时间: 2024-05-10 18:15:25 浏览: 12
首先,将关键字序列排序得到{9 12 14 15 17 20 23 26 32 36}。根据AVL树的定义,我们可以按照以下步骤创建平衡的AVL树:
1. 将序列的中间元素 17 作为根节点。
2. 将小于 17 的元素 {9, 12, 14, 15} 作为左子树,大于 17 的元素 {20, 23, 26, 32, 36} 作为右子树。
3. 左子树中间元素 12 作为左子树的根节点,小于 12 的元素 {9} 作为左子树,大于 12 的元素 {14, 15} 作为右子树。
4. 右子树中间元素 26 作为右子树的根节点,小于 26 的元素 {20, 23} 作为左子树,大于 26 的元素 {32, 36} 作为右子树。
5. 左子树的右子树中间元素 15 作为左子树的右子树的根节点,小于 15 的元素 {14} 作为左子树,大于 15 的元素为空。
6. 右子树的左子树中间元素 32 作为右子树的左子树的根节点,小于 32 的元素 {20, 23, 26} 作为左子树,大于 32 的元素 {36} 作为右子树。
最终得到的AVL树如下所示:
```
17
/ \
12 26
/ \ / \
9 15 20 32
/ \
14 36
```
AVL树的查找成功ASL为:
```
ASL = (1*1 + 2*2 + 2*3 + 1*4) / 10 = 1.9
```