Чтобы найти самый большой элемент меньше, чем K в BST

Учитывая двоичное дерево поиска и целое число K, я хотел бы найти самый большой элемент меньше, чем K.

В дереве ниже,

for K = 13, result = 12
for K = 10, result = 8
for K = 1 (or) 2, result = -1

      10

  5       12

2   8   11  14

Я попробовал следующую логику. Но есть ли лучший способ сделать это?

int findNum(node* node, int K)
{
        if(node == NULL)
        {
                return -1;
        }
        else if(K <= node->data)
        {
                return findNum(node->left,K);
        }
        else if(K > node->data)
        {
                int t = findNum(node->right,K);
                return t > node->data ? t : node->data;
        }

        return -1;
}

c c++ binary-search-tree
person josh    schedule 13.06.2011    source источник
comment
Вам следует прекратить, если вы найдете К-1. Я не могу сказать по вашему коду, делаете ли вы это (хотя это может быть очевидно, я не знаю С++).   -  person PengOne    schedule 13.06.2011
comment
Пожалуйста, уточните лучше. Более эффективным? Более точным?   -  person Seth Robertson    schedule 13.06.2011
comment
@PengOne: Вы, вероятно, правы в том, что ваше предложение было бы более эффективным, но технически нам не сказали, что BST содержит целые числа, а только ключ поиска.   -  person Seth Robertson    schedule 13.06.2011
comment
@Сет Робертсон: это подразумевается int в его коде.   -  person PengOne    schedule 13.06.2011
comment
@PengOne такая оптимизация, вероятно, будет более дорогостоящей, чем она того стоит, если дерево обычно не содержит K-1. А так как K-1 нигде в коде не встречается и это C, а не Malbolge, мне трудно понять, что нельзя сказать, что такого теста нет в приведенном выше коде.   -  person Jim Balter    schedule 13.06.2011
comment
Почему последний return -1? Может ли он когда-нибудь добраться туда? А над ним можно return t > node->data ? ... поменять на return t == -1 ? ..., эффект тот же, но понятнее что происходит.   -  person Jirka    schedule 03.07.2011

Ответы (5)


arrow_upward
18
arrow_downward

Это O(log n), что является минимумом. Тем не менее, вы можете повысить эффективность (что, кажется, главное, что волнует этих интервьюеров) и устранить возможность переполнения стека (тада!), исключив хвостовую рекурсию, превратив ее в цикл. Кроме того, ваш код не работает, если дерево содержит отрицательные числа... если вы имеете в виду неотрицательные целые числа, вы должны так и сказать, но если интервьюер только что сказал "целые числа", вам нужно немного другой код и другой API. (Вы можете сохранить ту же сигнатуру функции, но вернуть K вместо -1 в случае ошибки.)

Кстати, поскольку это вопрос для собеседования, реализация его путем вызова библиотечной функции скажет большинству интервьюеров, что вы умничка, или упускаете суть, или не знаете, как ее решить. Не возитесь с подобными вещами, просто начните работать над тем, что, как вы знаете, хочет интервьюер.

Вот реализация:

// Return the greatest int < K in tree, or K if none.
int findNum (Node* tree, int K)
{
    int val = K;

    while( tree )
        if( tree->data >= K )
            tree = tree->left;
        else{
            val = tree->data; 
            tree = tree->right;
        }

    return val;
}
person Jim Balter    schedule 13.06.2011

arrow_upward
6
arrow_downward

Я думаю, что идея здесь состоит в том, чтобы записать последний узел, после которого вы переходите к правому поддереву. Поэтому код будет (был обновлен)

int findNum (Node *node, int K)
{
    Node* last_right_move = NULL;

    while (node)
    {
        if (K<=node->data)
            node = node->left;
        else
        {
            last_right_move = node;
            node = node->right;
        }
    }

    if (last_right_move)
        return last_right_move->data;
    else
        return NOT_FOUND;  // defined previously. (-1 may conflict with negative number)
}
person badawi    schedule 14.06.2011

arrow_upward
4
arrow_downward

Я верю в использование стандартных библиотечных средств. Таким образом, мое решение использует std::set. :-)

int largest_num_smaller_than(std::set<int> const& set, int num)
{
    std::set<int>::const_iterator lb(set.lower_bound(num));
    return lb == set.begin() ? -1 : *--lb;
}
person Chris Jester-Young    schedule 13.06.2011

arrow_upward
1
arrow_downward

Я предлагаю вам просмотреть код в вашей локальной реализации set::upper_bound для руководства. Это не решение вашей точной проблемы, но очень близко.

В общем, в реальной жизни большинство этих проблем не нужно решать в собственном коде. STL может выполнять за вас множество обычных задач. Конечно, полезно знать, как их решать, отсюда и тест.

person Steve Townsend    schedule 13.06.2011

arrow_upward
1
arrow_downward

Что сказал первый ответ, и вот логика, почему он не может быть лучше, чем O (log n). Вы ищете наибольшее число меньше K. Это довольно близко к вызову BST-search/get.

Хотя ваш исходный алгоритм выглядит довольно хорошо, я думаю, что это будет быстрее:

    int findNum (node root, int K) {
        if(root == null) return -1;

        if(K > root.val) { 
           if(root.right != null) return findNum(root.right, K);               
           else return root.val; 
        }

        return findNum(root.left, K); //look in left subtree

    }
person Arnab Datta    schedule 27.07.2011