Алгоритм определения количества узлов с ключом, превышающим целое число K на BST

Question

У меня была следующая проблема в тесте неделю назад. Я не получил свою оценку, но я уверен, что мое решение не полностью охватило все базовые случаи проблемы.

Утверждение следующее:

Для дерева бинарного поиска напишите алгоритм (используя псевдокод), который вычисляет количество узлов с ключом, большим или равным данному целому числу k. Ваш алгоритм должен работать в наихудшее время O (h), где h - высота дерева двоичного поиска.

Предположим, у вас есть метод subtreeSize (treeNode n), который выполняется за время O(1) и возвращает количество узлов в поддереве с корнем в n, включая сам n.

Это мое решение:

nbNodesGreaterEqual(treeNode n, int k){

    if(n == null) return 0;
    if(n.getValue() >= k) return 1 + substreeSize(n.getRightChild()) + nbNodesGreaterEqual(n.getLeftChild(), k);
    if(n.getValue < k) return nbNodesGreaterEqual(n.getRightChild,k);
}

Мой алгоритм завершен? Кроме того, есть ли способ написать этот же алгоритм для обычного двоичного дерева (не BST), которое не проходит через все узлы?

Answer 1

Предполагая, что правый дочерний элемент узла содержит ключ, больший или равный ключу, хранящемуся в этом узле. Идея состоит в том, чтобы идти вниз по правой ветви, пока мы не найдем узел, ключ которого больше или равен k. Если мы находим узел с ключом, равным k, мы знаем, что все узлы справа должны иметь ключи больше k. Итак, мы берем размер этого поддерева. Добавьте 1 с этим, потому что эти узлы также должны быть подсчитаны. В случае, если мы перестали идти вниз по правой ветви, когда нашли узел с ключом, большим, чем k, мы знаем, что нужно включить правое поддерево, и есть вероятность того, что некоторые приемлемые узлы будут найдены в левом поддереве. Таким образом, мы вызываем функцию рекурсивно на левом поддереве. Наконец, добавляется 1, потому что этот узел тоже должен учитываться. Базовый случай, когда узел равен нулю, мы возвращаем 0.

ksum(node, k)      
  x = 0
  node==null
      return 0
  if node->key < k
     x = ksum(node->right, k)
  else if node->key == k
     x = subtreesize(node->right) + 1
  else
     x = subtreesize(node->right) + ksum(node->left, k) + 1

  return x