计算节点的排名在二叉搜索树 [英] Computing rank of a node in a binary search tree

问题描述

如果在二叉查找树的每个节点存储其重量（其子树中的节点的数量），这将是计算在给定节点的等级（其在排序列表索引），为我搜索它的有效方法在树？

If each node in a binary search tree stores its weight (number of nodes in its subtree), what would be an efficient method to compute a rank of a given node (its index in the sorted list) as I search for it in the tree?

推荐答案

启动等级为零。由于二进制搜索继续下来的根源，总结了所有的左子树搜索跳过由的大小。还包括节点沿小于所搜索的项的路径。这些都是搜索路径正确孩子只是父母。

Start the rank at zero. As the binary search proceeds down from the root, sum up the sizes of all the left subtrees that the search skips by. Also include the nodes along the path less than the searched item. These are just the parents of right children on the search path.

也就是说，当搜索那张左（从父左子），它发现没有新的值小于搜索到的项目，所以排名保持不变。当它进入右，父加在左子树的所有节点都小于所搜索的项目，所以加一加左子树尺寸。当它发现搜索到的项目。在包含该项目的节点的左子树的任何项目都小于它，所以它添加到排名。

I.e., when the search goes left (from parent to left child), it discovers no new values less than the searched item, so the rank stays the same. When it goes right, the parent plus all the nodes in the left subtree are less than the searched item, so add one plus the left subtree size. When it finds the searched item. any items in the left subtree of the node containing the item are less than it, so add this to the rank.

把这个放在一起：

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 - 然后初始化排名来1而不是0。

This returns the zero-based rank. If you need 1-based then initialize rank to 1 instead of 0.

这篇关于计算节点的排名在二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！