TIL6 - 2023.09.26

 

트리 (Tree)

• 방향 그래프의 일종으로 하나의 루트에서 하위로 뻗어나가는 구조를 가지고 있다
• 루트(Root) : 가장 상위에 존재하는 정점
• 노드(Node) : 각 정점
• 리프 노드(Leaf Node) : 자식이 없는 노드
• 레벨(Level) : 루트로부터 몇 번의 깊이
• 차수(Degree) : 한 정점에서 뻗어나가는 정점의 수
• 인접 행렬, 인접 리스트로 구현 가능
• ex) 부서, 디렉토리 구조

트리의 특징

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

 

이진 트리

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

이진 트리의 특징

• 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다 ➜ N개의 정점을 가진 편향 트리
• 정점이 N개인 포화 또는 완전 이진 트리의 높이는 logN이다
• 높이가 h인 포화 이진 트리는 2^h - 1개의 정점을 가진다
• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리

이진 트리 구현

• 배열

// 0번 인덱스는 관리를 위해 비워둔다.
// Left = Index * 2
// Right = Index * 2 + 1
// Parent = floor(Index / 2)
const tree = [
    undefined,
    // 1
    9,
    // 1+2, 1+2+1
    3, 8,
    // 2+2, 2+2+1, 3+2, 3+2+1
    2, 5, undefined, 7,
    // 4+2, 4+2+1, 5+2, 5+2+1
    undefined, undefined, undefined, 4
]

• 연결 리스트

class Node {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }
  
  class Tree {
    contructor(node) {
      this.root = node;
    }
    
    display() {
      // Level Order
      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);

과제

전위 / 중위 / 후위 순회 (스택) 검색하여 직접 구현

---

힙(Heap)

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

힙의 특징

• 우선 순위가 높은 요소를 루트(Root)로 배치하고 루트가 먼저 나가는 특징을 가진다
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다(오름차순, 내림차순의 차이)
• 아쉽게도 자바스크립트에서 직접 구현해야 한다

힙 요소 추가 알고리즘

• 요소가 추가될 때는 이진 트리의 가장 마지막에 추가한다
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다
• 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다
• 요소는 항상 이진 트리의 마지막에 추가되기 때문에 힙은 항상 완전 이진 트리이다
• 높이가 log N이기 때문에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가진다

 

힙 요소 제거 알고리즘

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

힙 추가 & 제거 코드 구현

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

    push(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 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];
        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); // 63
heap.push(36); // 54
heap.push(54); // 45
heap.push(27); // 36
heap.push(63); // 27
console.log(heap.heap); // [ null, 63, 54, 45, 27, 36 ]
heap.pop();
heap.pop();
console.log(heap.heap); // [ null, 45, 36, 27 ]

과제 : 최소 힙 구현

우선순위 큐

• FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐
• 우선순위 큐는 자료구조가 아닌 개념이다

---

트라이 (Trie)

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있다
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다
• 보통 문자열을 탐색할 때 (문자열의 갯수 X 문자열의 길이)만큼 시간이 걸리지만 트라이는  L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다는 단점이 있다

트라이 구조

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

트라이 코드 구현

class Node {
  constructor(value ='') {
    this.value = value;
    this.children = new Map();
  }
}
// Node {value: '', children: Map(0)}

class Trie {
  constructor() {
    this.root = new Node();
  }
  
  insert(string) { // string = 'cat'
    let currentNode = this.root; // root부터 탐색을 시작한다.
    
    for (const char of string) { // 문자열을 맨 앞부터 문자 하나씩 순회한다. char = 'c'
      if (!currentNode.children.has(char)) { // 현재 노드가 'c'를 간선으로 가지고 있지 않다면,
        currentNode.children.set(char, new Node(currentNode.value + char)); // 새롭게 노드를 추가한다.
        // Node {value:'', children: Map(1) {'c' => Node}}
      }
      
      currentNode = currentNode.children.get(char); // 그러고나서 char 노드로 이동한다.
      // 'c' 간선이 이어진 노드로 이동
      // Node {value: 'c', children: Map(0)}
    }
  }
  
  has(string) {
    let currentNode = this.root;

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

    return true;
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('can');
console.log(trie.has('cat')); // true
console.log(trie.has('can')); // true
console.log(trie.has('cap')); // false

---

정렬 (Sort)

• 요소들을 일정한 순서대로 열거하는 알고리즘

정렬의 특징

• 정렬 기준은 사용자가 정할 수 있다 ( 오름차순 / 내림차순 )
• 크게 비교식과 분산식 정렬로 나눌 수 있다
• 대부분의 언어가 빌트인으로 제공해준다
• 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재

 

어떤 정렬이 제일 빠를까??

 

비교식 정렬

버블 정렬

• 서로 인정합 두 요소를 검사하여 정렬하는 알고리즘
• O(N²) 시간 복잡도를 가진다

선택 정렬

• 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘
• O(N²) 시간 복잡도를 가진다

삽입 정렬

• 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘
• O(N²) 시간 복잡도를 가진다

분산식 정렬

분할 정복

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

합병 정렬

• 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘
• O(NlogN) 시간 복잡도를 가진다

퀵 정렬

• 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬
• O(NlogN) 시간 복잡도를 가진다
• 맨 오른쪽 또는 맨 왼쪽에 피벗(pivot)을 두고 정렬을 진행한다

---

이진 탐색 (Binary Search)

• 정렬 되어 있는 요소들을 반씩 제외하며 찾는 알고리즘
• O(logN) 시간 복잡도를 가진다

이진 탐색의 특징

• 반드시 정렬이 되어있어야 사용할 수 있다
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다
• O(logN) 시간복잡도인만큼 상당히 빠르다

배열을 이용한 이진 탐색 ( 45를 찾아라 )

이진 탐색 트리

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

이진 탐색 요소 추가

 

이진 탐색 요소 제거

 

1. 단말 정점을 삭제하는 경우

• 별다른 처리 없이 부모 정점과의 연결을 끊으면 된다

2. 하나의 서브 트리를 가지는 경우

• 제거되는 정점의 부모 간선을 자식 정점을 가르키게 바꾸면 된다

 

3. 두 개의 서브 트리를 가지는 경우

• 왼쪽 서브 트리의 가장 큰 값 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 된다
• 이 경우 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체된다

이진 탐색 트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다
• 그런 경우 순차 탐색과 동일한 시간복잡도를 가진다
• AVL 트리, 레드 - 블랙 트리를 이용하면 이진 탐색 트리의 균형을 맞춰줄 수 있다

이진 탐색 구현

const array = [1, 1, 5, 134, 400, 599, 1004, 2876, 8712];
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)
            left = mid + 1;
        else
            right = mid - 1;

        mid = Math.floor((left + right) / 2);
    }
    return -1;
}

이진 탐색 트리 구현

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

    insert(value) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }

        let currentNode = this.root;
        while (currentNode !== null) {
            if (currentNode.value < value) {
                if (currentNode.right === null) {
                    currentNode.right = new Node;
                    break;
                }
                currentNode = currentNode.right;
            } else {
                if (currentNode.left === null) {
                    currentNode.left = newNode;
                    break;
                }
                currentNode = currentNode.left;
            }
        }
    }
    has(value) {
        let currentNode = this.root;
        while (currentNode !== null) {
            if (currentNode.value === value) {
                return true;
            }

            if (currentNode.value < value) {
                currentNode = currentNode.right;
            } else {
                currentNode = currentNode.left;
            }
        }
        return false;
    }
}