Удаление узлов из двумерного дерева двоичного поиска

Question

Мне было интересно, может ли кто-нибудь дать полезную информацию об удалении узлов из двумерного дерева двоичного поиска.

Я понимаю, что есть четыре случая, первый из которых я завершил:

1. Удаление узла без дочерних элементов (листа), просто, просто установите указатель на этот узелна ноль.
2. Удаление узла с одним дочерним узлом на левом узле, а правый узел является нулевым.
3. Удаление узла с одним дочерним узлом на правом узле, а левый узел равен нулю.
4. Удаление узла с двумя дочерними элементами, слева и справа.

Я не уверен, как именно выполнить 2,3 и 4. Я пытался сделать это итеративно, однако, похоже, это не работает.Я предполагаю, что это должно быть сделано рекурсивно.Может кто-нибудь, пожалуйста, пролить свет на то, как это будет сделано точно.Это в Java, не должно иметь значения, хотя:)

Answer 1

В двумерном дереве все значения хранятся в конечных узлах. Внутренние узлы просто служат путями к поиску листового узла. В частности, внутренние узлы определяют полуплоскости, в которых содержатся базовые данные. Мы имеем дело только с данными; мы не модифицируем структурные элементы самой структуры данных. Таким образом, имеет место только случай 1 выше. Все остальные не имеют значения.