명품호세의 개발 공부 및 기록 블로그

트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

용어 :

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

이진 트리와 이진 탐색 트리

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

이진 탐색 트리 삭제

• 매우 복잡하다. 경우를 나누어서 이해하는 것이 좋다.

1. Leaf Node 삭제
   • Leaf Node : Child Node가 없는 Node
   • 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.
2. Child Node가 하나인 Node 삭제
   • 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.
3. 삭제할 Node의 자식이 2개인 경우 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다 (아래 방법중 하나를 선택해서 적용한다.)
   • 삭제할 Node의 오른쪽 자식 중, 가장 작은 삭제할 Node의 Parent Node가 가리키도록 한다.
   • 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

Ex)

1. 삭제할 Node의 오른쪽 자식 선택
2. 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
3. 해당 Node를 삭제할 Node의 Parent Node의 완쪽 Branch가 가리키게 한다.
4.  해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 한다.
5. 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 한다.
6. 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 한다.

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


class NodeManagement:
    def __init__(self, root):
        self.root = root

    def get_value(self):
        return self.root.value

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

    def search(self, value):
        self.current_node = self.root

        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.root
        self.parent = self.root
        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 is False:
            return False

        # 삭제할 노드를 찾음
        # 1. 삭제할 노드가 리프노드 경우
        if self.current_node.left is None and self.current_node.right is None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None

        # 2. 삭제할 노드가 Child Node를 가지고 있을 경우
        # 2-1 Child Node가 삭제할 노드의 왼쪽에 있을 경우
        elif self.current_node.left is not None and self.current_node.right is None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left

        # 2-2 Child Node가 삭제할 노드의 오른쪽에 있을 경우
        elif self.current_node.left is None and self.current_node.right is not None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right

        # 3. 삭제할 노드가 Child Node를 양쪽 모두 가지고 있을 경우
        elif self.current_node.left is not None and self.current_node.right is not None:
            # 3-1 삭제할 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:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                self.change_node_parent.left = None
                if self.change_node.right:
                    self.change_node_parent.right = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.change_node.left

            # 3-2 삭제할 Node가 Parent Node 오른쪽에 있는 경우
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right:
                    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

        return True



if __name__ == "__main__":
    bst_nums = set()

    while len(bst_nums) != 100:
        bst_nums.add(random.randint(0, 999))

    print(bst_nums)

    head = node_management.Node(500)
    binary_tree = node_management.NodeManagement(head)

    for number in bst_nums:
        binary_tree.insert(number)

    # 검색 기능 확인
    for number in bst_nums:
        if binary_tree.search(number) is False:
            print("search failed : ", number)

    delete_nums = set()
    bst_nums = list(bst_nums)
    while len(delete_nums) != 10:
        delete_nums.add(bst_nums[random.randint(0, 99)])

    # 삭제 기능 확인
    for del_num in delete_nums:
        if binary_tree.delete(del_num) is False:
            print('delete failed', del_num)

이진 탐색 트리의 시간 복잡도와 단점

시간 복잡도 (탐색)

• depth ( 트리의 높이) 를 h라고 표기한다면 O(h)
• 검색을 하기위해 비교 할때마다 절반씩 사라지므로 O(log n)으로 표시할 수 있다.

단점

• 균형이 잡혀이는 트리의 경우 평균 시간 복잡도는 O(log n)이지만 트리가 한쪽으로 편향되어 있으면 O(n)으로 나빠질 수 있다.

Hash Table : 키(key)에 데이터(value)를 저장하는 구조

• Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
• 파이썬 딕셔너리 타입이 해쉬 테이블의 예시이다.
• 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용한다 (공간과 탐색 시간을 맞바꾸는 기법이다.

기본 예시

# 간단한 해쉬 함수를 만들기 (나무기를 통해 나머지 값을 사용하기)
def custom_hash_func(key):
    return key % 5


def storage_data(data, value):
    key = ord(data[0])
    hash_address = custom_hash_func(key)
    hash_table[hash_address] = value


def get_value(data):
    key = ord(data[0])
    hash_address = custom_hash_func(key)
    return hash_table[hash_address]


if __name__ == '__main__':
    hash_table = list([0 for i in range(10)])

    storage_data('Andy', '01012341234')
    storage_data('Dave', '01033332222')
    storage_data('Trump', '01055556666')

    print(hash_table)
    print(get_value('Andy'))

해시 테이블의 가장 큰 문제는 해시 충돌이다. 이것을 해결하는 방법은 아래와 같다.

• Chaining 기법
  • 개방 해싱 또는 Open Hashing 기법 중 하나이다. 
  • 충돌이 일어나면, 링크드 리스트를 사용하여 데이터를 추가로 뒤에 연결시켜 저장한다.

  • def get_key(data):
        return hash(data)
    
    
    def hash_function(key):
        return key % 8
    
    
    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])):
                if hash_table[hash_address][index][0] == index_key:
                    hash_table[hash_address][index][1] = value
                    return
                hash_table[hash_address].append([index_key, value])
        else:
            hash_table[hash_address] = list([index_key, value])
        hash_table[hash_address] = 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(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
    
    
    if __name__ == "__main__":
        ## 해시 충돌 해결 해보기
        hash_table = list([0 for i in range(8)])
    

• Linear Probing 기법
  • 폐쇄 해슁 또는 Close Hashing 기법중 하나이다.
  • 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법

  • def get_key(data):
        return hash(data)
    
    
    def hash_function(key):
        return key % 8
    
    
    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
                    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:
                    return None
    
                elif hash_table[index][0] == index_key:
                    return hash_table[index][1]
        else:
            return None
    
    
    if __name__ == "__main__":
        ## 해시 충돌 해결 해보기
        hash_table = list([0 for i in range(8)])