【アウトプット】木構造（ツリー構造）

学びたてホヤホヤのアウトプットになります。
説明が間違っている場合などは、ご指摘いただけますと幸いです。

二分木（binary tree）

データ構造の1つで、1つの親ノードが2つの子ノードを持つもの。
二分木は大量のデータを効率よく探索できるメリットがある。

以下、二分木の種類。

全二分木（full binary tree）

全てのノードが「子ノードを持たない　もしくは　2つの子ノードを持つ」二分木のこと。
つまり、子ノードを1つだけ持つようなノードは存在しないということ。

完全二分木（perfect binary tree）

全てのリーフノードが同じ深さを持つ二分木のこと。
親-子-孫　の３階層ある場合、リーフノードは4つになるということ。

一方で、場合によっては「最下層を除いた全ての階層はノードで満たされ、かつ最下層においてはリーフノードが左側から順に詰められている二分木」のことを指すこともある（こちらも「完全二分木」ではあるものの「（complete binary tree）」と言う）。

また、完全二分木は以下の性質を持つ。

• ルートノードを0階層とした場合、その階層（i）が持つノードの数は「２^i」となる。
• リーフノード以外の内部ノードの合計は「2^i -1」となる。

二分探索木（ binary search tree）

ツリーの各ノードの値が「左の子ノード ≤ 親 ≤ 右の子ノード」という制約を持つ二分木のこと。
二分探索木は、データの探索を簡単にするもの。
探したい値（キー）が決まると、まずはルートノードから探索を始める。ルートノードの値とキーを比較し、もしキーが小さい場合は左の子ノード、大きい場合は右の子ノードへと探索を続ける。これをキーが見つかるまで繰り返し行う。

一方で、例えば「1,2,3,4,5」という値を持つノードがあり、ルートノードが5、その左の子ノードが4、その左の子ノードが3、
その左の子ノードが2、その左の子ノードが１となってしまっている場合、探索効率は非常に悪くなってしまう。

平衡二分探索木（self-balancing binary search tree）

ルートノードから各リーフノードまでの高さができるだけ等しくなっている二分木。
この状態だと、二分探索木の探索効率が最も良くなる。

平衡二分探索木の作り方

1. 配列の先頭を開始位置、末尾を終了位置と設定する（配列全体を範囲とする場合）。
2. 部分木を作成する関数へ「配列、開始位置、終了位置」という引数を渡す。
3. 配列の中央の値を二分探索木のルートノードに設定する。
4. 部分木を作成する関数へ「配列、開始位置、終了位置 -1」という引数を渡し、再帰的に左の部分木を作る。
5. 部分木を作成する関数へ「配列、中央（開始位置） +1、終了位置」という引数を渡し、再帰的に右の部分木を作る。
6. 配列の要素が1つになったら、それを新たなノードとしてツリーに追加する。

class BinarySearchTree{
    public int data;
    public BinarySearchTree left;
    public BinarySearchTree right;

