BST in java in arrays

Question

私はバイナリ検索アルゴリズムを記述しようとしています。配列を検索して配列に挿入するのはコードです。私がしたことは、右の動きがインデックスの2倍、左が1です。コードはここにあります。検索方法が配列を1つずつ順番に繰り返すループより速いかどうかも疑問でした。

public class BinaryTree { 
    int root =0; 
    int right = 2; 
    int left = 1; 
    int arr[]; 
    public void search(int arr[], int value){ 
     if(arr[right] == value){ 
      System.out.println("found"); 
      return; 
     } 
     if(arr[left] == value){ 
      System.out.println("found"); 
      return; 
     } 
     else{ 
      left+=1; 
      right+=2; 
     } 

    } 

    public void insert(int value, int arr[]) { 
      this.arr = arr; 

      if(arr[0]==0){ 
       arr[0] = value; 
       root = arr[0]; 
       System.out.println(root); 
      } 

      if(value>root){ 
       if(arr[right]==0){ 
       arr[right] = value; 
       right+=2; 
       } 

      } 
      if(value<root){ 
       if(arr[left]==0){ 
        arr[left] = value; 
        left+=1; 
        }else{ 
         left+=1; 
        } 
      } 

    } 
    public void printint(){ 
     for(int i=0;i<arr.length;i++){ 
      System.out.print(arr[i]); 

     } 
    } 
    public static void main(String args[]) { 
     int tol[] = new int[9]; 
     BinaryTree tree = new BinaryTree(); 
     tree.insert(4, tol); 
     tree.insert(9,tol); 
     tree.insert(9, tol); 
     tree.insert(2, tol); 
     tree.search(tol, 9); 
     tree.printint(); 
    } 

} 

これはバイナリ検索ツリーと考えられますか？

Answer 1

私はあなたがやろうとしていることについて特定の言葉があると思います。あなたが現在実装している方法では、arr [left]またはarr [right]が0でないときに挿入に失敗します。インデックスをインクリメントした後で再試行するには、いくつかのwhileループを使用する必要があります。

左/右の値を増やしただけなので、それ以降の挿入は機能しますが、値を間違えて増やしているため、値を上書きし始めます。左には（index * 2）+ 1、右には（index * 2）+ 2に増分する必要があります。

ツリーのバランスがとれているほど、検索は高速になります。全くバランスのとれていないツリーは速くなく、バランスの取れたツリーはln（n）（私は思う）になります。

left *= 2; 
left += 1; 

right *= 2; 
right += 2; 

index depth element 
0  0  ROOT 
1  1  L1 
2  1  R1 
3  2  L1L2 
4  2  L1R2 
5  2  R1L2 
6  2  R1R2 
7  3  L1L2L3 
8  3  L1L2R3 
9  3  L1R2L3 
10  3  L1R2R3 
11  3  R1L2L3 
12  3  R1L2R3 
13  3  R1R2L3 
14  3  R1R2R3