Найти медиану AVL-дерева

Question

Я немного искал и нашел связанный пост: Get median from AVL tree? , но я не слишком доволен ответом.

Мои мысли по решению этой проблемы:

• Если коэффициент баланс 0, обратный корень
• еще держать удаление корня, пока дерево не является полностью сбалансированным, и вычислить медиану корней просто удален

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

Может кто-нибудь подтвердить или исправить мои идеи? благодаря!

Answer 1

Есть две проблемы в вашем Предложенный подход:

• Вы разрушаете свое дерево в процессе (или занимают в два раза больше памяти для «резервного» копия)
• В худшем случае, вы для получения полностью сбалансированного дерева требуется довольно много корневых изъятий (я думаю, что в худшем случае он будет близок к удалению 2^(n-1)-1) ... и вам все равно нужно будет вычислить медиана из этого.

Ответ на ваш связанный вопрос правильный и оптимальный. Обычный способ решения этой задачи - построить Order statistic tree (путем хранения количества элементов левого и правого поддерева для каждого узла). Имейте в виду, что вы должны соответственно компенсировать цифры, если происходит поворот дерева AVL.

См. Ответ IVlad here. Так как дерево AVL гарантирует работу O(log n)Поиск и алгоритм IVlad является по существу Поиск операции, вы можете найти в k -го наименьшего элемента в O(log n) времени и O(1) пространстве (не считая места для самого дерева).

Предполагая, что ваше дерево индексируется от 0 и имеет n элементы, найти медиану следующим образом:

• если n нечетное: Найти (n-1)/2 -ю элемент и возвращает его
• если n является даже: Найти n/2 -го и (n/2)-1 элементов и вернуть их в среднем

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