Найдите kth самый маленький элемент в дереве двоичного поиска Оптимальным способом

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

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

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

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

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

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

В целом, существуют решения (основанные не на дереве).

С уважением.

Это то, что я подумал, и это работает. Он будет работать в o (log n)

public static int FindkThSmallestElemet(Node root, int k)
    {
        int count = 0;
        Node current = root;

        while (current != null)
        {
            count++;
            current = current.left;
        }
        current = root;

        while (current != null)
        {
            if (count == k)
                return current.data;
            else
            {
                current = current.left;
                count--;
            }
        }

        return -1;


    } // end of function FindkThSmallestElemet

Для двоичного дерева поиска обход по порядку вернет элементы ... по порядку.

Просто выполните обход в порядке и остановитесь после обхода k элементов.

O (1) для постоянных значений k.