Suppression de noeuds d'un arbre de recherche binaire 2d - structures de données, arborescence de recherche binaire, kdtree

Je me demandais si quelqu'un pouvait fournir des informations utiles sur la suppression de nœuds d'une arborescence de recherche binaire 2D.

Je comprends qu'il y a quatre cas, dont le premier que j'ai terminé:

1. Supprimer un nœud sans enfants (une feuille), simplement, définissez simplement le pointeur de ce nœud sur null.
2. La suppression d'un nœud avec un enfant sur le nœud gauche et le nœud droit est nulle.
3. La suppression d'un nœud avec un enfant sur le nœud droit et le nœud gauche est nulle.
4. Suppression d'un nœud avec deux enfants, gauche et droite.

Je ne sais pas comment faire exactement 2,3 et 4. J'ai essayé de le faire de manière itérative, cependant, cela ne semble pas fonctionner. Je suppose que cela doit être fait de manière récursive. Quelqu'un peut-il s'il vous plaît faire la lumière sur la façon dont cela serait fait exactement.

Réponses:

Dans un arbre 2D, toutes les valeurs sont stockées dans la feuillenœuds. Les nœuds internes servent simplement de voies pour localiser le nœud feuille. Plus précisément, les nœuds internes définissent les demi-plans dans lesquels les données sous-jacentes sont contenues. Nous ne traitons que des données; nous ne modifions pas les éléments structurels de la structure de données elle-même. Ainsi, seul le cas 1 ci-dessus est valable. Tous les autres ne sont pas pertinents.