pjaehyun의 개발일지

선택정렬(Selection Sort)란?

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
1. 주어진 데이터 중, 최소값을 찾는다.
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

선택 정렬(Selection Sort) 알고리즘 구현

1. 첫 번째 반복문 루프는 데이터의 마지막이 자동으로 정렬되기 때문에 데이터의 수 -1로 정해준다.
2. 최소값의 index를 저장할 수 있도록 변수를 선언해준다.
3. 두 번째 반복문은 정렬된 인덱스 다음번부터 시작하면 된다.
4. 차례대로 데이터 값을 비교하며 인덱스값을 알맞게 바꿔준다.

def selection_sort(data):
    for index in range(len(data) - 1):
        min_index = index
        for index2 in range(index+1, len(data)): # index+1은 min_index와 index2를 비교할 때
            if data[min_index] > data[index2]:   # +1을 하지않으면 자기자신을 비교하여 불필요한 부분을 제거
                min_index = index2
        data[index], data[min_index] = data[min_index], data[index]
    return data

선택 정렬(Selection Sort) 알고리즘 시간 복잡도

• 선택정렬 알고리즘에는 for문이 두 개 들어가니까 시간복잡도는 O(n^2)
• 실제로 상세하게 계산하면 𝑛∗(𝑛−1)/2이 된다.

정렬(sorting)이란?

• 정렬(sorting): 어떤 데이터들이 주어졌을 때 이를 순서대로 나열하는 것
• 정렬은 프로그램 작성시 빈번하게 필요로 한다.
• 다양한 알고리즘이 있으며, 알고리즘 학습의 필수이다.

버블 정렬(Bubble Sort)란?

• 두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

버블정렬의 규칙찾기

• n개의 리스트가 있는 경우 최대 n-1번의 로직이 적용된다.
• 로직을 1번 적용할 때 마다 가장 큰 숫자가 리스트의 가장마지막에 위치하므로 비교해야할 숫자가 하나씩 줄어들음
• 로직이 경우에 따라 일찍 끝날 수도 있다. 로직을 적용할 때 데이터의 교환이 한번도 일어나지 않으면 이미 정렬된 상태이므로 더 이상 로직을 반복할 필요가 없다.

버블 정렬(Bubble Sort) 알고리즘 구현

def bubble_sort(data):
    swap = False
    for index in range(len(data) - 1):
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        if swap == False:
            break
    return data

버블 정렬(Bubble Sort) 알고리즘 시간 복잡도

• 버블정렬 알고리즘에는 for문이 두 개 들어가니까 시간복잡도는 O(n^2)
• 최악의 경우, n*(n-1)/2
• 완전 정렬이 되어있는 상태라면 최선은 O(n)

• 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있다.
• 시간 복잡도: 얼마나 빠르게 실행되는지
• 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

• 통상 둘 다 만족시키기 어려움
• 시간과 공간은 반비례적 경향이 있다
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선이 된다.

공간 복잡도(Space Complexity)

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
• 총 필요 저장 공간
• 고정 공간(알고리즘과 무관한 공간): 코드 저장 곤간, 단순 변수 및 상수
• 가변 공간(알고리즘 실행과 관련이 있는 공간): 실행중 동적으로 필요한 공간
• 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛)
• c: 고정 공간
• 𝑆𝑝(𝑛): 가변 공간

Big-O 표기법을 생각해볼 때 고정공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.

공간 복잡도 계산

• 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 된다.

ex) 재귀함수를 사용하지 않은 factorial함수

• 변수 n의 값에 상관없이 변수 n, 변수 result, 변수 index만 필요로하기 때문에 공간복잡도는 O(1)이 된다.

def factorial(n):
    result = 1
    for index in range(2, n+1):
        result *= index
    return result

ex) 재귀함수를 사용한 factorial함수

• factorial함수를 재귀 함수로 1까지 호출할 경우 n부터 1까지 스택에 쌓이게 되어 저장공간이 n개 만들어지게 되므로 공간복잡도는 O(n)이 된다.

def factorial(n):
    if n > 1:
        return n * factorial(n-1)
    else:
        return 1

알고리즘 복잡도 계산 항목

• 시간 복잡도: 알고리즘 실행 속도
• 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

