[데브코스] TIL-105 이진 탐색 트리, 이진 힙

  오늘은 전체적인 자료구조와 알고리즘에 대한 강의 내용이었다. 다시 듣는 내용도 있었고, 들어 보지 못했던 새로운 내용도 존재했다. 기존에 들었던 내용들도 시간이 지나면서 많이 잊어버렸는데 다시 한 번 들어보니 처음 들었을때 보다는 조금은 더 익숙해진 느낌이다. 우선 트리, 이진 트리, 이진 탐색 트리, 힙, 트라이, 정렬, 탐색등에 대해서 공부를 했다. 그런데 참..이게.. 들을때는 이해했는데 시간이 지나면,,, 잊어버린다는게,,, 문제다,,, 자연스럽게 익숙해 질 수 있게 계속 보는게 답인 것 같다...기존에 보다 자세하게 정리한 부분들이 있지만 오늘 배운 내용을 기준으로 간략하게 다시 정리해 보려 한다.

---

트리란?

 

  트리는 말그대로 나뭇가지가 뻗어나가는 것을 형태를 갖기 때문에 트리라고 부르는데 방향 그래프의 일종으로 노드를 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다.

 

• 노드들 사이에는 부모와 자식의 관계를 갖는다.
• 가장 최상위 노드를 '루트노드'라 부른다.
• 정점이 n개의 트리는 반드시 n-1개의 간선을 갖는다.
• 루트 노드에서 특정 노드로 가는 경로는 유일하다.(시작은 반드시 루트 노드를 타고 이동하므로)
• 주의해야 할 점은 같은 부모 노드를 가지는 노드들을 sibling(형제)관계라고 하는데 만약 형제 노드들끼리 연결이 되어 있다면 이것은 트리 자료 구조가 아니다!!

---

이진 트리란?

 

  이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.(트리의 특성에서 이진 트리만의 특성이 추가된 것)

 

• 트리 자료 구조의 특징을 모두 가지고 있음
• 추가적으로 각 노드는 최대 2개의 노드를 가질 수 있는 구조다.
• 완전 이진 트리, 포화 이진 트리, 편향 이진 트리로 유형화 되어 있다.
• 일반적인 이진 트리를 사용하는 경우는 많지 않고 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리를 구현할때 응용된다.

  이진 트리를 구현하는 방법은 크게 배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현할 수 있다. 특히 배열을 이용해서 만드는것이 편리하긴 하다. 배열을 통해 이진 트리를 구성하는 방법은 수학적 규칙을 이용해서 구현하는것이다. 

//부모 노드에서 자식 노드로 접근하려면
let leftChildNode = parentNodeIndex * 2;
let rightChildNode = parentNodeIndex * 2 + 1;

//자식 노드에서 부모 노드로 접근하려면
let parent = parseInt(childNodeIndex / 2)

//이진 트리
          9
       	 / \
      	3   8
       / \   \
      2  5    7
               \
                4
//이진 트리를 구현
let binaryTree = [undefined,9,3,8,2,5,undefined,7,undefined,undefined,undefined, 4];
//참고로 0번 인덱스는 사용하지 않는편이 좋다.

---

이진 탐색 트리란?

 

  기존의 트리와 이진 트리의 특성을 모두 갖으며, 추가적으로 부모노드의 왼쪽 자식 노드는 부모보다 작은 값을 오른쪽 자식 노드는 부모보다 큰 값을 갖는 특징을 가지고 있는 자료구조이다. 이진 탐색 트리를 순회하는 방법으로는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 방법이 존재하는데 그 중에서도 DFS는 다시 전위 순회, 중위 순회, 후위 순회로 이진 탐색 트리를 순회할 수 있다.

---

이진 힙이란?

 

  이진 힙은 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 정렬되는 자료 구조이다. 

 

• 우선순위가 높은 요소가 먼저 나가는 특징을 가진다
• 루트가 가장 큰 값이 되는 최대 이진 힙과 루트가 가장 작은 값이 되는 최소 이진 힙으로 나뉜다.
• 자바스크립트에서는 직접 힙을 구현해서 사용해야 한다.
• 보통 우선순위 큐를 구현할 때 많이 활용된다.(우선순위 큐는 자료구조가 아닌 우선 순위가 높은 요소가 먼저 나가는 형식을 일컫는 말이다. 따라서 구현 방법은 다양하다.)

이진 힙 요소 추가 방법

 

1. 요소가 추가될 때는 트리의 가장 마지막에 정점을 위치시킨다.
2. 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
3. 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.

이진 힙 요소 제거 방법

 

1. 요소 제거는 루트 정점만 가능하다.(그래서 사실상 이진 힙에서 요소 제거는 루트 노드를 제거하는 것이다.)
2. 루트 노드가 제거된 후 가장 마지막에 위치하는 노드가 루트를 위치시킨다.(즉, 루트노드 제거 > 그 자리에는 가장 마지막에 위치한 노드로 바꿔준다.)
3. 루트 노드의 두 자식 노드 중 더 우선순위가 높은 노드와 자리를 바꾼다.
4. 그리고 새롭게 가지게 되는 두 자식 노드들의 우선순위가 더 낮을 때까지 이를 반복한다.

---

트라이(trie)란?

 

  문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 트리구조의 간선은 이전 정점으로부터 새롭게 추가되는 문자정보를 가지고 있다. 일반적으로 검색창의 자동완성 기능에 사용된다. 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 탐색이 가능하다. 다만 각 노드가 자식에 대한 정보를 전부 가지고 있기 때문에 저장 공간을 더 많이 사용하게 된다. 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

//ex) 'cat' , 'can'


              (루트) <<비어 있음
            c /
             /
          ('c')
         a /
          /
       ('ca')
      t /  \ n
       /    \
   ('cat') ('can')

---

 

이진 탐색이란?

 

  이진 탐색은 정렬되어 있는 요소들을 절반씩 제외하며 찾는 알고리즘으로 O(log N)시간 복잡도를 갖는다.

 

• 반드시 정렬되어 있어야 사용할 수 있다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• 탐색 속도가 매우 빠르다.

배열을 이용한 구현 방법

 

• 2개의 포인터가 필요하다.
• left 포인터는 요소의 0번 index를 rigth 포인터는 마지막에 위치한 요소의 index를 갖는다.
• 절반씩 제거해 나가야 하기 때문에 중간지점(mid)를 left + right / 2 로 찾아서 탐색하고자 하는 값과 비교한다.
• 탐색하고자 하는 값보다 작다면 right 포인트를 mid -1 로 옮겨 탐색 과정을 반복한다.
• 탐색하고자 하는 값보다 크다면 left 포인트를 mid + 1 로 옮겨 탐색 과정을 반복한다.
• 단, 주의해야 할 점은 left 값이 right 값 보다 작다는 조건이 필요하다. (없으면 무한 루프에 빠짐) 

---

오늘을 마무리 하며

 

  분명 한 번 들었던 내용임에도 생각보다 헷갈렸고, 구현하는게 쉽지 않다는 생각이 많이 들었다. 자료구조와 알고리즘은 계속해서 반복적으로 공부하며 천천히 익숙하게 만들어야 할 필요가 있는것 같다. 그리고 또 단순히 자료구조와 알고리즘을 알고 있다는것과 그것을 직접 구현하는 것은 다른 문제이기 때문에 이번 주 과제로 주어진 '이진 탐색 트리를 전위 순회, 중위 순회, 후위 순회를 구현하는 것'과 '트라이로 자동 완성 기능을 직접 구현하는 것' 을 기준으로 구현 연습을 집중적으로 해 볼 생각이다.