二叉搜索树的花费与总权怎么计算？关键字和伪关键字又是什么？

1. 二叉搜索树的花费与总权的计算：

• 二叉搜索树的花费指的是所有节点的深度之和，即根节点深度为0，其余节点的深度为其父节点的深度+1。
• 二叉搜索树的总权指的是所有节点的权值之和，即所有节点的关键字之和。

2. 关键字和伪关键字的定义：

• 关键字是指数据结构中用于比较、排序和查找的唯一标识符，通常为节点中存储的数据值。
• 伪关键字是指在数据结构中，为了方便排序或查找而添加的辅助关键字，不一定与节点中存储的数据值完全相同，但保证排序或查找结果与使用真实关键字相同。

在构建二叉搜索树时，为了保证树的平衡性和避免极端情况下的退化，可以使用伪关键字来构建树。具体来说，伪关键字是在原始关键字的基础上添加一些额外信息，使得在构建树时能够更好地平衡左右子树。例如，可以将节点的伪关键字设为其关键字与一个随机数的和，这样可以避免出现多个相同关键字的节点在一条链上的情况。