두 가지 항목이 존재하지만 일반적으로 공간복잡도보다는 시간 복잡도를 통해서 알고리즘 분석이 이루어진다.

알고리즘 성능 표기법

• Big-O 표기법: O(n)
• 알고리즘 최악의 실행 시간을 표기
• 가장 많이 사용되고 일반적으로 사용된다.
• 아무리 최악의 상황이라도, 최소한의 성능은 보장한다는 의미

• Ω (오메가) 표기법:  Ω(N)
• 오메가 표기법은 알고리즘 최상의 실행 시간을 표기

• Θ (세타) 표기법: Θ(N)
• 오메가 표기법은 알고리즘 평균 실행 시간을 표기

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기에는 최상, 평균, 최악 중 최악의 시간인 Big-O 표기법을 중심으로 한다.

Big-O 표기법

• O(입력)
• 입력 n에 따라 결정되는 시간 복잡도 함수
• O(1), O(𝑙𝑜𝑔𝑛), O(n), O(n𝑙𝑜𝑔𝑛), O(𝑛^2), O(2𝑛), O(n!)등으로 표기한다.
• 입력 n의 크기에 따라 기하급수적으로 시간복잡도가 늘어날 수 있다.
• O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) < O(𝑛^2) < O(2𝑛) < O(n!)

• 단순하게 입력 n에 따라, 몇번 실행되는지를 계산하면 된다.
• 표현식에 가장 큰 영향을 미치는 n의 단위로 표기한다.

• Big-O 표기방법
• 만약 시간 복잡도 함수가 10n^2 + 20 이라면
• 가장 높은 차수는 10n^2
• 상수는 실제 실행에 큰 영향이 없다.
• Big-O표기법으로 O(n^2)이 됨

힙이란?

• 힙: 데이터에서 최대한 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
• 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽부터 차례대로 삽입하는 트리

• 힙을 사용하는 이유
• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
• 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 사용된다.

힙(Heap) 구조

• 힙은 최대값을 구하기 위한 구조(Max Heap)와, 최소값을 구하기 위한 구조(Min Heap)로 분류할 수 있다.
• 힙은 다음과 같은 두 가지 조건을 가지고 있다.
1. 최대 힙의 경우 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.
• 최소 힙의 경우 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음
2. 완전 이진 트리 형태를 가진다.

힙과 배열

• 일반적으로 힙 구현시 배열 자료구조를 활용한다.
• 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, Root Node의 인덱스 번호를 1로 지정하면 구현이 수월하다.
• 부모 노드 인덱스 번호(Parent Node index) = 자식 노드 인덱스 번호(Child Node index) // 2
• 왼쪽 자식 노드 인덱스 번호(Left Child Node index) = 부모 노드 인덱스 번호(Parent Node index) * 2
• 오른쪽 자식 노드 인덱스 번호(Right Child Node index) = 부모 노드 인덱스 번호(Parent Node index) * 2 + 1

힙 구현

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) # 0번 자리를 None으로 초기화하여 1번부터 시작
        self.heap_array.append(data)

Insert 구현

• 삽입한 노드가 부모 노드의 값보다 클 경우, 부모 노드와 삽입한 노드 위치를 바꾼다.

    # 반복문을 실행하는 조건함수
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
            
    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        
        self.heap_array.append(data)
        inserted_idx = len(self.heap_array[-1])
        while move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
                self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
                inserted_idx = parent_idx
        return True

Insert를 구현할 때에는 조건문을 먼저 타는것이 아니라 데이터를 삽입한 후에 조건문을 이용하여 데이터를 한칸씩 상위노드로 올리는 작업을 해야한다. 최대 힙구조에서는 부모노드가 자식노드보다 작으면 안되기 때문에 삽입되어진 데이터가 부모노드보다 큰지 비교를하여 삽입된 데이터가 더 크다면 서로의 위치를 바꾸어 주는 과정을 반복한다.

Delete 구현

