자료구조 - 해시 테이블, 트리, 힙, 그래프 정리

1. 해시테이블

• 해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조

구현

충돌

• 아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다.
• 예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다.
  👉🏻 입력값이 달라도 똑같은 결과가 나오면 충돌
• 이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다.
• 오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식
• 체이닝은 충돌 발생 시 ‘연결’해가는 것
• 오픈 어드레싱 O(1)
• 체이닝 O(n)
• 오픈 어드레싱은 값이 뭉치는 클러스터링이 발생할 수 있고,
• 체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점
• 그래서 각 언어 별로 해시테이블의 구현 방식이 다른데요. C++, Java, Go는 체이닝을 택하고 Python, Ruby는 오픈 어드레싱을 택하고 있다.

구현 (Python)

• 체이닝 방식의 해시테이블

# structures.py


class HashTable:
    def __init__(self):
        self.size = 10 # 해시테이블의 사이즈 (10으로 나눈 나머지이기떄문에 10으로 설정)
        self.table = [None] * self.size

    def _hash_function(self, key):
        return key % self.size

    def put(self, key, value):

        index = self._hash_function(key) # 키를 넣었을 때 결과값

        if self.table[index] is None: # 값이 없을 때 (푸시한적이 없는 해싱값일 때)
            self.table[index] = HashNode(key, value)#next=None

        else: # 이미 값이 있을 때 (푸시한적이 있는 해싱값일 때) - 체이닝방식이므로 같은 값은 맨 끝에 계속 붙여주면 됨
            node = self.table[index]
            while node.next is not None: # 다음 노드가 없을 때 까지(맨끝까지)
                node = node.next
            node.next = HashNode(key, value)

    def get(self, key):

        index = self._hash_function(key)
        node = self.table[index]

        while node is not None: #노드에 배정된 키가 있을 동안
            if node.key == key: #내가 원하는 값(내가 넣은 키라면)
                return node.value #값 반환
            node = node.next #원하는 노드가 아니면 옮기자
        return -1 # 배정된 게 없다면 -1 반환하자

    def remove(self, key):

        index = self._hash_function(key)
        node = self.table[index]
        prev_node = None

        while node is not None:
            if node.key == key:

                if prev_node is None: # 이전 노드가 없다 - 첫번째꺼다 - 지금거를 다음걸로 바꾼다
                    self.table[index] = node.next
                else:
                    prev_node.next = node.next # 이전 노드의 next를 지금거의 다음걸로 넘긴다 (가운데를 빼는 느낌)
                return

            prev_node = node # 이전 노드를 지금 노드로 넘긴다
            node = node.next

 

# test.py

ht = HashTable()

ht.put(1, 1)
ht.put(2, 2)
assert ht.get(1) == 1
assert ht.get(2) == 2
assert ht.get(3) == -1

ht.put(12, 1)
ht.put(22, 2)
ht.put(32, 3)
assert ht.get(12) == 1
assert ht.get(22) == 2
assert ht.get(32) == 3

ht.remove(12)
assert ht.get(2) == 2
assert ht.get(12) == -1
assert ht.get(22) == 2
assert ht.get(32) == 3

ht.get(2)

 

---

2. 트리

• 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점
• 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점

트리 용어

• Node: 트리에서 데이터를 저장하는 기본 요소
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node(Terminal Node): Child Node가 하나도 없는 노드 (제일 끝)
• Sibling: 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

트리의 종류

이진트리

• 각 노드가 최대 두 개의 자식을 가지는 트리
• 하위 노드가 3개 이상일 수 없다. 무조건 0,1,2개

      o      Level 0
    o o o    Level 1
   o  o  o   Level 2 # 이진 트리(X)

      o      Level 0
    o   o    Level 1
   o o o     Level 2 # 이진 트리(O)

 

완전 이진 트리 (Complete Binary Tree)

• 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다

      o      Level 0
    o   o    Level 1
     o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

      o      Level 0
    o   o    Level 1
   o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

 

완전 이진 트리를 배열로 표현

트리 구조를 표현하는 방법

• 직접 클래스 구현
• 배열로 표현 -> 완전 이진 트리를 쓰는 경우에 가능!
  • 왼쪽부터 데이터가 쌓이므로, 이를 순서대로 배열에 쌓으면서 표현

완전 이진 트리 배열로 표현하기

• 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않음
• 그래서 None 값을 배열에 넣고 시작한다. [None]
• 8의 자식 6,3 / 6의 자식 4,2 / 3의 자식 5

      8      Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
    6   3    Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
   4 2 5     Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 됩니다!

 

배열 = [None, 8, 6, 3, 4, 2, 5]

 

1. 왼쪽에 있는 자식의 인덱스 : 현재 인덱스 * 2
   • 8 : 1번 / 6 : 1 * 2 = 2번
   • 6 : 2번 / 4 : 2 * 2 = 4번
2. 오른쪽 자식의 인덱스 : 현재 인덱스 * 2 + 1
   • 8 : 1번 / 3 : 1 * 2 + 1 = 3번
   • 6 : 2번 / 2 : 2 * 2 + 1 = 5번
3. 부모 인덱스 : 현재 인덱스 // 2
   • 3 : 3번 / 3 // 2 = 1번 : 8
   • ==부모를 찾을 수 있다!==

완전 이진 트리의 높이

트리의 높이

루트 노드부터 가장 아래 리프 노드까지의 길이

높이가 2인 트리

      o      Level 0  # 루트 노드
    o   o    Level 1
   o o o     Level 2  # 가장 아래 리프 노드

이 트리의 높이는 ? 2 - 0 = 2!

 

