[자료구조] 트리&힙

이정우·2023년 3월 17일
0

자료구조

목록 보기
1/5
post-thumbnail

밸~하!

밸로그 여러분 안녕하세요!

오늘은 자료구조 중 비선형 자료구조인 트리와 힙에 대해서 알아보겠습니다!

트리란?

트리는 몇가지 제약이 있는 방향 그래프의 일종입니다!

하나의 루트에서 하위로 뻗어나가는 구조 즉 정점을 가리키는 간선이 하나밖에 없는 구조를 가지고 있습니다

잠깐 용어 설명을 드리자면

가장 최상단에 있는 정점을
Root 루트 라고 부릅니다
또한 각 정점은 Node 노드 라고 부르며 가장 하위의 자식이 없는 노드는 Leaf Node 리프노드라고 부릅니다

그리고 트리에는 레벨 이라는 개념이 존재합니다

레벨이란?

루트로 부터 몇번째 깊이 인지를 나타내는데 쓰입니다
그리고 한 정점에서 뻗어나가는 간선의 수를 Degree 곧 차수라고도 부릅니다

이러한 트리는 어디에서 많이 사용할까요??

가장 흔히 사용하고 접할 수 있는것이 바로
조직도 입니다

대표이사로부터 뻗어나가는 조직도를 생각해 보시면 이해가 쉬울 것입니다

소프트웨어 에서 떠올릴 수 있는 구조로는

디렉토리 구조입니다

이처럼 트리 또한도 다양한 곳에서 쓰일 수 있는 자료구조입니다
그럼 트리는 어떤 특징을 가지고 있을까요??

트리의 특징

  1. 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.

  2. 정점이 n개인 트리는 반드시 n-1개의 간선을 가진다
    -왜냐하면 하나의 부모 정점만을 가지고 있기 때문입니다

  3. 루트에서 특정 정점으로 가는 경로는 유일하다

    트리는 몇가지 규칙만 지키면 아무렇게나 구현해도 상관 없습니다

    단 이진트리는 탐색을 위한 알고리즘에서 많이 쓰이기 때문에 그 특징을 알아부면 좋습니다

    이진트리

    이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미합니다
    완전 이진트리는 마지막 정점을 제외하고 모든 정점이 채워져 있는 트리를 의미합니다
    만약 마지막 정점까지 채워진다면 포화 이진 트리라고 부릅니다
    편향 트리의 경우에는 한 방향으로만 정점이 이어진것을 뜻합니다

    이진트리의 특징

  4. 정점이 n개인 이진 트리는 최악의 경우 높이가 n이 될 수 있다
    -n 개의 정점을 가진 편향트리가 되는것입니다

  5. 정점이 n개인 포화 또는 완전 이진 트리의 높이는 log n 이다

  • 레벨이 증가됨에 따라 두개씩 정점이 생기기 때문입니다
  1. 높이가 h인 포화 이진 트리는 2**h -1 개의 정점을 가진다.
  • 이진법을 생각하시면 이해가 쉬우실 것입니다
  1. 일반적인 이진 트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용 된다.
    -이진 탐색 트리
    -힙
    -AVL 트리
    -레드 블랙 트리

    그러면 트리는 어떻게 구현할 수 있을까요??

    트리의 구현 방법

    트리는 그래프의 일종이기 때문에 구현하는 방법도 인접 행렬과 인접 리스트로 구현할 수 있습니다

    이진 트리의 경우 자식의 정점이 2개 이하로 제한이 되기 때문에
    조금 더 최적화 된 방법으로 구현 할 수 있습니다

    일차원 배열 혹은 링크가 2개 존재 하는 연결리스트로 구현 가능합니다!

    자바스크립트에서는 어떻게 구현할까요??

    먼저 배열로 구현하기위해서는 몇가지 규칙만 기억하면 됩니다

  2. index*2를 하면 왼쪽 정점

  3. index*2+1을 하면 오른쪽 정점

  4. 부모정점을 구하기 위해 (index/2)의 소수점 버리기

    이런 방식으로 간단하게 이진트리를 구현할 수 있습니다

    이진트리를 또한 연결리스트로도 구현할 수 있는데요

    기존 연결리스트의 노드에 next대신 left와 right를 넣습니다
    그 다음 계속 left와 right에 값을 연결시켜주면 완성됩니다!

    그다음 알아볼것은 바로
    힙입니다!

    힙에 대해서 알아보기 이전에 우선순위 큐라는 개념에 대해서 설명드리겠습니다!

    우선순위 큐란?

    일반적인 큐와는 다르게 우선순위가 높은요소가 먼저 나가는 개념을 가지고 있습니다

    여기서 주의할점은
    우선순위 쿠는 자료구조가 아닌 개념이라는 것입니다
    따라서 우선수위 큐를 구현하는 방법은 다양하게 존재할 수 있습니다!

    그중 힙은 우선순위 큐를 구현하기 위한 가장 적합한 방식입니다
    그럼 이제 힙에 대해서 알아보겠습니다

    힙 이란?

