Найти k-й наименьший элемент в бинарном дереве поиска оптимальным способом

Question

Мне нужно найти k-й наименьший элемент в бинарном дереве поиска без использования статической / глобальной переменной. Как добиться этого эффективно? Решение, которое я имею в виду, заключается в выполнении операции в O (n), наихудшем случае, поскольку я планирую выполнить обход по всему дереву. Но в глубине души я чувствую, что здесь не используется свойство BST. Правильно ли мое предположение или есть лучшее?

Answer 1

Вот только набросок идеи:

В BST левое поддерево узла T содержит только элементы, меньшие, чем значение, сохраненное в T. Если k меньше, чем количество элементов в левом поддереве, k самый маленький элемент должен принадлежать левому поддереву. В противном случае, если k больше, то k наименьший элемент находится в правом поддереве.

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

Теперь предположим, что мы находимся в узле T:

1. Если k == num_elements (левое поддерево T) , то ответ, который мы ищем, это значение в узле T.
2. Если k> num_elements (левое поддерево T) , то очевидно, что мы можем игнорировать левое поддерево, поскольку эти элементы также будут меньше, чем k th самый маленький. Итак, мы сводим проблему к поиску k - num_elements(left subtree of T) наименьшего элемента в правом поддереве.
3. Если k , то k th самый маленький находится где-то в левом поддереве, поэтому мы уменьшаем проблему, чтобы найти k th самый маленький элемент в левое поддерево.

Анализ сложности:

Это занимает O(depth of node) времени, что составляет O(log n) в худшем случае для сбалансированного BST или O(log n) в среднем для случайного BST.

BST требует O(n) хранения, и требуется еще O(n) для хранения информации о количестве элементов. Все операции BST занимают O(depth of node) времени, и требуется O(depth of node) дополнительного времени для поддержания информации о "количестве элементов" для вставки, удаления или поворота узлов. Следовательно, хранение информации о количестве элементов в левом поддереве сохраняет пространственно-временную сложность BST.

Answer 2

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

void findK(Node* p, int* k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}

Answer 3

public int ReturnKthSmallestElement1(int k)
    {
        Node node = Root;

        int count = k;

        int sizeOfLeftSubtree = 0;

        while(node != null)
        {

            sizeOfLeftSubtree = node.SizeOfLeftSubtree();

            if (sizeOfLeftSubtree + 1 == count)
                return node.Value;
            else if (sizeOfLeftSubtree < count)
            {
                node = node.Right;
                count -= sizeOfLeftSubtree+1;
            }
            else
            {
                node = node.Left;
            }
        }

        return -1;
    }

это моя реализация в C #, основанная на алгоритме, который я описал выше, и я подумал, что я опубликую его, чтобы люди могли лучше понять, как он работает для меня

спасибо IVlad

Answer 4

Более простым решением было бы выполнить обход по порядку и отслеживать элемент, который в настоящее время должен быть напечатан, со счетчиком k. Когда мы дойдем до k, выведите элемент. Время выполнения O (n). Помните, что возвращаемый тип функции не может быть пустым, он должен возвращать свое обновленное значение k после каждого рекурсивного вызова. Лучшим решением для этого будет расширенный BST с отсортированным значением позиции в каждом узле.

public static int kthSmallest (Node pivot, int k){
    if(pivot == null )
        return k;   
    k = kthSmallest(pivot.left, k);
    k--;
    if(k == 0){
        System.out.println(pivot.value);
    }
    k = kthSmallest(pivot.right, k);
    return k;
}

Answer 5

// добавить версию Java без рекурсии

public static <T> void find(TreeNode<T> node, int num){
    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();

    TreeNode<T> current = node;
    int tmp = num;

    while(stack.size() > 0 || current!=null){
        if(current!= null){
            stack.add(current);
            current = current.getLeft();
        }else{
            current = stack.pop();
            tmp--;

            if(tmp == 0){
                System.out.println(current.getValue());
                return;
            }

            current = current.getRight();
        }
    }
}

Answer 6

Вы можете использовать итеративный обход inorder: http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal с простой проверкой k-го элемента после извлечения узла из стека.

Answer 7

Учитывая только простое двоичное дерево поиска, все, что вы можете сделать, это начать с самого маленького и пройти вверх, чтобы найти нужный узел.

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

Answer 8

Рекурсивная заказная прогулка со счетчиком

Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack

Идея похожа на решение @prasadvk, но имеет некоторые недостатки (см. Примечания ниже), поэтому я публикую это как отдельный ответ.

// Private Helper Macro
#define testAndReturn( k, counter, result )                         \
    do { if( (counter == k) && (result == -1) ) {                   \
        result = pn->key_;                                          \
        return;                                                     \
    } } while( 0 )

// Private Helper Function
static void findKthSmallest(
    BstNode const * pn, int const k, int & counter, int & result ) {

    if( ! pn ) return;

    findKthSmallest( pn->left_, k, counter, result );
    testAndReturn( k, counter, result );

    counter += 1;
    testAndReturn( k, counter, result );

    findKthSmallest( pn->right_, k, counter, result );
    testAndReturn( k, counter, result );
}

// Public API function
void findKthSmallest( Bst const * pt, int const k ) {
    int counter = 0;
    int result = -1;        // -1 := not found
    findKthSmallest( pt->root_, k, counter, result );
    printf("%d-th element: element = %d\n", k, result );
}

Примечания (и отличия от решения @ prasadvk):

1. if( counter == k ) тест требуется в трех местах: (a) после левого поддерева, (b) после корня и (c) после правого поддерева. Это должно гарантировать, что k-й элемент обнаружен для всех местоположений , т.е. независимо от того, в каком поддереве он находится.

2. if( result == -1 ) требуется проверка, чтобы печатался только элемент результата , в противном случае печатаются все элементы, начиная с k-го наименьшего до корня.

Answer 9

Для не сбалансированного дерева поиска, требуется O (n) .

Для сбалансированного дерева поиска требуется O (k + log n) в худшем случае, но только O (k) в Амортизация смысл.

Наличие и управление дополнительным целым числом для каждого узла: размер поддерева дает O (log n) сложность времени. Такое сбалансированное дерево поиска обычно называется RankTree.

В общем, есть решения (основанные не на дереве).

Привет.

Answer 10

Это хорошо работает: status: массив, который определяет, найден ли элемент. k: k-й элемент, который нужно найти. count: отслеживает количество узлов, пройденных во время обхода дерева.

int kth(struct tree* node, int* status, int k, int count)
{
    if (!node) return count;
    count = kth(node->lft, status, k, count);  
    if( status[1] ) return status[0];
    if (count == k) { 
        status[0] = node->val;
        status[1] = 1;
        return status[0];
    }
    count = kth(node->rgt, status, k, count+1);
    if( status[1] ) return status[0];
    return count;
}