• 보통 삭제는 Root Node를 삭제한다.(힙의 용도는 최대값, 최소값을 Root Node에 놓아 바로 꺼내 쓸 수 있도록함)
• Root Node 삭제시 가장 하단부 왼쪽에 위치한 Node를 Root Node로 이동
• Root Node의 값이 Child Node보다 작을 경우 Root Node의 Child Node중 가장 큰 값을 가진 노드와 위치를 바꿔주는 작업을 함

    # 반복문을 실행하는 조건함수
    def move_down(self, root_idx):
        left_child_idx = root_idx * 2
        right_child_idx = root_idx * 2 + 1
        # 왼쪽 자식 노드도 없을 때
        if left_child_idx > len(self.heap_array):
            return False
        # 오른쪽 자식 노드만 없을 때
        elif right_child_idx >= len(self.heap_array):
            if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                return True # Root Node가 자식노드보다 작기때문에 반복문을 돌아야한다.
            else:
                return False
        # 자식이 둘 다 있을 때
        else:
            if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
                if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
                    return True
                else:
                    return False
 
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
            
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        root_idx = 1
        while move_down(root_idx):
            left_child_idx = root_idx * 2
            right_child_idx = root_idx * 2 + 1
            # 오른쪽 자식 노드만 없을 때
            if right_child_idx >= len(self.heap_array):
                if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                    self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]                    
                    root_idx = left_child_idx
            # 자식이 둘 다 있을 때
            else:
                if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
                    if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                        self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]
                        root_idx = left_child_idx
                else:
                    if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
                        self.heap_array[root_idx], self.heap_array[right_child_idx] = self.heap_array[right_child_idx], self.heap_array[root_idx]
                        root_idx = right_child_idx
        return returned_data

Delete를 구현할 때는 루트노드를 삭제하고 가장 뒤에있는 노드를 끌어올린 이후 부터 조건에 맞게 노드들을 이동시킨다.

데이터를 아래로 이동시키면 세가지 경우가 생긴다.

1. 자식노드가 존재하지 않을때

2. 부모노드아래에 왼쪽자식노드만 존재할 때

3. 자식노드가 둘 다 존재할 때

1번 경우는 자식노드가 없으니 더이상 내려갈 곳이 없어 아무런 행동을 취하지 않아도 된다.

2번경우는 자식노드가 부모노드보다 더 크다면 서로의 위치를 바꾸어 주어야한다.

3번경우는 자식노드 둘을 비교하여 둘중에 더 큰 노드를 부모노드와 비교하여 부모노드보다 더 크다면 위치를 바꿔준다.

이러한 과정을 조건이 맞을 때 까지 반복해준다.

전체 코드

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) # 0번 자리를 None으로 초기화하여 1번부터 시작
        self.heap_array.append(data)
        
    # 반복문을 실행하는 조건함수
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
            
    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        
        self.heap_array.append(data)
        inserted_idx = len(self.heap_array[-1])
        while move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
                self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
                inserted_idx = parent_idx
        return True
        
    # 반복문을 실행하는 조건함수
    def move_down(self, root_idx):
        left_child_idx = root_idx * 2
        right_child_idx = root_idx * 2 + 1
        # 왼쪽 자식 노드도 없을 때
        if left_child_idx > len(self.heap_array):
            return False
        # 오른쪽 자식 노드만 없을 때
        elif right_child_idx >= len(self.heap_array):
            if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                return True # Root Node가 자식노드보다 작기때문에 반복문을 돌아야한다.
            else:
                return False
        # 자식이 둘 다 있을 때
        else:
            if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
                if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
                    return True
                else:
                    return False
 
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
            
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        root_idx = 1
        while move_down(root_idx):
            left_child_idx = root_idx * 2
            right_child_idx = root_idx * 2 + 1
            # 오른쪽 자식 노드만 없을 때
            if right_child_idx >= len(self.heap_array):
                if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                    self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]                    
                    root_idx = left_child_idx
            # 자식이 둘 다 있을 때
            else:
                if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
                    if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
                        self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]
                        root_idx = left_child_idx
                else:
                    if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
                        self.heap_array[root_idx], self.heap_array[right_child_idx] = self.heap_array[right_child_idx], self.heap_array[root_idx]
                        root_idx = right_child_idx
        return returned_data

트리(Tree) 구조

• Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 사용된다.

트리(Tree)와 관련된 용어

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

이진 트리와 이진 탐색 트리(Binary Search Tree)

• 이진트리: 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리(Binary Search Tree): 이진 트리에 다음과 같은 추가 조건이 있는 트리
• 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다.

Node 클래스 구현

class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None

이진 탐색 트리 구현

