TIL (2022.04.04)

1.連結ソート

同一の問題の分割、解決およびマージ=分割およびマージ(Divide and Conquer)
時間複雑度O(Nlogn)=配列過程N回反復+連続分割logn回反復
統合ソート-エンジニア大韓民国
連結ソート-エンコーディング

int mergeSort(int low, int high){
    if(low<high){
        int mid = (low+high)/2;
        mergeSort(low,mid);
        mergeSort(mid+1,high);
        merge(low,mid,high);
    }
}

void merge(int low,int mid,int high){
    int i=low,j=mid+1,k=low;

    while(i<=mid && j<=high){
        if(arr[i]<=arr[j])
            merged[k++]=arr[i++];
        else
            merged[k++]=arr[j++];
    }

    while(i<=mid){
        merged[k++]=arr[i++];
    }
    while(j<=high){
        merged[k++]=arr[j++];
    }
    for(int k=low;k<=high;k++){
        arr[k]=merged[k];
    }
}

2.木

ツリー-頂点間の接続にループは存在しません
リーフノード-サブノードなし
バイナリ・ツリー-サブツリーが最大2個あるため、サブツリーの数は1,0ですが、2未満なので、バイナリ・ツリーです.
ノードの位置がiの場合、右側はi 2+1、左側はi 2再帰的に簡単にナビゲートでき、アクセス順に3つのクラスに分けられます.
(1)電位=親-左-午
(2)中尉=左-親-よ
(3)バック=左-右-親