По моему личному мнению, дополнительное преимущество, связанное с предоставлением вам минимума / максимума, не гарантируется. Это действительно может принести больше вреда, чем пользы, мешая вам думать о том, как вы должны в идеале думать об этой проблеме. Если у вас есть какие-либо проблемы здесь, я настоятельно рекомендую вам посмотреть, как найти минимальное значение в O (N), как найти элемент K-порядка в O (N) и как отсортировать список с помощью быстрой сортировки в O (nlogn). ) для списка. Как только вы поймете эти понятия, эту проблему станет легче понять.
1) Modify the tree so that the tree and all its nodes will have the size of the tree as an additional parameter not just value (you can try to do this in the add operation of the BST). You can add the element to the BST, and then recalculate the sizes of each node which should be O(logN + logN) = O(logN)
2) You can also do this for deletes (or rather after deletes) O(logN + logN) = O(logN)
3) Then you can perform a K-order median select on the new BST see 4)
4) O (logN) * 1004 *
if(left.size === right.size)
return root.value
if(left.size < right.size)
return recursiveFunction(root.right)
if(left.size > right.size)
return recursiveFunction(root.left)
Мой анализ асимптотики c может быть неверным на шагах 2 или 3, поэтому я приглашаю всех, у кого есть больше знаний, внести свой вклад.
И, конечно же, вы можете изменить # 4, чтобы выполнить поиск по K-порядку для min / max в logN, а не только для медианного значения.
Необходимо выполнить корректировку для деревьев AVL четного размера, используя методику K-порядка ниже. Вы также можете просто обработать четный случай по-другому, где, если левый больше на 1, тогда root, а правый root требует усреднения. Если справа больше на 1, то усредните значения root и слева от root.
. Вы можете попытаться реализовать логику c для обоих случаев, используя абсолютные различия между левой и правой и если оно равно 0, вернуть root. Если оно равно 1, а слева больше, сделайте то, что я описал выше (см. Следующий шаг, если вы не понимаете, о каком шаге я имею в виду) И если оно равно 1 и справа больше, среднее значение root и слева от root как описано выше
Источники:
https://en.wikipedia.org/wiki/Order_statistic_tree
Этот подход также работает для деревьев с дублирующимися значениями, но он полностью зависит от его осуществление.