[Front-end🦁] #35アルゴリズム/バイナリツリー

1.クイズ

解題はすべて解題できる問題なので、緒論を説明するときにPythonで素早く解題し、説明を聞きながらJavaScriptの参考点、あるいは私の論理で修正が必要な点をチェックします.

1.秘密地図

正規表現が初めて出たときの問題なので、直接正規表現でアクセスできます.本当は正規式を書きたいならいくつかしか覚えていません正規のモジュール関数を覚えていません.Python reドキュメント、Apple regexドキュメントを精読する必要があります
秘密の地図

2.ダーツゲーム

ダーツゲームたまたま...先週は勉強問題でした先週は忙しくて昨日解けませんでした!これは問題です.先生の解答は私のと少し違いますが、基本的な論理は同じです.
ダーツゲーム

3.キャッシュ

ケイシーはLRUを利用した問題だが、サイズ0のテストボックスを漏らした.問題を細かく分解しすぎて、重複するコードがたくさんあることに気づき、最後に圧縮しました.
キャッシュ

2.バイナリツリー

class Node {
    constructor(data){
        this.data = data;
        // this.child = []; // 2진트리가 아닌 트리가 됨
        this.left = null;
        this.right = null;
    }
}

class Tree {
    constructor(data) {
        let init = new Node(data);
        this.root = init;
        this.데이터수 = 0;
    }

    length(){
        return this.데이터수;
    }

    insert(data){
        let 새로운노드 = new Node(data);
        let 순회용현재노드 = this.root;

        while(순회용현재노드){
            if (data === 순회용현재노드.data){
                // 중복된 값은 탈락!
                return;
            }
            if (data < 순회용현재노드.data){
                // 들어온 데이터가 작으면 왼쪽
                // 비어있으면 데이터를 넣고, 비어있지 않으면 타고 또 내려가야합니다.
                if (!순회용현재노드.left){
                    순회용현재노드.left = 새로운노드;
                    return;
                }
                순회용현재노드 = 순회용현재노드.left;
            }
            if (data > 순회용현재노드.data){
                if (!순회용현재노드.right){
                    순회용현재노드.right = 새로운노드;
                    return;
                }
                순회용현재노드 = 순회용현재노드.right;
            }
        }
        this.데이터수 += 1;
    }

    DFS(){
        // 깊이우선탐색, DFS(Depth First Search)
        // Stack 이용!
        let 결과값 = [];
        let 스택 = [this.root];
        
        while(스택.length !== 0){
            let current = 스택.pop();
            if (current.right) {
                스택.push(current.right);
            }
            if (current.left) {
                스택.push(current.left);
            }
            결과값.push(current.data);
        }
        return 결과값;
    }

    BFS(){
        // BFS는 DFS의 스택을 큐로만 바꾸어주면 된다.
        // .pop() 대신 .shift()
    }
}

+赤黒ツリー:不均等なバイナリツリーが発生して検索効率が低下する場合を解決するツリー.

本も子供も黒い!

赤の子供はみな黒でなければなりません.

黒で、子供がどんな色でもいいです.

BFSによって新しいノードの位置が決定される.(バイナリツリー、左から右)