Двоичное дерево поиска с прошивкой
В вузe дали следующее задание:
Написать программу для работы по запросам оператора с упорядоченной таблицей, реализованной в виде двоичного дерева поиска с прошивкой.
Ключ-целое число. Информация - строка произвольной длинны.
Узел дерева содержит ключ, указатели на правое и левое поддеревья, указатель на следующий узел в обратном порядке следования ключей и указатель на информационной поле.
При выполнении операция удаления и добавления, дерево должно не терять упорядоченности.
У меня возникли следующие вопросы:
Что такое указатель на следующий узел в обратном порядке? Т.е. это указатель на предыдущий узел?
Как мне поддерживать упорядоченность дерева при удалении и добавлении элемента?
Насколько рациональна следующая идея: Обходить измененное дерево и из него строить новое дерево ?
Я правильно понимаю, что под прошивкой понимается ссылка указателей листьев на корень дерева?