将关键字序列（9，1，23，14，55，20，84，27）顺序依次插入初始为空的二叉排序树，并求出等概率情况下

二叉排序树的结构。

将关键字序列（9，1，23，14，55，20，84，27）依次插入初始为空的二叉排序树，得到的树结构如下：

          9
        /   \
       1    23
        \   / \
        14 20 55
             /  \
            27  84

对于等概率情况下的二叉排序树，需要满足以下条件：

1. 根结点为序列中的中位数。
2. 左子树为关键字序列中小于中位数的子序列构成的等概率的二叉排序树。
3. 右子树为关键字序列中大于中位数的子序列构成的等概率的二叉排序树。

由于关键字序列中共有8个数，因此中位数为第4个数，即14。因此，等概率情况下的二叉排序树的根结点为14。将关键字序列分为两个子序列：{9, 1, 14, 23}和{55, 20, 84, 27}。左子树为{9, 1, 14, 23}构成的等概率的二叉排序树，右子树为{55, 20, 84, 27}构成的等概率的二叉排序树。对左子树和右子树分别递归地构造等概率的二叉排序树，得到最终的等概率的二叉排序树。

相关问题

将关键字序列（9，1，23，14，55，20，84，27）顺序依次插入初始为空的二叉排序树

好的，我来回答你的问题。将这个关键字序列依次插入初始为空的二叉排序树，插入的顺序如下：

1. 将 9 插入根节点。
2. 将 1 插入根节点的左子树。
3. 将 23 插入根节点的右子树。
4. 将 14 插入节点 1 的右子树。
5. 将 55 插入节点 23 的右子树。
6. 将 20 插入节点 14 的右子树。
7. 将 84 插入节点 55 的右子树。
8. 将 27 插入节点 23 的左子树。

最终的二叉排序树如下所示：

        9
       / \
      1   23
         /  \
        14  55
            / \
           27  84
               /
              20

需要注意的是，二叉排序树的插入顺序和二叉树的插入顺序不同，二叉排序树的每个节点的左子树都比该节点小，右子树都比该节点大。

将关键字序列（9，1，23，14，55，20，84，27）顺序依次插入初始为空的二叉排序树，并求出等概率情况下查找成功的平均查找长度

等概率情况下查找成功的平均查找长度（ASL）可以通过以下公式计算：

ASL = (根结点深度 + 左子树的ASL + 右子树的ASL) / N

其中，N为关键字序列的长度。

对于本题，可以先构造出二叉排序树，然后再计算等概率情况下查找成功的平均查找长度。

将关键字序列（9，1，23，14，55，20，84，27）依次插入初始为空的二叉排序树，得到的树结构如下：

          9
        /   \
       1    23
        \   / \
        14 20 55
             /  \
            27  84

根结点深度为2，左子树的ASL为(0+1+2)/4=0.75，右子树的ASL为(1+1+2)/4=1.00。因此，等概率情况下查找成功的平均查找长度为：

ASL = (2 + 0.75 + 1.00) / 8 = 0.34375

因此，等概率情况下查找成功的平均查找长度为0.34375。