    public BinarySearchTree(int data, BinarySearchTree left, BinarySearchTree right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class Main{
    public static BinarySearchTree 関数②(int[] arr, int start, int end) {
    
        // 配列の要素が1つになったら、それを新たなノードとしてツリーに追加する。
        if(start == end) return new BinarySearchTree(arr[start], null,null);

        // 配列の中央の値を二分探索木のルートノードに設定する。
        int mid = (int) Math.floor((start+end)/2);

        // 部分木を作成する関数へ「配列、開始位置、終了位置 -1」という引数を渡し、再帰的に左の部分木を作る。
        BinarySearchTree left = null;
        if(mid-1 >= start) left = 関数②(arr, start, mid-1);

        // 部分木を作成する関数へ「配列、中央（開始位置） +1、終了位置」という引数を渡し、再帰的に右の部分木を作る。
        BinarySearchTree right = null;
        if(mid+1 <= end) right = 関数②(arr, mid+1, end);

        // 中央の値をrootとしてreturnする。
        BinarySearchTree root = new BinarySearchTree(arr[mid], left, right);
        return root;
    }

    public static BinarySearchTree 関数①(int[] nums) {
        if(nums.length == 0) return null;

        // 配列の先頭を開始位置、末尾を終了位置と設定する。
        // 部分木を作成する関数へ「配列、開始位置、終了位置」という引数を渡す。
        return 関数②(nums, 0, nums.length-1);
    }

    public static void main(String[] args){
        BinarySearchTree res = 関数①(int型の配列);
        
    }
}

平衡二分探索木の中で探索する場合は、以下のようにして探す（探しているデータが存在するか否かの探索）。
※　上記に追加する形を想定。

    // 再帰の場合
    public static boolean 関数③(int key, BinarySearchTree array){
        // そもそも平衡二分探索木(array)がnullならfalse。
        if(array == null) return false;

        // 平衡二分探索木の中からキー（探索している値）と一致する値があればtrue。
        if(array.data == key) return true;

        // 現在のノードよりキーが小さければ左の子ノードに、大きければ右の子ノードに移って探索を続ける。
        if(array.data > key) return 関数③(key, array.left);
        else return 関数③(key, array.right);
    }

    // 反復の場合
    public static boolean 関数③(int key, BinarySearchTree array){
        BinarySearchTree iterator = array;
        while(iterator != null){
            if(iterator.data == key) return true;
            if(iterator.data > key) iterator = iterator.left;
            else iterator = iterator.right;
        }

        // iteratorがnullになっても（平衡二分探索木を全て探しても）キーが見つからない場合はfalse。
        return false;
    }
    

走査

走査とは、特定のルールに従って各ノードをみて回ることを指す。
そんな走査には、深さ優先走査と幅優先走査がある。

深さ優先走査

ノードから接続している未訪問のノードへ進み、進むことができなくなったら戻るという走査戦略。
以下のような手順をとる。

1. 初期ノードから探索を開始。
2. 現在のノードに隣接する未訪問のノードがある場合は、そのノードを訪問しそのノードを「現在のノード」とする。
3. ステップ2を繰り返す。
4. 現在のノードに隣接する未訪問のノードがない場合は、直前に訪れたノードに戻る。
5. ステップ2を繰り返す。
6. 全てのノードを訪問するか、または目的のノードが見つかった場合に探索を終了する。

迷路の解を求める場合などに有効。

幅優先走査

現在のノードと同じ階層にあるノードに対して探索を行うという走査戦略。
以下のような手順を取る。

1. 初期ノードを訪問し、訪問済みのリストやキューに追加。
2. 現在のノードに隣接する未訪問のノード全てを訪問し、それぞれを訪問済みのリストやキューに追加。
3. 全ての隣接ノードを訪問した後、キューから次のノードを取り出し、それを新たな「現在のノード」とする。
4. ステップ2を繰り返す。
5. 全てのノードを訪問するか、または目的のノードが見つかった場合に探索を終了する。

最短経路を求める場合などに有効。

深さ優先走査

深さ優先探索は可能な限り深くノードを探索する戦略だが、以下の探索順序の種類が存在する。

前順走査（pre-order traversal）

まずルートノード（N）を調査する。
次に、左の子ノード（L）を再帰的に探索する。
最後に右の子ノード（R）を再帰的に探索する。
この探索の順序は NLR と記述される。

間順走査（in-order traversal）

まず左の子ノード（L）を再帰的に探索する。
次に、ルートノード（N）を調査する。
最後に右の子ノード（R）を再帰的に探索する。
この探索の順序は LNR と記述される。

ノードの値の昇順表示などに使用される。

後順走査（post-order traversal）

まず左の子ノード（L）を再帰的に探索する。
次に、右の子ノード（R）を再帰的に探索する。
最後にルートノード（N）を調査する。
この探索の順序は LRN と記述される。

逆間順走査（reverse in-order traversal）

まず右の子ノード（R）を再帰的に探索する。
次に、ルートノード（N）を調査する。
最後に左の子ノード（L）を再帰的に探索する。
この探索の順序は RNL と記述される。

ノードの値の降順表示に使用される.

二分探索木への挿入

二分探索木への挿入は、挿入後も「左の子ノード　< 親ノード < 右の子ノード」という構成を維持する必要がある。

1. 関数Insert(root, v)という、既存のルートノード(root)と、挿入したい新しい値(v)を受け取る関数を用意。
2. 新しい値(v)を適切な位置に挿入するために、現在見ているノードの値と比較し、vがそのノードの値よりも大きければ右の子ノードへ、小さければ左の子ノードへ移動する。
3. 二分探索木を探索し、リーフノードに到達したら、そのノードはvの親ノードとなる。そしてvを、その親ノードの左または右に挿入する。
4. 親ノードが存在しない場合、v二分探索木の新しいルートノードとなる。

二分探索木からの削除

二分探索木からの削除は、挿入よりも複雑になる、
理由としては、削除するノードの位置にどのノードを置くのか決めなければならないため。さらに、その新たに置かれたノード以下の部分木も、適切に二分探索木の構造を維持しなければならないため。

二分探索木からノードを削除するアルゴリズムは、以下の5つのケースを考慮する必要がある。

その1：ツリーが空の場合、または削除対象のノードが存在しない場合

既存のツリーを返す。

その2:削除対象のノードがリーフノードの場合

そのノードを削除する。

その3:削除対象のノードが左側に子ノードを持たない場合

削除対象のノードの右側の部分木を、親ノードの部分木に置き換える。

その4:削除対象のノードが右側に子ノードを持たない場合

削除対象のノードの左側の部分木を、親ノードの部分木に置き換える。

その5:削除対象のノードが左右に子ノードを持つ場合

まず、削除対象のノード(N)の後続ノード（削除対象のノードの値よりも大き値のノードの中で、最も小さい値を持つノード）を見つける。
後続ノード(S)は、削除対象のノードの右側の部分木に必ず存在する。

5-1：後続ノードの親ノード(SP)が削除対象のノード（N）と同じ場合

後続ノード（S）が削除対象のノード（N）の直接の子である場合、後続ノード（S）をその親ノード（SP）に置き換える。
後続ノード（S）は、削除対象のノード（N）より大きい最小値であるため左部分木は常にnullとなっている。

5-2:後続ノードの親ノード(SP)が削除対象のノード（N）と異なる場合

後続ノード（S）が削除対象のノード（N）の右部分木の深部にある場合、以下の処理を行う。

まず、後続ノードの親ノード(SP)から後続ノード（S）を取り除き、その位置に後続ノード（S）の右部分木を移す。
次に、削除対象のノード（N）の位置に後続ノード（S）を置き換える。この結果、後続ノード（S）が削除対象ノード(N)の親ノード（P）の新しい子ノードとなる。
最後に、削除対象のノード（N）の左部分木を後続ノード（S）の左部分木とする。これにより、削除対象のノード（N）の左部分木が保持され、後続ノード（S）が削除対象のノード（N）の全ての子を引き継ぐ。

二分ヒープ（binary heap）

二分ヒープは、親ノードの値がその子ノードの値と等しいかそれより大きい（または小さい）という特徴を持つ。
これにより、最大ヒープ（親ノードの値が子ノードの値よりも大きい）または、最小ヒープ（親ノードの値が子ノードの値よりも小さい）が形成することができる。
兄弟ノード（同階層のノード）間での大小については制約はない。
また、二分ヒープは完全二分木の性質（全ての階層が左から右へ順に埋まっている状態）を持つため、配列として表現することも可能。

二分ヒープは完全二分木であることから、配列のインデックスをiとすると以下の規則を見出せる。

- i番目のノードの左の子ノード: left(i) = 2i + 1
- i番目のノードの右の子ノード: right(i) = 2i + 2
- i番目のノードの親ノード: parent(i) = floor((i-1) / 2)

[7,11,16,20,28,39,22,45,32,41] という配列があった場合、以下となることがわかる。

0番目のノードの左の子ノード: left(0) = 1 → arr[1]は11でarr[0]の左の子ノード
0番目のノードの右の子ノード: right(0) = 2 → arr[2]は16でarr[0]の右の子ノード

4番目のノードの左の子ノード: left(4) = 9 → arr[9]は41でarr[4]の左の子ノード
4番目のノードの右の子ノード: right(4) = 10 → arr[10]は存在しないのでarr[4]の右の子ノードは存在しない
4番目のノードの親ノード: parent(4) = 1 →　arr[1]は11でarr[４]の親ノード

Max-Heapify

Max-Heapify関数は、最大ヒープというデータ構造を維持するための関数。あるノードとその子ノードが最大ヒープのルールを守るよう、必要に応じてノード間のデータを入れ替える処理を行う。

次のようなステップで進められます。

1. ある特定のノード（i）を起点にし、そのノード(i)が、自分自身とその子ノードの中で最大の値であることを確認する。
2. ノード(i)が最大の値を持つ場合は、処理を終了する。
3. ノード(i)が子ノードよりも小さい値を持つ場合は、そのノード(i)と最大の値を持つ子ノードを交換する（スワップ)。
4. スワップによって移動した子ノードに対して、再度Max-Heapify関数を適用する。つまり、その子ノードが新しい場所で最大値を持つことを確認し、必要であればさらにスワップする。
5. すべてのノードが最大ヒープのルールを守るようになるまで繰り返す。

上記は特定のノードに対して最大ヒープの特徴を持たせることはできるが、配列全体に対して最大ヒープの特徴を持たせることはできない。
配列全体に対して最大ヒープの特徴を持たせるためには、配列の中央からスタートし、配列の先頭（ルートノード）に向かって maxHeapify関数を各ノードに適用することが必要となる。

配列の中央からスタートする理由としては、ヒープは完全二分木であるがゆえに、配列で表現した場合その半分以上はリーフノードとなる。リーフノードには子ノードが存在しないため、リーフノードは「親ノードが子ノードより大きい」というヒープの条件を満たすことが保証される。

配列全体に対する最大ヒープの実装例。

import java.util.Arrays;
import java.util.ArrayList;

class Heap{
    // 配列i番目の左の子ノードの要素番号を返す
    public static int left(int i){
        return 2*i + 1;
    }

