Извлечение качеств в двоичном дереве поиска

Question

Существуют ли эффективные методы для нахождения числа всех элементов, меньших, чем элемент в двоичном дереве поиска? Я пытался найти процедуру или реализацию на C++, но я не смог. Так что вы имели:

 8 
    / \ 
    3  10 
/\  \ 
1 6  14 

и вы хотите, чтобы найти число узлов менее 10, вы можете получить 4.

Answer 1

Если вы знаете, сколько узлов ниже данного узла (постоянное время), вы можете просто сделать следующее:

int BinarySearchTree::countLessThan(const Node *n, const T &value) const { 
    if (n->value >= value) { 
     // The value has to be in the left sub-tree, so continue searching there: 
     if (n->left) 
      return countLessThan(n->left, value); 
     else 
      return 0; 
    } else { 
     // The value has to be in the right sub-tree, so continue searching there 
     // but include the whole left sub-tree and myself: 
     int count = 1; 
     if (n->left) 
      count += n->left->count(); 
     if (n->right) 
      count += countLessThan(n->right, value); 
     return count; 
    } 
} 

Запустите алгоритм на корневом узле:

int BinarySearchTree::countLessThan(const T &value) const { 
    countLessThan(root, value); 
} 

живой пример можно увидеть здесь: http://ideone.com/JcpjeK

Он работает на следующем дереве (я поменял местами 14 и 10, поэтому 10 может быть левым ребенком 14 лет. Это связано с тем, что моя быстрая и грязная реализация BST допускает только правильный ребенок, если есть уже левый ребенок):

 8 
    / \ 
    3  14 
/\ /
1 6 10 

Answer 2

1. Если вы используете std::map или std::set как ваш BST, вы можете использовать std::map::lower_bound функции члена в сочетании с std::distance:

   auto count = std::distance(bst.begin(), bst.lower_bound(target)); 
   

2. в противном случае, вы можете использовать std::lower_bound удовольствие но он будет оптимальным только с плоскими контейнерами (std::vector), поскольку он предполагает, что контейнер реализует итераторы произвольного доступа.

   auto count = std::distance(
       bst.begin(), std::lower_bound(bst.begin(), bst.end(), target)); 
   

Answer 3

Вы можете сделать что-то вроде этого:

int res = countLessThan(root, value, 0); // res is your answer 

Тогда это реализовать:

int BTree::countLessThan(node *currNode, int value, int count) 
{    
     if(currNode->left != NULL) 
       count = countLessThan(currNode->left, value, count); 

     if(currNode->value >= value) 
       return count; 
     count++; 

     if(currNode->right != NULL) 
       count = countLessThan(currNode->right, value, count); 

     return count; 

}