Кто-нибудь знает быстрый способ определить, на каком уровне данный элемент находится в TreeSet ? Под уровнем я подразумеваю глубину этого элемента в дереве, то есть количество его предков.
Фоновая.
Я использую класс TreeSet Java для хранения своих элементов.
Чтобы сравнить два элемента, мне нужно вычислить некоторую вспомогательную информацию о них. Я не могу хранить эту вспомогательную информацию для каждого элемента, так как это заняло бы слишком много памяти.
С другой стороны, если я создаю вспомогательную информацию для каждого сравнения, моя программа работает слишком медленно.
Когда элемент вставляется в TreeSet, моя текущая реализация вычисляет вспомогательную информацию для элемента, который он вставляет, и не пересчитывает его, пока элемент не найдет свое место в TreeSet. После этого вспомогательная информация отбрасывается.
Чтобы ускорить мою программу, я хотел бы сохранить вспомогательную информацию также для верхних уровней TreeSet, поскольку они участвуют во многих сравнениях. Итак, после сравнения двух узлов я хотел бы решить, сохранять ли или отбрасывать их вспомогательную информацию на основе их глубины в TreeSet.
Update.
Я также был бы благодарен, если бы кто-нибудь мог предложить альтернативный класс, реализующий какие-то сбалансированные деревья (AVL-деревья, красные / черные деревья, Splay-деревья, ...), и где каждый имеет доступ к высоте элемент.