Supprimer la méthode de l'arbre de recherche binaire
Je suis en train de mettre en œuvre une méthode remove de la BST de la structure que j'ai été travailler sur. Voici le code avec la fonction de recherche, d'insertion et méthodes de suppression:
public class BST {
BSTNode root = new BSTNode("root");
public void insert(BSTNode root, String title){
if(root.title!=null){
if(title==root.title){
//return already in the catalog
}
else if(title.compareTo(root.title)<0){
if(root.leftChild==null){
root.leftChild = new BSTNode(title);
}
else{
insert(root.leftChild,title);
}
}
else if(title.compareTo(root.title)>0){
if(root.rightChild==null){
root.rightChild = new BSTNode(title);
}
else{
insert(root.rightChild,title);
}
}
}
}
public void find(BSTNode root, String title){
if(root!= null){
if(title==root.title){
//return(true);
}
else if(title.compareTo(root.title)<0){
find(root.leftChild, title);
}
else{
find(root.rightChild, title);
}
}
else{
//return false;
}
}
public void remove(BSTNode root, String title){
if(root==null){
return false;
}
if(title==root.title){
if(root.leftChild==null){
root = root.rightChild;
}
else if(root.rightChild==null){
root = root.leftChild;
}
else{
//code if 2 chlidren remove
}
}
else if(title.compareTo(root.title)<0){
remove(root.leftChild, title);
}
else{
remove(root.rightChild, title);
}
}
}
M'a dit que je pouvais utiliser la méthode insert pour m'aider avec la méthode remove, mais je ne le vois juste pas comment je peux récupérer le plus petit/plus grand élément, puis remplacer celui que je suis de les supprimer avec cette valeur, puis, de manière récursive supprimer le nœud que j'ai pris de la valeur de remplacement, tout en conservant O(logn) de la complexité. N'importe qui ont des idées ou flagrante trous que j'ai raté, ou toute autre chose utile que je frappe ma tête sur ce problème?
EDIT:
J'ai utilisé les réponses des idées à venir avec ce qui, je crois, va fonctionner, mais j'obtiens une erreur que mes méthodes (et pas seulement de le supprimer) doit retourner Cordes, voici à quoi ressemble le code, j'ai pensé que c'est le retour des déclarations??
public String remove(BSTNode root, String title){
if(root==null){
return("empty root");
}
if(title==root.title){
if(root.leftChild==null){
if(root.rightChild==null){
root.title = null;
return(title+ "was removed");
}
else{
root = root.rightChild;
return(title+ "was removed");
}
}
else if(root.rightChild==null){
root = root.leftChild;
return(title+ "was removed");
}
else{
String minTitle = minTitle(root);
root.title = minTitle;
remove(root.leftChild,minTitle);
return(title+ "was removed");
}
}
else if(title.compareTo(root.title)<0){
remove(root.leftChild, title);
}
else{
remove(root.rightChild, title);
}
}
String minTitle = minTitle(root.rightChild)
comme suggéré ici (algolist.net/Data_structures/Binary_search_tree/Removal)
OriginalL'auteur dawich77 | 2013-11-09
Vous devez vous connecter pour publier un commentaire.
doux, laissez-moi savoir si cela fonctionne, bonne chance!
Je pense que c'théoriquement fonctionne, je suis juste d'avoir de la difficulté avec l'ensemble de mes méthodes en disant qu'ils doivent retourner une chaîne de caractères, même si j'inclus le retour de déclarations, certains autres bugs, code à suivre
Compris la question du retour, maintenant tout fonctionne merci!
Vous êtes les bienvenus!
OriginalL'auteur Josh Engelsma
OriginalL'auteur sanjay
Pour comparer des objets en java utiliser .méthode equals() au lieu de "==" opérateur
vous devez utiliser comme cette
ou si vous êtes interesed d'ignorer l'affaire a suivre ci-dessous le code
OriginalL'auteur Prabhakaran
OriginalL'auteur Shawn
Je sais que c'est une très vieille question, mais de toute façon... accepté La réponse de la mise en œuvre est prise à partir de c++, donc l'idée de pointeurs existe encore, ce qui devrait être changé, car il n'y a pas de pointeurs en Java.
Donc, à chaque fois lorsque vous modifiez le nœud à null ou quelque chose d'autre, à l'instance du nœud est changé, mais pas l'original
Cette mise en œuvre est tirée de l'un des coursera cours sur les algorithmes.
Tous les liens entre les nœuds sont appartenait à l'aide de la valeur de retour de la récursivité.
OriginalL'auteur psykid