search - 二分探索木での探索操作

Question

二分探索木(再帰またはループ)での検索操作のより良い実装はどれですか?

Answer 1

検索する場合、再帰は必要ありません。この状況では、再帰はやり過ぎです。ループを記述して、見つかったときにブレークするか、リーフ ノードでブレークする (見つからない場合)

Answer 2

通常、再帰は実装が簡単で、少なくともツリーを使用すると、他の人間にとってコードが読みやすくなります。しかし、最終的には、ツリーのバランスが取れているかどうかによって異なります

• ツリーのバランスがとれている場合、再帰呼び出しが log(n) を超えないことが保証されているため、確実に再帰を使用できると思います(たとえば、 n=100000000 の場合、実行する必要がある再帰呼び出しの最悪の数は約 27 です)。

• 一方、ツリーのバランスが取れていない場合は、ツリーのすべての要素をチェックする必要があり、再帰はスタックを維持するために大量のメモリを使用する可能性があるため、ループが最善の策だと思います。

Answer 3

While(current != null) 動作します。

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

どのアルゴリズムが最適かは、解決しようとしている問題のコンテキストによって異なります。これが役立つことを願っています。 http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 5

エンティティ クラス BinaryTreeNode があると仮定すると、バイナリ検索ツリーでノードを検索する非再帰的な実装は次のとおりです。

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;