자료구조 힙은 이진트리 형태를 가지며 우선순위가 높은 요소를 루트에 두기위해 요소가 삽입,삭제 될때 바로 정렬되는 특징이 있습니다

간혹 우선순위 큐와 힙이 같다고 이야기를 하는경우도 있지만 실제로는 다릅니다

만약 매번 배열을 우선순위에 따라서 정렬을 한다면
그것도 우선순위 큐가 될 수 있습니다
단지 힙보다 효율성이 떨어질 뿐입니다

그럼 이 힙은 어떤 특징을 가지고 있는지 알아보겠습니다!

힙의 특징

  1. 우선순위가 높은 요소가 먼저 나가는 특징을 가진다
  2. 힙은 루트가 가장 큰값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap) 이 두가지가 존재합니다
    -두가지의 차이는 오름차순이냐 아니면 내림차순이냐의 차이만이 존재합니다
  3. 다른언어와는 다르게 자바스크립트에서는 힙을 직접 구현해서 사용해야한다

그럼 이제 힙이 어떤식으로 동작하는지 알아보겠습니다

힙의 핵심 로직

힙의 핵심로직은 요소 추가와 삭제입니다!

1. 힙의 요소를 추가하는 로직

힙 요소 추가 알고리즘은 다음과 같은 규칙을 따릅니다!

1.먼저 요소를 추가할 때 이진트리의 가장 마지막에 추가합니다!
2. 요소가 추가되면 부모정점보다 우선순위가 높은지 체크합니다 만약 우선순위가 부모정점보다 높다면 부모정점과 순서를 바꿉니다
3. 2번의 과정을 반복하면 결국 우선순위가 가장 높은 정점이 루트가 됩니다
4. 요소가 추가될때 항상 마지막 정점에 추가되기 때문에 힙은 항상 이진트리입니다
5. 완전 이진트리의 높이는 log n이기에 힙의 요소 추가 알고리즘은 O(log n) 시간복잡도를 가지게 됩니다

2. 힙의 요소를 제거하는 로직

힙 요소 제거 알고리즘은 힙의 요소 추가 알고리즘보다 조금 더 복잡합니다

  1. 요소 제거는 루트 정점만 가능합니다
    그래서
    2.루트정점이 제거 되면 가장 마지막 정점이 루트에 위치합니다
    이때 추가와는 반대로 루트로부터 점점 정점을 아래로 내려야합니다
    3.루트 정점의 두 자식 정점 중 우선순위가 높은 정점과 바꾼다
  2. 두 자식 정점이 우선순위가 더 낮을때 까지 반복합니다
    그러면 자연스럽게 우선순위가 더 높은 정점이 루트정점이 될 수 있습니다
    추가와 마찬가지로 제거도 완전 이진트리의 높이만큼 진행되기 때문에
  3. 시간복잡도가 O(log n)이 된다

그러면 이제는 자바스크립트에서 어떻게 구현하는지 알아보겠습니다

javascript에서 구현하기

요소 추가 로직

먼저 내부적으로 관리 해야 할 배열이 필요합니다
편의를 위해 null로 표현하겠습니다

추가 로직을 진행할 때 규칙에 따라 힙의 가장 마지막에 요소를 추가합니다
이제부터 부모와 우선순위를 비교하여 순서를 바꾸는 로직을 반복할 겁니다

부모가 더 우선순위가 낮거나 루트가 아닐때까지 루프를 돌리면서
부모와 자식의 순서를 바꿔줍니다

요소 제거 로직

제거로직은 추가 로직보다 조금 더 복잡합니다

먼저
루트 요소를 반환하기 위해 임시로 상수에 저장합니다
그리고 루트정점은 가장 마지막 정점으로 대체합니다
그리고 나서 루트로부터 아래로 내려가기 위한 변수를 미리 설정해 둡니다

반복은 하위 정점들이 현재 정점보다 우선순위가 낮을 경우 종료합니다

먼저 왼쪽 정점보다 오른쪽 정점이 우선순위가 낮은경우 오른쪽 정점과 바꿉니다
만약 아니라면 왼쪽 정점과 바꿉니다

그리고 바꾼 정점에서 왼쪽정점의 위치와 오른쪽 정점의 위치를 다시 구합니다
이렇게 루프가 종료될때까지 반복하면 힙 구조를 지킬수 있습니다

자 이렇게 오늘은 트리와 힙에 대해서 알아보았는데요!

직접 이론을 따라 구현해 보는것도 공부에 조금 더 도움이 되는것같습니다!

그럼 오늘도 이만

밸~바!

profile
주니어 프론트엔드 개발자

0개의 댓글