@Rob Вы можете сделать то же самое с простым BST, где каждый узел содержит как значение, так и индекс элемента, и вы даже можете объединить поиск и вставку в одном действии. Но если в стандартной библиотеке есть что-то, что работает, вы также можете использовать это :-)
я есть задача, которая требует, чтобы я нашел наименьший из всех больших элементов в массиве для всех элементов массива и сохранил соответствующие индексы в массиве, и я не могу понять последнюю часть решения.
Это похоже на проблему, описанную здесь:https://www.geeksforgeeks.org/smallest-greater-elements-in-whole-array/
Единственное отличие состоит в том, что учитываются только значения справа от записи массива (j> i), например:
input: [80; 19; 49; 45; 65; 71; 76; 28; 68; 66]
output: [-1; 7; 4; 4; 9; 6; -1; 9; -1; -1]
Решение с самобалансирующимся деревом имеет для меня смысл. Тем не менее, я все еще должен учитывать индексирование, потому что только решения справа от записи массива являются действительными.
Есть ли способ сопоставить индексирование вставленных значений с записями дерева или создать второе дерево с идентичной структурой, но с индексом старых записей массива вместо фактических значений как узлов? Я не уверен, потому что структура самобалансирующегося дерева, конечно, зависит от вставленных значений (большие значения в правом поддереве, меньшие значения в левом поддереве).
РЕДАКТИРОВАТЬ: На самом деле второе дерево AVL, вероятно, не поможет, так как я должен проверить, что индексирование больше, а запись массива больше при обходе дерева ...