Сохранение глубины узла дерева двоичного поиска

Question

Как сохранить свойство глубины узла дерева двоичного поиска, обновленного после удаления какого-либо объекта?

Я думаю, что для случая, когда я удаляю узел с одним дочерним, я могу установить глубину каждого узла под родительским элементом удалённого узла (исходная глубина - 1).

Однако я не могу придумать, как улучшить глубину обновления, когда я удаляю узел с двумя детьми.

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

Я не ищу для кода, только общий план игры или псевдо-код

Answer 1

Я думаю, что проблема казалась более сложной для меня, чем это было на самом деле. После рисования нескольких деревьев и применения функции удаления на узле с двумя детьми (на бумаге) я заметил, что только один узел действительно изменяется по глубине - узел, который заменяет удаленный узел.

Я установил глубину узла N, который заменил узел R с глубиной R.

Answer 2

Структура данных, которая представляет агрегацию глубины, представляет собой гистограмму, то есть сопоставление словаря с глубины для подсчета. Удаление листа - это одно обновление к гистограмме, а удаление нелиста - упражнение, оставленное читателю.