计算二叉排序树 -40 -5 0 1 2 3 4 5 7 8 10成功查找长度
时间: 2024-01-03 07:04:10 浏览: 29
首先,将这些数字插入到一棵二叉排序树中:
```
2
/ \
-5 4
\ / \
0 3 8
\ \
1 10
/ \
5 7
```
按照二叉排序树的查找方法,从根节点开始,依次比较要查找的值和当前节点的值的大小关系,直到找到目标节点或者遇到空节点为止。在这棵树中查找成功的路径是:2 -> 4 -> 8 -> 7,因此成功查找长度为4。
相关问题
计算中序排序二叉排序树-40 -5 0 1 3 4 5 7 8 10的成功查找长度
中序遍历二叉排序树得到的序列是一个有序序列,因此对于给定的序列,可以构建一棵唯一的二叉排序树。构建后,对于每个要查找的元素,从根节点开始比较,如果当前节点的值等于要查找的值,则查找成功;否则,如果要查找的值小于当前节点的值,则往左子树递归查找,否则往右子树递归查找。每次递归都会深入一层树,因此成功查找长度就是从根节点到查找成功的节点的路径长度。
对于给定的序列,构建的二叉排序树如下所示:
```
4
/ \
0 7
/ \ / \
-5 1 5 8
\ / \
-40 3 10
```
假设要查找的元素依次为 4, 0, 8, 3,成功查找的路径分别为:
- 4:1(根节点)
- 0:2(根节点 -> 左子树 -> 左子树)
- 8:3(根节点 -> 右子树 -> 右子树 -> 右子树)
- 3:4(根节点 -> 右子树 -> 左子树 -> 右子树 -> 左子树)
因此,成功查找长度的总和为 1+2+3+4=10。
二叉排序树-40 -5 0 1 3 4 5 7 8 10的失败平均查找长度
首先,我们需要构建这个二叉排序树。根据二叉排序树的定义,对于每个节点,其左子树的所有节点值都小于该节点值,右子树的所有节点值都大于该节点值。因此,我们可以按顺序将这些数字依次插入到二叉排序树中,得到如下结构:
```
4
/ \
0 8
/ \ / \
-5 1 5 10
/ \ \
3 - 7
```
接下来,我们可以使用失败平均查找长度的公式来计算。失败平均查找长度指的是在查找不成功的情况下,需要查找的平均次数。对于这个二叉排序树,如果我们要查找一个不在树中的数字,它最终会被查找到的位置一定是一个叶子节点或者空节点。
因此,我们可以计算每个叶子节点和空节点的深度,然后根据它们出现的概率计算加权平均值。具体地,假设树中共有n个节点,x个叶子节点和n-x个空节点,则有:
- 叶子节点的深度为1,出现的概率为x/n;
- 深度为2的节点有2(x-1)个,出现的概率为(x-1)/n;
- 深度为3的节点有2(x-2)+4(x-2)个,出现的概率为(x-2)/n;
- 以此类推,深度为k的节点有2(x-k+1)+4(x-k+2)+...+2^(k-1)(x-1)+2^k(n-x)个,出现的概率为1/n。
因此,失败平均查找长度为:
```
FASL = (x/n) * 1 + ((x-1)/n) * 2 + ((x-2)/n) * 3 + ... + (1/n) * k
```
对于这个二叉排序树,可以计算出x=5,n=9,代入公式得:
```
FASL = (5/9) * 1 + (4/9) * 2 + (3/9) * 3 + (2/9) * 4 + (1/9) * 5
= 2.6
```
因此,这个二叉排序树的失败平均查找长度为2.6。