    // 配列i番目の右の子ノードの要素番号を返す
    public static int right(int i){
        return 2*i + 2;
    }

    // 配列i番目の親ノードの要素番号を返す
    public static int parent(int i){
        return (int)Math.floor((i-1)/2);
    }

    // maxHeapify関数
    public static void maxHeapify(ArrayList<Integer> arr, int i){
        
        int l = Heap.left(i);
        int r = Heap.right(i);

        // 現在の要素番号を最大と仮定
        int biggest = i;

        // 配列の中に要素番号lが存在する　且つ　要素番号lの値がbiggestの値よりも大きい場合はbiggestを更新
        if(l < arr.size() && arr.get(l) > arr.get(biggest)) biggest = l;
        // 配列の中に要素番号rが存在する　且つ　要素番号rの値がbiggestの値よりも大きい場合はbiggestを更新
        if(r < arr.size() && arr.get(r) > arr.get(biggest)) biggest = r;

        // biggestの値が更新されていた場合
        if(biggest != i ){
            // 要素番号i番目の値と、biggestの値を入れ替える
            int temp = arr.get(i);
            arr.set(i, arr.get(biggest));
            arr.set(biggest, temp);
            // 入れ替えたノードの位置が正しいか、maxHeapifyを呼び出して確認
            Heap.maxHeapify(arr, biggest);
        }
    }
    
