Вопрос по обходу АВЛ

[nim_cch]

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

тогда тебе нужно хранить и поддерживать в каждой вершине размер поддерева. с ним можно просто за log n найти k-й ключ.

[nim_cch]

Черевато большими затратами памяти

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

[MBo]

>Тогда эта структура много весит
а на баланс какого типа поле отведено?

[nim_cch]

а на баланс какого типа поле отведено?

sbyte

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

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

покажи код, какой у тебя есть, иначе сложно давать конкретные советы