计算二叉搜索树中节点的等级

dissem 发表于 Dev

异见

如果二叉搜索树中的每个节点都存储其权重（子树中的节点数），那么当我在树中搜索给定节点（排序列表中的索引）时，这将是一种有效的方法来计算其排名？

基因

从零开始排名。当二进制搜索从根向下进行时，添加搜索跳过的所有左侧子树的大小，包括找到的节点的左侧子树。

即，当搜索左移时（从父级到左子级），它发现的新值不会小于搜索到的项，因此排名保持不变。正确时，父级加上左侧子树中的所有节点都小于搜索到的项目，因此加一个加上左侧子树的大小。找到搜索到的项目时。包含该项目的节点的左子树中的任何项目均小于该项目，因此请将其添加到等级中。

放在一起：

int rank_of(NODE *tree, int val) {
  int rank = 0;
  while (tree) {
    if (val < tree->val) // move to left subtree
      tree = tree->left;
    else if (val > tree->val) {
      rank += 1 + size(tree->left);
      tree = tree->right;
    }
    else 
      return rank + size(tree->left);
  }
  return NOT_FOUND; // not found
}

这将返回从零开始的排名。如果需要从1开始，则初始化rank为1而不是0。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。