    public static void buildMaxHeap(ArrayList<Integer> arr){
        int middle = Heap.parent(arr.size()-1);
        // 配列の中央からルートノードまでmaxHeapify関数を適用する
        for(int i = middle; i >=0; i--){
            Heap.maxHeapify(arr,i);
        }    
    } 
}

class Main{
    public static void main(String[] args){

        ArrayList<Integer> heap = new ArrayList<>(Arrays.asList(new Integer[]{7,11,39,16,20,28,22,45,32,41}));
        System.out.println(heap); // → [7, 11, 39, 16, 20, 28, 22, 45, 32, 41]
        Heap.buildMaxHeap(heap);
        System.out.println(heap); // → [45, 41, 39, 32, 20, 28, 22, 16, 11, 7]
    }
}

ヒープソート

ヒープソートは、二分ヒープのデータ構造を用いてデータのソートを行うアルゴリズム。

1. 与えられたデータから最大ヒープを作成する。
2. ヒープから最大値（ルートノード）を取り出し、最後のリーフノードと交換する。
3. ヒープとして考慮する範囲から最大値を除く。
4. ここまでの結果ヒープの性質が崩れている可能性があるため、maxHeapify関数を呼び出し、再び最大ヒープを作成する。
5. これらの手順をヒープのサイズが1になるまで繰り返す（配列全体がソートされたということ）。

例：[2, 10, 8, 5, 1]という配列の場合。

最初の最大ヒープ: [10, 8, 5, 2, 1]
1回目: [8, 5, 2, 1] と 10
２回目: [5, 2, 1] と 8, 10
3回目: [2, 1] と 5, 8, 10
4回目: [1] と 2, 5, 8, 10
5回目: [] と 1, 2, 5, 8, 10

ヒープソートの実装例

import java.util.Arrays;
import java.util.ArrayList;

class Heap{
    public static int left(int i){
        return 2*i + 1;
    }

