TIL - Day5

트리

트리 알아보기

• 몇 가지 제약이 있는 방향그래프의 일종
• 하나의 루트(최상위 부모)에서 하위로 뻗어나가는 구조이다.
• 각 정점은(Node), 자식이 없는 정점(Leaf Node)
• 레벨은 Root로부터 몇 번째 깊이인지
• 한 정점에서 뻗어나가는 간선의 수는 차수(Degree) - 자식 수
  

트리의 특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N-1개의 간선 수를 가진다.
• 루트에서 특정 정점으로 가는 경로는 유일해야한다.

이진트리(탐색 알고리즘)

• 각 정점이 최대 2개의 자식을 가지는 트리
  

이진트리의 특징

• 정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 수 있다. (편향트리)
• 정점인 N개인 포화/완전 이진트리의 높이는 logN
  • 레벨이 증가하면 2개씩 정점이 생기기 때문
• 높이가 n인 포화 이진트리는 2ⁿ- 1개의 정점을 가진다.
• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등에 자주 사용된다.

트리의 구현 방법

• 그래프와 마찬가지로 인접 행렬, 인접 리스트로 구현 가능하다.

이진트리의 구현 방법

• 배열이나 요소에 링크가 2개 존재하는 연결 리스트로 구현 가능하다.

left = Index * 2;
right = Index * 2 + 1;
Parent = Math.floor(Index / 2);

• Linked List로 구현

class Node{
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class Tree{
    constructor(node){
        this.root = node;
    }

    display(){
        const queue = new Queue();
        queue.enqueue(this.root);
        while(queue.size){
            const currentNode = queue.dequeue();
            console.log(currentNode.value);
            if(currentNode.left) queue.enqueue(currentNode.left);
            if(currentNode.right) queue.enqueue(currentNode.right);
        }
    }
}

const tree = new Tree(new Node(9));

tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4); 

• 트리를 탐색하는 방법인 전위 순회, 중위 순회, 후위 순회를 구현해보자!
  • BFS 너비 우선 탐색
