Opération de recherche dans l'arbre de recherche binaire

Question

Quelle est la meilleure implémentation de l'opération de recherche dans l'arbre de recherche binaire (récursion ou en boucle)?

Answer 1

Il n'y a pas besoin de récursion si vous souhaitez effectuer une recherche. La récursivité serait excessive pour cette situation. Il suffit d'écrire une boucle et de casser quand on trouve ou se casse au noeud feuille (si non trouvé)

Answer 2

Je trouve généralement la récursivité plus facile à mettre en œuvre et, au moins avec les arbres, rend votre code plus lisible pour d'autres êtres humains. Mais à la fin il dépend de votre arbre est équilibré ou non

• Si votre arbre est équilibré alors je pense que vous pouvez certainement utiliser récursion puisque vous êtes assuré que les appels récursifs ne dépassera pas log (n) (par exemple pour n = 100000000 le pire nombre d'appels récursifs vous devrez faire sont seulement environ 27)

• Si d'autre part votre arbre est pas équilibré alors je pense loopin g est votre meilleur pari car vous devrez peut-être vérifier tous les éléments de l'arbre et la récursivité utilisera une énorme quantité de mémoire pour maintenir la pile.

Answer 3

While(current != null) fonctionne le mieux pour me..Assuming que vous avez déjà votre défini TreeNode de classe y, dans la classe de BST qui étend Comparable et TreeNode = >> implémenter la méthode de recherche booléenne comme ci-dessous

public class BST<E extends Comparable<E>> 
    extends AbstractTree<E> { 

    protected TreeNode<E> root; 

    protected int size = 0; 

~ ~ ~ ~

// Returns true if the element is in the tree 
    public boolean search(E e) { 
    TreeNode<E> current = root; // Start from the root 

    while (current != null) { 
     if (e.compareTo(current.element) < 0) { 
     current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
     current = current.right; 
     } 
     else // element matches current.element 
     return true; // Element is found 
    } 

    return false; 
    } 

Answer 4

En supposant que vous avez une BinaryTreeNode de classe d'entité, ici est la mise en œuvre non récurrent de la recherche d'un nœud binaire Rechercher Arbre:

public static BinaryTreeNode searchBstNode(BinaryTreeNode temp, int data){ 

    while(true){ 
     if(temp.getData()==data){ 
      break; 
     } 
     if(temp.getData()>data){ 
      if(temp.getLeft()!=null){ 
       temp=temp.getLeft();  
      } 
      else{ 
       System.out.println("Data value ="+ data+" not found!"); 
       return null; 
      } 
     } 
     if(temp.getData()<data){ 
      if(temp.getRight()!=null){ 
       temp=temp.getRight(); 
      } 
      else{ 
       System.out.println("Data value ="+ data+" not found!"); 
       return null; 
      } 

     } 
    } 
    System.out.println("Data found in the BST"); 
    return temp; 

Answer 5

Quel est le meilleur des algorithmes seront dépendent du contexte du problème que nous arr aller à résoudre.Cette page wiki montre bien la prison entre ces deux. J'espère que cela sera utile. http://en.wikipedia.org/wiki/Binary_search_algorithm