    public static int right(int i){
        return 2*i + 2;
    }

    public static int parent(int i){
        return (int)Math.floor((i-1)/2);
    }

    public static void maxHeapify(ArrayList<Integer> arr, int end, int i){
        
        int l = Heap.left(i);
        int r = Heap.right(i);

        int biggest = i;

        if(l <= end && arr.get(l) > arr.get(biggest)) biggest = l;
        if(r <= end && arr.get(r) > arr.get(biggest)) biggest = r;

        if(biggest != i ){
            int temp = arr.get(i);
            arr.set(i, arr.get(biggest));
            arr.set(biggest, temp);
            Heap.maxHeapify(arr, end, biggest);
        }
    }
    
    public static void buildMaxHeap(ArrayList<Integer> arr){
        int middle = Heap.parent(arr.size()-1);
        for(int i = middle; i >=0; i--){
            Heap.maxHeapify(arr, arr.size()-1, i);
        }    
    } 

    public static void heapSort(ArrayList<Integer> arr){
        // arrを最大ヒープに
        Heap.buildMaxHeap(arr);

        int end = arr.size() - 1;
        while(end > 0){
            //  ヒープの最大ノードと最後のリーフノードを入れ替える
            int temp = arr.get(end);
            arr.set(end, arr.get(0));
            arr.set(0, temp);

            //　ヒープとして考慮する範囲から最大値を除く
            end--;
            Heap.maxHeapify(arr, end, 0);
        }
    }
}

class Main{
    public static void main(String[] args){

        ArrayList<Integer> heap = new ArrayList<>(Arrays.asList(new Integer[]{7,11,39,16,20,28,22,45,32,41}));
        System.out.println(heap); // → [7, 11, 39, 16, 20, 28, 22, 45, 32, 41]
        Heap.buildMaxHeap(heap);
        System.out.println(heap); // → [45, 41, 39, 32, 20, 28, 22, 16, 11, 7]
    }
}

優先度付きキュー（priority queue）

優先度付きキューとは、要素が優先度順に格納されるキューのことを指す。

具体的な操作としては、以下などが挙げられる。

• top(): 最も高い優先度を持つ要素を取得する。
• insert(x): 要素xを優先度に基づいて適切な位置に挿入する。
• pop(): 最も高い優先度を持つ要素をキューから取り除き、その要素を返す。

ヒープは特定の順序でデータを効率的に管理するデータ構造のため、優先度付きキューの実装に使用される。

優先度付きキューの実装例

import java.util.Arrays;
import java.util.ArrayList;

class Heap{
    