class BST(self, value):
    def __init__(self, head):
        self.head = head

Insert 구현

    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

Search 구현

    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False

Delete 구현

    # 삭제 할 값을 탐색
    def delete(self, value):
        searched = False
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right
        if searched == False:
            return False

Case1: Child Node가 없는 노드 삭제

        # self.current_node가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태 
        # Leaf Node삭제(Child Node가 없는 노드 삭제)
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
            del self.current_node

Case2: Child Node가 한개 있는 노드 삭제

        # 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
        # Child Node가 자신보다 작을 때
        if self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
                
        # Child Node가 자신보다 클 때
        if self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right

Case3: Child Node가 두개 있는 노드 삭제

        # 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 삭제할 Node가 Parent Node보다 작을 경우
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_parent = self.change_node
                    self.change_node = self.change_node.left
                    
                # 가장 작은 값을 가진 Node의 Child Node가 있을 때
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
            
            # 삭제할 Node가 Parent Node보다 클 경우
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                    
                # 가장 작은 값을 가진 Node의 Child Node가 있을 때
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left

전체 코드

class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None
 
class BST(self, value):
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
                    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False
        
    def delete(self, value):
        searched = False
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right
        if searched == False:
            return False
        
        # Leaf Node삭제(Child Node가 없는 노드 삭제)
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
            del self.current_node
            
        # 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
        # Child Node가 자신보다 작을 때
        if self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
                
        # Child Node가 자신보다 클 때
        if self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right
                
        # 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 삭제할 Node가 Parent Node보다 작을 경우
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
            
            # 삭제할 Node가 Parent Node보다 클 경우
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
        
                

Linear Probling 기법

• Close Hashing 기법 중 하나, 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면 해당 hash address의 다음 address부터 맨처음에 나오는 빈공간에 저장하는 기법

Linear Probling 기법 구현

hash_table = list([0 for i in range(10)]) # 0부터 9까지의 리스트를 0으로 초기화
 
def get_key(data):
    return hash(data)
 
def hash_function(key):
    return key % 10
 
def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:                        # 해시 주소값안에 데이터가 존재할 때
        for index in range(hash_address, len(hash_table)):   # 현재 주소값 테이블의 끝까지 반복문을 돌며
            if hash_table[index] == 0:                       # 빈 공간을 찾으면 데이터를 저장
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key
                hash_table[index][1] = value                 # 해시 주소값 안의 key값과 index_key값이 동일하면 데이터를 수정
                return
    else:
        hash_table[hash_address] = [index_key, value]
        
def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):  # 해시 주소값 부터 테이블 끝까지 반복문을 돌며
            if hash_table[index] == 0:                      # 해시 주소안의 키 값이 index_key와 동일한지 찾고
                return None                                 # 동일하다면 해당 value값을 반환
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

해시 충돌(Hash Collision)

• 서로 다른 두개의 입력에 대해 동일한 출력값을 내는 상황을 말한다.
• 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

Chaining 기법

• 해시충돌을 해결하기 위한 기법
• Open Hashing 기법 중 하나, 해시 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료구조를 이용하여 데이터를 추가로 뒤에 연결시켜 저장하는 기법

Chaining 기법의 장단점

장점

• 한정된 공간을 효율적으로 사용할 수 있다.
• 미리 공간을 잡아둘 필요가 없다.

단점

• 외부 저장공간을 사용한다.
• 한 해시에 자료들이 계속 연결되면 검색 효율이 떨어진다.

Chaining 기법 구현

hash_table = list([0 for i in range(10)]) # 0부터 9까지의 리스트를 0으로 초기화
 
def get_key(data):
    return hash(data)
 
def hash_function(key):
    return key % 10
    
def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    # 해시주소값에 데이터가 존재할 때
    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            
            # 해당 해시 주소값의 key 값과 index_key가 같을 때 데이터를 덮어씀
            if hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
        
        # hash_address에 해당하는 key값과 index_key값이 일치하지 않으면 append해줌으로 데이터를 추가
        hash_table[hash_address].append([index_key, value])
    else:
        hash_table[hash_address] = [[index_key, value]]
        
def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:
    
        # hash_address에 해당하는 key값과 index_key가 일치하면 value를 반환해준다.
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None
    else:
        return None