• 전위 순회는 [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회
• 중위 순회는 [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회
• 후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회

class Queue{
  constructor(){
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value){
    this.queue[this.rear++] = value; //rear 영역에 값을 넣고 rear인덱스를 하나 증가
  }

  dequeue(){
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front++;
    return value;
  }

  peek(){ //큐의 가장 앞에 있는 값 알아내기
    return this.queue[this.front];
  }

  size(){ //큐의 길이는 끝 - 처음
    return this.rear - this.front;
  }
}

const q = new Queue();

class Node{
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class Tree{
    constructor(node){
        this.root = node;
    }

    display(){
        const queue = new Queue();
        queue.enqueue(this.root);
        while(queue.size){
            const currentNode = queue.dequeue();
            console.log(currentNode.value);
            if(currentNode.left) queue.enqueue(currentNode.left);
            if(currentNode.right) queue.enqueue(currentNode.right);
        }
    }
  
  	BFS(){ // 너비 우선 탐색 [ 10, 6, 15, 3, 8, 20 ]
        const result = [];
        const q = new Queue();
        q.enqueue(this.root);
        console.log(this.root.value);
        while(q.front !== q.rear){
            const cur = q.dequeue();
            result.push(cur.value);

            if(cur.left) q.enqueue(cur.left);
            if(cur.right) q.enqueue(cur.right);
        }
        return result;
    }

    DFSPreOrder(){ // 전위순회 [ 10, 6, 3, 8, 15, 20 ]
        const result = [];
        function PreOrder(node){
            result.push(node.value);
            if(node.left) PreOrder(node.left);
            if(node.right) PreOrder(node.right);
        }
        PreOrder(this.root);
        return result;
    }

    DFSInOrder(){ // 중위순회 [ 3, 6, 8, 10, 15, 20 ]
        const result = [];
        function InOrder(node){
            if(node.left) InOrder(node.left);
            result.push(node.value);
            if(node.right) InOrder(node.right);
        }
        InOrder(this.root);
        return result;
    }

    DFSPostOrder(){ // 후위순회 [ 3, 8, 6, 20, 15, 10 ]
        const result = [];
        function PostOrder(node){
            if(node.left) PostOrder(node.left);
            if(node.right) PostOrder(node.right);
            result.push(node.value);
        }
        PostOrder(this.root);
        return result;
    }
}

const tree = new Tree(new Node(10));

tree.root.left = new Node(6);
tree.root.right = new Node(15);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(8);
tree.root.right.right = new Node(20);  

힙

힙 알아보기

우선순위 큐

• 우선순위가 높은 요소가 먼저 나가는 큐 (자료구조x 개념)
• 힙은 우선순위 큐를 구현하기위한 가장 적합한 방법이다.

힙이란?

• 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.
• 우선순위 큐 != 힙

힙의 특징

• 우선순위가 높은 요소를 Root로 배치 -> 가장 먼저 나감
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)
• 루트가 가장 작은 값이 되는 최소 힙(Min Heap)

힙 요소 추가 알고리즘

• 요소 추가 시 트리의 가장 마지막 정점에 추가한다.
• 추가 후 부모 정점보다 우선순위가 높은지 확인하고 높다면 바꾼다.
• 순서를 바꿀 수 없을때까지 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
• 힙(완전 이진 트리임) 높이는 logN이기 때문에 힙의 요소 추가 알고리즘은 O(logN)의 시간복잡도

힙 요소 삭제 알고리즘

• 요소 삭제는 루트 정점만 가능하다.
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
• 루트 정점의 두 자식 중 더 우선순위가 높은 정점과 위치를 바꾼다.
• 두 자식 정점이 우선순위가 낮아질 때 까지 반복한다.
• 힙(완전 이진 트리임) 높이는 logN이기 때문에 힙 요소 삭제 알고리즘은 O(logN)의 시간복잡도

class MaxHeap{
    constructor() {
        this.heap = [null];
    }

    push(value){
        this.heap.push(value);
        let currentIndex = this.heap.length - 1 // 현재 인덱스는 힙 길이 - 1
        let parentIndex = Math.floor(currentIndex / 2);

        while(parentIndex !== 0 && this.heap[parentIndex] < value){
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value; // 부모 위치와 추가된 요소의 인덱스와의 교환
            this.heap[currentIndex] = temp;

            // 위 작업을 반복하기 위한 로직
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }

    pop(){
        const returnValue = this.heap[1]; //Root 정점 제거하기 위해
        this.heap[1] = this.heap.pop(); //마지막 요소로 루트를 채워줌

        //루트로부터 아래로 내려가면서 비교하기 위한 변수들
        let currentIndex = 1;
        let leftIndex = 2;
        let rightIndex = 3;

        while(this.heap[currentIndex] < this.heap[leftIndex] ||
              this.heap[currentIndex] < this.heap[rightIndex]){

                if(this.heap[leftIndex] < this.heap[rightIndex]){ //왼쪽보다 오른쪽이 클 경우
                    const temp = this.heap[currentIndex];
                    this.heap[currentIndex] = this.heap[rightIndex];
                    this.heap[rightIndex] = temp;
                    currentIndex = rightIndex;
                }
                else{
                    const temp = this.heap[currentIndex];
                    this.heap[currentIndex] = this.heap[leftIndex];
                    this.heap[leftIndex] = temp;
                    currentIndex = leftIndex; //바뀐 후 그 밑의 자식들을 탐색하기 위해
                }
                leftIndex = currentIndex * 2;
                rightIndex = currentIndex * 2 + 1;
              }

              return returnValue;
    }
}

const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(100);
heap.push(57);
heap.push(27);
heap.push(39);
heap.push(66);

console.log(heap.pop()); //100
console.log(heap.heap); // [ null, 66, 57, 45, 36, 27, 39]

최소 힙

• 비교 조건만 바꿔줬더니 손쉽게 최소 힙을 구현할 수 있었다!!

class MinHeap{
    constructor() {
        this.heap = [null];
    }

    push(value){
        this.heap.push(value);
        let currentIndex = this.heap.length - 1 // 현재 인덱스는 힙 길이 - 1
        let parentIndex = Math.floor(currentIndex / 2);

        while(parentIndex !== 0 && this.heap[parentIndex] > value){
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value; // 부모 위치와 추가된 요소의 인덱스와의 교환
            this.heap[currentIndex] = temp;

            // 위 작업을 반복하기 위한 로직
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }

    pop(){
        const returnValue = this.heap[1]; //Root 정점 제거하기 위해
        this.heap[1] = this.heap.pop(); //마지막 요소로 루트를 채워줌

        //루트로부터 아래로 내려가면서 비교하기 위한 변수들
        let currentIndex = 1;
        let leftIndex = 2;
        let rightIndex = 3;

        while(this.heap[currentIndex] > this.heap[leftIndex] ||
              this.heap[currentIndex] > this.heap[rightIndex]){

                if(this.heap[leftIndex] > this.heap[rightIndex]){ //왼쪽보다 오른쪽이 클 경우
                    const temp = this.heap[currentIndex];
                    this.heap[currentIndex] = this.heap[rightIndex];
                    this.heap[rightIndex] = temp;
                    currentIndex = rightIndex;
                }
                else{
                    const temp = this.heap[currentIndex];
                    this.heap[currentIndex] = this.heap[leftIndex];
                    this.heap[leftIndex] = temp;
                    currentIndex = leftIndex; //바뀐 후 그 밑의 자식들을 탐색하기 위해
                }
                leftIndex = currentIndex * 2;
                rightIndex = currentIndex * 2 + 1;
              }

              return returnValue;
    }
}

const heap = new MinHeap();
heap.push(45);
heap.push(36);
heap.push(100);
heap.push(57);
heap.push(27);
heap.push(39);
heap.push(66);

console.log(heap.pop()); // 27
console.log(heap.heap); // [null, 36, 45, 39, 57, 66, 100]

Trie - 트리를 이용한 자료구조

구글이나 네이버 등에서 검색 시 자동완성을 하려면 어떻게 해야할까?

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 간선은 이전 정점으로 새롭게 추가된 문자 정보를 가지고 있다.
• 정점은 이전 정점으로부터 더해진 문자 정보를 가지고 있다.
  

트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 응용
• 문자열을 탐색할 때 효율적으로 찾을 수 있다.
• N이 문자열 길이라면 탐색, 삽입은 O(N)이 소요된다.
• 각 정점이 자식에 대한 링크를 모두 가지고 있기에 저장 공간을 더 많이 사용한다.

트라이의 구조

• 루트는 비어있다.
• 각 간선(링크)은 추가될 문자를 키로 가진다.
• 각 정점의 값은 이전 정점의 값 + 간선의 키
• 해시 테이블과 연결 리스트를 이용하여 구현한다.

class Queue{
    constructor(){
        this.queue = [];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    enqueue(value){ // 데이터 삽입
        this.queue[this.rear++] = value; // rear영역에 값을 넣고 rear 인덱스를 하나 증가
        this.size++;
    }

    dequeue(){ // front에서 데이터 삭제
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front++;
        this.size--;
        return value;
    }

    peek(){ // 큐의 맨 앞에 값 알아내기
        return this.queue[this.front];
    }
}


class Node{
    constructor(value = ' '){
        this.value = value;
        this.children = new Map(); // 키로 사용할 간선 정보, 이전 정점의 값 정보를 위해 맵 객체로 저장
        this.isWordsFlag = false;
    }
}

class Trie{
    constructor(){
        this.root = new Node(); //root는 공백
    }

    insert(string){
        let currentNode = this.root;

        for(const char of string){
            if(!currentNode.children.has(char)){ // 자른 문자열을 키(간선) 으로 가지고 있지 않다면
                currentNode.children.set(
                    char,
                    new Node(currentNode.value + char) // cat이 있는 상태에 can을 추가한다면 c,a가 있다는 걸 확인 후 n만 추가한 정점 생성
                )
            }
            currentNode = currentNode.children.get(char);
        }

        currentNode.isWordsFlag = true;
    }

    search(string){  // 단어가 있는지 조회
        let currentNode = this.root;

        for(const char of string){
            if(!currentNode.children.has(char)){
                return undefined;
            }
            currentNode = currentNode.children.get(char);
        }
        console.log(currentNode);
        return currentNode;
    }

    has(string){
        return this.search(string) ? true : false;
    }

    autoWord(answer){
    
        const currentNode = this.search(answer);
        
        if(currentNode === undefined){
            return "해당 단어가 없습니다.";
        }
        
        const words = [];
        const q = new Queue();
        q.enqueue(currentNode);
        
        while(q.size){
            let current = q.dequeue();

            if(current.isWordsFlag){ // 삽입된 문자들을 정확히 기억해주는 변수
                words.push(current.value);
            }

            for(const item of current.children.values()){
                q.enqueue(item);
            }
        }
        return words;
    }
}


const trie = new Trie();

trie.insert("cat");
trie.insert("can");
trie.insert("car");
trie.insert("cart");
trie.insert("cannn");

console.log(trie.autoWord("car")); //[ ' car', ' cart' ]

자동 완성 코드 구현 (레벨 순회 응용?)

autoWord(answer){
    
        const currentNode = this.search(answer);
        
        if(currentNode === undefined){
            return "해당 단어가 없습니다.";
        }
        
        const words = [];
        const q = new Queue();
        q.enqueue(currentNode);
        
        while(q.size){
            let current = q.dequeue();

            if(current.isWordsFlag){ // 있어야만 모든 간선과 이전 정점 정보가 함께 나오지 않는다.
                words.push(current.value);
            }

            for(const item of current.children.values()){
                q.enqueue(item);
            }
        }
        return words;
    }

정렬

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.

버블정렬(비교식)

• 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 (오름차순 비슷)
• 각 순회마다 마지막 인덱스에 가장 큰 요소가 정렬된다.
• 즉, n-1번 순회하면 정렬이 마무리된다.
• O(n²) 시간복잡도

선택정렬(비교식)

• 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 알고리즘
• 각 순회마다 맨 앞에 우선순위가 높은 요소가 정렬됨
• O(n²) 시간복잡도

삽입정렬(비교식)

• 선택된 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 알고리즘
• 삽입정렬은 두번째 요소부터 시작한다.
• 어느정도 정렬이 되어있는 상태에선 퀵 정렬보다 빠르다.
• O(n²) 시간복잡도

분산 정렬

✔ 분할 정복

• 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략

합병정렬

• 최선과 최악이 같은 안정적인 알고리즘
• O(n log n) 시간복잡도

퀵 정렬

• 매우 빠르지만 최악O(n²) 의 경우가 존재하는 불안정 정렬
• O(n log n) 시간복잡도

이진 탐색

• 정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
• O(log n) 시간복잡도
  • Ex) 1~50 까지 숫자 중 하나 맞추기

이진 탐색의 특징

• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열이나 이진 트리로 구현할 수 있다.

이진 탐색 트리

• 이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값, 오른쪽 서브 트리는 부모보다 큰 값

요소 삭제

• 단말 정점을 삭제한다면?
  • 별다른 처리 필요x 부모 정점과 연결을 끊으면 자동으로 삭제
• 하나의 서브 트리를 가지고 있다면?
  • 제거되는 정점의 부모 간선을 자식 정점을 가르키도록 한다.
• 두 개의 서브 트리를 가지고 있다면?
  • 왼쪽 서브 트리의 가장 큰 값 or 오른쪽 서브 트리의 가장 작은 값과 교체

이진 탐색 트리의 문제점

• 최악의 경우 한쪽으로 편향된 편향 트리가 될 수 있다.
• 이럴 경우 순차 탐색과 같은 시간 복잡도를 갖게 된다.
  • 해결법 ? AVL 트리, 레드-블랙 트리

배열로의 구현법

const Array = [1,1,5,124,400,600,1000,2345,6789];

function binarySearch(array, findValue){
    let left = 0;
    let right = Array.length - 1;
    let mid = Math.floor((left + right) / 2);

    while(left < right){
        if(Array[mid] === findValue){
            return mid;
        }

        if(Array[mid] > findValue){ //가운데보다 찾는 숫자가 작다면 -> 왼쪽 진행
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
        mid = Math.floor((left + right) / 2);
    }

    return -1; // 찾는 값이 배열에 존재하지 않을 경우
}