    public static void buildMaxHeap(ArrayList<Integer> arr){
        int middle = Heap.parent(arr.size()-1);
        for(int i = middle; i >=0; i--){
            Heap.maxHeapify(arr, arr.size()-1, i);
        }    
    } 

    public static void maxHeapify(ArrayList<Integer> arr, int end, int i){
        
        int l = Heap.left(i);
        int r = Heap.right(i);

        int biggest = i;
        if(l <= end && arr.get(l) > arr.get(biggest)) biggest = l;
        if(r <= end && arr.get(r) > arr.get(biggest)) biggest = r;

        if(biggest != i ){
            int temp = arr.get(i);
            arr.set(i, arr.get(biggest));
            arr.set(biggest, temp);
            Heap.maxHeapify(arr, end, biggest);
        }
    }

    public static int left(int i){
        return 2*i + 1;
    }

    public static int right(int i){
        return 2*i + 2;
    }

    public static int parent(int i){
        return (int)Math.floor((i-1)/2);
    }
}

// 優先度付きキュー
class PriorityQueue{
    public ArrayList<Integer> maxHeap;

    public PriorityQueue(ArrayList<Integer> arr){

        this.maxHeap = new ArrayList<Integer>();
        for(Integer i: arr) this.maxHeap.add(i);
        Heap.buildMaxHeap(this.maxHeap);
    }

    public int top(){
        // maxHeapの先頭要素を返す
        return this.maxHeap.get(0);
    }

    public int pop(){
        // maxHeapのルートノードの値を変数へ格納
        Integer temp = this.maxHeap.get(0);
        // maxHeapの最後の要素の値をルートノードに設定
        this.maxHeap.set(0, this.maxHeap.get(this.maxHeap.size()-1));
        // maxHeapの最後の要素を削除
        this.maxHeap.remove(this.maxHeap.size()-1);
        // 最大ヒープを構築
        Heap.maxHeapify(this.maxHeap, this.maxHeap.size()-1, 0);
        // 最初に格納しておいたルートノードの値を返す
        return temp;
    }

    public void insert(int x){
        // 新しい要素をmaxHeapの最後に追加
        this.maxHeap.add(x);
        // 新しく追加した要素(x)のインデックスを取得
        int i = this.maxHeap.size()-1;
        // 新しく追加した要素(x)の親のインデックスを取得
        int parent = Heap.parent(i);
        // 新しく追加した要素(x)を適切な位置に配置
        while(parent >= 0 && this.maxHeap.get(parent) < x){
            Integer temp = this.maxHeap.get(i);
            this.maxHeap.set(i, this.maxHeap.get(parent));
            this.maxHeap.set(parent, temp);
            i = parent;
            parent = Heap.parent(i);
        }    
    }  
}

class Main{
    public static void main(String[] args){
        ArrayList<Integer> heap = new ArrayList<>(Arrays.asList(new Integer[]{7,11,39,16,20,28,22,45,32,41}));
        System.out.println(heap); // → [7, 11, 39, 16, 20, 28, 22, 45, 32, 41]
        PriorityQueue pq = new PriorityQueue(heap);
        System.out.println(pq.maxHeap); // → [45, 41, 39, 32, 20, 28, 22, 16, 11, 7]
        pq.insert(3);
        System.out.println(pq.maxHeap); // → [45, 41, 39, 32, 20, 28, 22, 16, 11, 7, 3]
        pq.insert(60);
        System.out.println(pq.maxHeap); // → [60, 41, 45, 32, 20, 39, 22, 16, 11, 7, 3, 28]
        System.out.println(pq.pop()); // → 60
        System.out.println(pq.maxHeap); // → [45, 41, 39, 32, 20, 28, 22, 16, 11, 7, 3]
    }
}

最後に

以前DB設計をした際にインデックスのことを考えるためにB-treeのことを少し調べましたが、今ならもう少し理解できたりするのかな、、？と思いました（全然そんなことはないかもしれないけど）。