각 레벨에 노드가 꽉 차 있는 경우

      1            Level 0 -> 1개
    2   3          Level 1 -> 2개
   4 5 6 7         Level 2 -> 4개
 8 9....... 14 15  Level 3 -> 8개
                   Level k -> 2^k 개

 

👉 레벨이 k라면, 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k이다.

노드가 꽉 찬 완전 이진 트리의 모든 노드 개수

• 높이 h
• 각 레벨k 의 노드 2^k개

레벨은 1, 2, 3, ... , h 이므로 모든 노드의 개수는
1 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^h
=  2^(h+1) - 1

 

👉 높이가 h라면, 최대 노드 개수는 2^(h+1) -1개가 된다.

[!최대 노드 개수가 N이라면 h는?]
2^(h+1) -1 = N
→ h = log_2(N+1)-1

 

👉 완전 이진 트리 노드의 갯수가 N일 때, 높이는 최대 O(logN)

 

---

3. 힙 (Heap)

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Tree)(Complete Binary Tree) 

• 최대/최소의 값들이 필요한 연산에 사용
• Max 힙 : 최댓값이 맨 위
• Min 힙 : 최솟값이 맨 위

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

 

 

최대 힙 - 삽입 알고리즘

1. 원소를 맨 마지막에 넣는다.
2. 부모 노드와 비교, 더 크면 자리 바꾸기
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때 까지 반복

이 맥스 힙에서 9를 추가해보겠습니다!
      8      Level 0
    6   3    Level 1
   4 2 1     Level 2

1. 맨 마지막에 원소를 넣습니다.

      8      Level 0
    6   3    Level 1
   4 2 1 9   Level 2

2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   3    Level 1
   4 2 1 9   Level 2

      8      Level 0
    6   9    Level 1
   4 2 1 3   Level 2

2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   9    Level 1
   4 2 1 3   Level 2

      9      Level 0
    6   8    Level 1
   4 2 1 3   Level 2

3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!

      9      Level 0
    6   8    Level 1
   4 2 1 3   Level 2

 

최대 힙 - 삽입 시간 복잡도

완전 이진트리 최대 높이 : O(log(N))
-> 반복하는 최대 횟수 : O(log(N))
-> Max 힙의 원소 추가는 O(log(N)) 의 시간 복잡도

 

최대 힙 - 삽입 구현

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self.items) - 1
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

 

최대 힙 - 추출

최대 힙에서 원소를 추출하는 방법 : 루트 노드(최댓값) 삭제 👉 맨 위 원소만 삭제 가능

 

이 맥스 힙에서 원소를 제거해보겠습니다! (항상 맨 위의 루트 노드가 제거 됩니다.)
      8      Level 0
    6   7    Level 1
   2 5 4 3   Level 2

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

      8      Level 0
    6   7    Level 1
   2 5 4 3   Level 2

      3      Level 0
    7   6    Level 1
   2 5 4 8   Level 2

2. 맨 뒤에 있는 원소를 삭제합니다.
이 값이 기존 맥스힙에 있던 가장 큰 값입니다. 따라서 이 값을 마지막에는 반환해줘야 합니다!

      3      Level 0
    6   7    Level 1
   2 5 4 X   Level 2

3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 합니다.
우선 부모와 왼쪽 자식을 비교합니다. 그리고 부모와 오른쪽 자식을 비교합니다.
그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경해야 합니다.
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경합니다.

      3      Level 0
    6   7    Level 1
   2 5 4     Level 2

      7      Level 0
    6   3    Level 1
   2 5 4     Level 2

3-2. 다시 자식 노드와 비교합니다.
우선 부모와 왼쪽 자식을 비교합니다.
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경합니다.

      7      Level 0
    6   3    Level 1
   2 5 4     Level 2

      7      Level 0
    6   4    Level 1
   2 5 3     Level 2


4. 가장 아래 레벨에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삭제했습니다!

      7      Level 0
    6   4    Level 1
   2 5 3     Level 2

5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환하면 됩니다!

 

최대 힙 - 추출 시간 복잡도

O(log(N))

 

최대 힙 - 구현

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self.items) - 1
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def extract(self):
        if len(self.items) - 1 < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self.items) - 1 and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self.items) - 1 and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

 

---

4. 그래프 (Graph)

• 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점
• 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점
• 그래프 : 연결 관계에 초점

• 노드(Node): 연결 관계를 가진 각 데이터, 정점(Vertex)
• 간선(Edge): 노드 간의 관계를 표시한 선
• 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

유방향 그래프 (Directed Graph)

• 방향이 있는 간선
• 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행 가능

무방향 그래프 (Undirected Graph)

• 방향이 없는 간선

그래프의 표현 방법

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
• 인접 리스트(Adjacnecy List): 연결리스트 (Linked List)로 그래프의 연결 관계를 표현
• 제니 : 0 , 르탄 : 1 , 로제 : 2 , 사나 : 3

	  로제 - 사나
	   ⎜
제니 - 르탄

          2 - 3
          ⎜
      0 - 1

 

이를 인접 행렬, 2차원 배열로 나타내면

 

          2 - 3
          ⎜
      0 - 1

  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

 

이를 배열로 나타내면

graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

 

인접 리스트로 표현

• 인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장

          2 - 3
          ⎜
      0 - 1

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

 

이를 딕셔너리로 표현하면

graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

 

이 두 방식의 차이?

👉 시간 VS 공간

• 인접 행렬으로 표현 : 연결 여부를 즉각적으로 알 수 있다.
  • 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간 사용
• 인접 리스트로 표현 : 연결 여부를 알기 위해선 각 리스트를 돌아야 함
  • 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간 사용
  • 대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선) 만큼의 공간만 사용