1. 해싱(Hashing)

해싱은 데이터를 키:값의 쌍으로 구성하여 배열에서 인덱스로 데이터를 참조하듯 키로 데이터에 바로 접근할 수 있도록 하기위해

고안된 방식이다.  해시 함수(Hash Function)를 사용하여 키 값을 특정한 길이의 해시값으로 변환하고 이 해시값에 해당하는

위치에 데이터를 저장하는 것으로 삽입, 삭제, 탐색에 O(1)에 가까운 성능을 보이도록 한다.  Python의 dictionary 나 Java의
HashMap, HashTable 과 같이 대부분의 언어에서 내장 라이브러리로 지원하며 굉장히 자주 사용되는 유용한 방식이다. 

 

 

2. 용어

  • 버킷(Bucket) : 해시 함수로 얻은 해시 값을 주소로 하는 저장 공간.  해시 방식은 미리 지정된 갯수만큼의 버킷을 만들어두고
                                  데이터를 저장해나간다. 

  • 슬롯(Slot) : 버킷이 데이터 하나를 저장하기 위해 사용하는 공간. 

  • 충돌(Collision) : 서로 다른 키 값에 대해 해시 함수로 얻은 해시 값이 서로 동일한 경우, 즉 같은 버킷에 다수의 데이터를
                                      저장해야하는 상황을 의미한다.
  • 클러스터링(Clustering) : 연속된 주소를 가진 버킷에 데이터가 밀집되는 현상을 의미한다.
  • 부하율(Load Factor) : 전체 버킷 중 사용중인 버킷의 비율을 의미한다. 

 

 

3. 해싱의 특징

  • 삽입, 삭제, 탐색에 평균적으로 O(1)의 성능을 보인다.

  • 해시 함수의 특성상 언젠가 충돌이 반드시 발생하며 그럴수록 성능이 저하되기 때문에 해시 함수가 얼마나
    충돌이 일어나지 않도록 해시 값을 생성하느냐에 따라 성능이 크게 좌우된다.

 

 

4. 충돌(Collision) 의 처리

 ① 체이닝(Chaining) 기법

  • 같은 해시 값을 가지는, 즉 같은 버킷에 저장해야할 데이터들을 연결 리스트의 형태로 이어붙이는 방식

  • 비교적 구현이 간단하고 연결리스트를 사용하기 때문에 슬롯 갯수의 제약이 없다.

  • 클러스터링에 영향을 거의 받지 않기 때문에 해시 함수를 선정할 때 충돌의 최소화만을 중점적으로 고려할 수 있다.

  • 충돌이 많이 발생할 경우 최악의 경우 O(N) 수준까지 성능이 저하될 수 있다.
     
  • 하나의 버킷의 슬롯 갯수가 일정 이상으로 늘어나면 연결 리스트 대신 이진 트리를 사용하여 검색효율을 높이기도 한다.

  • 부하율이 높아져도 성능 저하가 선형적으로 발생하기 때문에 높은 부하율이 예상될수록 개방주소기법에 비해 성능이 좋다.

  • 처음에 얻은 해시주소 내에서 문제를 해결하기 때문에 폐쇄 해싱(Closed Hashing)이라고도 한다.

 

 ② 개방주소(Open  Addressing) 기법

  • 충돌이 발생할 경우 다른 비어있는 버킷을 찾아 데이터를 삽입하는 방식

  • 체이닝 기법과 달리 추가적인 메모리나 외부 자료구조에서의 작업을 필요로하지 않는다.

  • 연결리스트나 트리 등 외부 자료구조를 사용하지 않기 때문에 삽입/삭제의 오버헤드가 적어 저장할 데이터가  적다면
    체이닝 기법보다 좋은 성능을 보인다.

  • 저장해야할 데이터가 많아져서 부하율이 일정 이상으로 증가하면 체이닝에 비해 성능이 급격히 저하된다.
  • 비어있는 버킷을 찾는 방식으로 선형 탐색, 제곱 탐색, 이중 해싱이 있다. 

  • 선형 탐색은 말그대로 선형적으로 다음 버킷을 참조해나가며 빈 버킷을 찾는 방식이다.

  • 제곱 탐색은 처음 얻은 해시 값에서 제곱수만큼씩 증가해나가며 빈 버킷을 찾는 방식이다.
  • 이중 해싱은 처음 얻은 해시 값이 충돌을 일으킬 경우 2차 해시 함수를 사용하여 다시한번 해시 값을 얻는 방식이다.
    가장 많은 연산을 필요로하지만 클러스터링의 영향을 거의 받지 않는다.

 ※ 클러스터링에 취약하다는 것은 반대로 참조 지역성(Locality of Reference)이 높다는 의미가 되기 때문에
      캐싱 성능이 좋아진다. 그렇기 때문에 선형탐색 -> 제곱 탐색 -> 이중 해싱 순으로 클러스터링 방지는 잘 되지만
      참조 지역성이 낮아져 캐싱 성능은 떨어진다. 체이닝 기법의 경우에도 클러스터링의 영향을 거의 받지 않기 때문에
      참조 지역성이 낮아 선형탐색을 통한 개방주소 기법에 비해 캐싱 성능이 떨어진다.

 

 

5. 리사이징(Resizing) & 재해싱(Rehashing)

  • 부하율이 높아져 성능이 저하되는 것을 방지하기 위해 기존보다 더 많은 버킷을 할당한 뒤 기존에 저장된 데이터들을
    새로운 공간간에 다시해싱하는 작업 

  • 개방주소법의 경우 삭제 시 발생하는 더미 데이터 등으로 인한 성능저하 문제도 있기 때문에 주기적인 재해싱을 해줘야
    성능을 유지할 수 있다.

 

1. ADT 작성

Trie:
    Datas:
        __root : 트리의 루트노드
        __size : 트리의 크기

    Operations:
        insert(string) : 문자열 string 을 트라이에 삽입
        find(string) : 문자열 string이 트라이에 들어있다면 True, 아니라면 False 반환
        
Trie.__Node:
    Datas:
    	is_term : 해당 노드가 문자열의 마지막 문자를 나타내는지 여부
        next : 연결된 다음 문자 노드 리스트.  next[ord(key) - ord('a')] 가 None 이 아니라면
               다음 문자가 key인 문자열이 Trie 내에 존재한다는 의미가 된다.

    Operations:
    	get(key) : 문자 key 에 해당하는 다음 문자 노드를 반환
        set(key) : 문자 key 에 해당하는 다음 문자 노드를 설정

 

 

2. 구현 

class Trie:
    # 트라이의 노드 클래스
    class __Node:
        def __init__(self, is_term=False):
            self.next = [None] * 26
            self.is_term = is_term

        # key 에 해당하는 다음 문자 노드를 반환
        def get(self, key):
            return self.next[ord(key) - ord('a')]

        # key 에 해당하는 다음 문자 노드를 설정
        def set(self, key, node):
            self.next[ord(key) - ord('a')] = node

    def __init__(self):
        # 루트 노드
        self.__root = self.__Node()
        
        # 트라이의 크기
        self.__size = 0

    def __len__(self):
        return self.__size

    # 문자열 삽입
    def insert(self, string: str):
        # 루트 노드에서 탐색 시작
        cur = self.__root

        # 삽입할 문자열의 모든 문자를 소문자로 변환
        for c in string.lower():
            nxt = cur.get(c)
            # 문자 c에 해당하는 노드가 없다면 생성
            if not nxt:
                nxt = self.__Node()
                cur.set(c, nxt)

            # 문자 c에 해당하는 노드로 이동
            cur = nxt

        # 기존에 없었던 문자열이라면
        if not cur.is_term:
            # 문자열의 마지막 문자에 해당하는 노드에 is_term 값을 True 로 설정
            cur.is_term = True
        
            # 트리의 크기 1 증가
            self.__size += 1

    # 문자열 탐색
    def find(self, string):
        return True if self.__search(string) else False

    # 문자열의 마지막 문자에 해당하는 노드를 찾아 반환
    def __search(self, string: str):
        cur = self.__root
        for c in string.lower():
            cur = cur.get(c)
            if not cur:
                return None
        if cur.is_term:
            return cur
        return None

 

1. 트라이(Trie)

 트라이(Trie)는 문자열의 빠른 탐색을 위해 고안된 트리이다. 하나의 노드가 하나의 문자를 나타내도록 하여

문자열을 저장해나가는 것으로 검색할 문자열의 길이가 N 일 때, O(N)의 복잡도로 탐색을 마칠 수 있다.

하나의 문자열의 끝임을 표시하기 위해 문자열의 마지막 문자인 노드를 식별할 수 있도록 한다.

위 그림의 트라이는 문자열의 마지막 문자인 노드를 주황색으로 표시한 것이다.  위 트라이에 저장된 문자열은

be, bee, bean, app, apple, apart 의 6개가 된다.

 

 

2. 특징

  • 길의 N의 문자열을 삽입할 경우 O(N)의 시간복잡도로 삽입 가능

  • 길이 N의 문자열을 탐색할 경우 O(N)의 시간복잡도로 탐색 가능

  • 저장된 문자열 중 지금까지 입력한 문자열로 시작하는 모든 문자열을 파악할 수 있기 때문에 
    자동완성 기능의 구현에 사용됨

트라이의 삽입/탐색 연산은 굉장히 간단하기 때문에 구현 파트에서 주석으로 간단히 설명하고 넘어가기로 한다.

'CS > 자료구조' 카테고리의 다른 글

#14 해싱(Hashing)  (0) 2021.10.26
#13 트라이(Trie) 구현  (0) 2021.10.25
#11 트리(Tree) 5 - B-Tree  (0) 2021.10.18
#10 레드블랙 트리(Red-Black Tree) 구현  (0) 2021.10.14
#9 트리(Tree) 4 - 레드블랙 트리(Red-Black Tree)  (0) 2021.10.08

이전에 설명했던 자가균형 이진트리인 AVL 트리나 레드블랙 트리는 메모리상에서 데이터를 빠르게 삽입, 삭제하고

탐색하는데에는 충분한 성능을 보인다.  하지만 읽고 쓰는 대상이 메모리상의 데이터가 아닌 외부 저장장치가 되면

이야기는 달라진다.  기본적으로 외부 저장장치에 대한 입출력은 입출력의 단위인 버퍼의 크기 내에서는 데이터가

많든 적든 똑같은 속도를 보이며 이 속도는 기본적으로 굉장히 느리기때문에 메모리 내에서의 처리속도가 느려지더라도

입출력 횟수를 줄이는 쪽이 성능 개선으로 이어진다.  즉, 하나의 노드당 하나의 데이터와 2개의 자식노드만을 가질 수

있는 이진트리는 외부 저장장치에의 입출력을 고려하면 효율적이지 못한것이다.

 

 

1. 다원 탐색 트리(Multi-way Search Tree)

 이를 해결하기 위해 이진탐색트리와 동일하게 좌측 자식노드는 부모노드보다 키 값이 작고 우측 자식노드는

부모노드보다 키 값이 크지만 하나의 노드가 다수의 데이터와 2개보다 많은 자식노드를 가질 수 있도록 하는

다원 탐색 트리(Multi-way Search Tree, 이하 MST)를 사용할 수 있다. 

 

위 그림처럼 하나의 노드에 n개의 데이터가 들어간다면 자식노드는 n+1개까지 가질 수 있는 것이다.

 

 

2. B-Tree

 그런데 이진탐색트리의 문제점이 MST에서도 마찬가지로 발생한다.  균형이 어긋날 경우 탐색속도를 보장할 수

없다는 것이다. 필연적으로 MST에도 균형을 유지하도록 삽입, 삭제가 이루어지는 트리가 생겼다. 이것이 B-Tree 이다. 

B가 무엇을 의미하는지는 창시자가 따로 밝힌바가 없기에 알 수없지만 균형잡힌 MST이니 Balanced의 B라고 생각해도

좋을 것이다. 

 

 ① B-Tree 의 용어

  • 하나의 노드가 가질 수 있는 자식노드의 최대 갯수를 트리의 차수(degree)라고 한다.
  • 차수가 M 인 B-Tree 를 M차 B트리라고 한다.

 

 ② B-Tree 의 규칙 (M차 B트리)

  • 루트 노드는 최소 2개의 자식노드를 가져야한다.
  • 루트 노드를 제외한 모든 노드는 최소 floor(M/2) 개의 데이터를 가져야한다.
  • 모든 내부 노드는 데이터갯수+1 개의 자식노드를 가져야한다
  • 모든 노드는 최대 M 개의 자식노드만 가질 수 있다.
  • 모든 리프 노드는 같은 레벨이어야한다.
  • 노드 내의 데이터는 정렬된 상태여야한다.
  • 입력되는 자료는 중복될 수 없다.

 

 ③ B-Tree 의 특징

  • 자료의 삽입이 항상 리프 노드에서 이루어지며 트리가 아래로 뻗어나가는 것이 아닌 위로 자라는
    Bottom-up 방식이다.
  • 일반적으로 하나의 노드가 가질 수 있는 데이터의 갯수는 저장장치의 블록 크기와 유사하게 설정된다.
  • 항상 노드내에 데이터가 최소 반 이상은 채워져있기 때문에 블록(노드)단위의 입출력이 효율적이다.
  • 순차탐색을 위해서는 inorder 순회를 해야하기 때문에 순차탐색이 비효율적이다.

 

 

3.  B-Tree 의 삽입 연산

① 공통 부분

  • 트리가 비어있다면 루트노드를 할당.
  • 이진 탐색 트리와 같은 요령으로 삽입할 노드를 탐색

 

② Case 1. 분할이 발생하지 않는 경우

  • 단순히 삽입할 노드에 오름차순 정렬상태를 유지하도록 키 값 삽입

 

③ Case 2. 분할이 발생하는 경우

  • 삽입할 노드에 오름차순 정렬상태를 유지하도록 키 값 삽입
  • 노드에 들어있는 데이터 갯수가 한도를 넘어섰을 경우 노드의 중간값을 기준으로 노드를 반으로 분할
  • 분할의 기준이 된 중간값은 부모노드로 올려보낸다.  부모노드가 없을 경우 중간값을 새로운 루트 노드로 설정
  • 부모노드에 올라간 중간값으로 인해 부모노드가 데이터 갯수 한도를 넘겼을 경우 같은 방식으로 분할

 

 

4. B-Tree 의 삭제 연산

① 공통 부분

  • 트리가 비어있다면 종료
  • 이진 탐색 트리와 같은 요령으로 삭제할 노드를 검색
  • 삭제할 노드를 찾지못했다면 종료

 

② Case 1. 삭제할 키 값이 리프노드에 있고 해당 노드의 키 갯수가 최소 키 갯수보다 많을 경우

  • 단순히 노드에서 해당 데이터를 찾아서 삭제

 

③ Case 2. 삭제할 키 값이 리프노드에 있고 해당 노드의 키 갯수가 최소 키 갯수와 같으며
               인접한 형제노드 중 키 값을 빌려올 노드가 있을 경우

  • 노드에서 해당 데이터를 찾아서 삭제
  • 삭제로 인해 노드의 최소 키 갯수를 만족하지 못하게 됨
  • 왼쪽 형제노드중 최댓값 혹은 오른쪽 형제노드중 최솟값을 부모 key 값으로 올리고
    기존 부모 key 값을 가져와서 최소 키 갯수를 맞춤

 

④ Case 3. 삭제할 키 값이 리프노드에 있으며 해당 노드의 키 갯수가 최소 키 갯수와 같으며
               인접한 형제노드의 키 갯수가 모두 최소 키 갯수와 같을 경우 

  • 노드에서 해당 데이터를 찾아서 삭제
  • 삭제로 인해 노드의 최소 키 갯수를 만족하지 못하게 됨
  • 형제노드로부터 값을 빌려올 수 없기 때문에 한쪽 형제 노드와 부모key값, 해당노드를 하나의 노드로 병합
  • 병합을 위해 부모노드의 key 값 하나가 삭제되기 때문에 부모노드를 리프노드로 간주하고 Case1~3 의 작업을
    부모노드에 대해 수행해준다. 

 

⑤ Case 4. 삭제할 키 값이 내부노드에 있을 경우

  • 이진 탐색 트리때와 마찬가지로 좌측 서브트리중 최댓값 또는 우측 서브트리중 최솟값을 후임자로
    가져와 삭제할 데이터를 대체
  • 후임자 데이터는 리프노드의 값이기 때문에 리프노드에서의 삭제과정으로 이행한다.

 

5. B+Tree

 B+Tree 는 B-Tree의 개량버전으로 기본적으론 B트리와 거의 유사하지만 다음과 같은 차이점이 있다.

① 내부 노드에는 key 값만이 존재한다.

   B+Tree 는 B-Tree 와는 달리 내부 노드에는 데이터가 존재하지 않는다. 즉, 내부 노드는 데이터를 찾아가기

   위한 key값을 가질 뿐 실제 데이터는 모두 리프노드에 존재한다.  데이터를 저장하지 않는 덕분에 하나의

   Disk Block에 더 많은 노드를 저장할 수 있으며 결과적으로 key 탐색시에 읽어야할 Disk Block의 갯수가 

   줄어들어 B-Tree 보다 효율적인 탐색이 가능하다.

 

② 리프 노드끼리는 Linked List 형태로 연결되어있다.

   B+Tree의 리프 노드들은 서로 연결리스트 형태로 이어져있기 때문에 순차탐색의 효율이 B-Tree보다 뛰어나다.

   

 많은 파일시스템들이 블록 인덱싱을 위해 B+트리를 사용하며 데이터베이스에서도 테이블 인덱싱을 위해

 B+트리가 종종 사용된다.

1. ADT 작성

RBTree:
    Datas:
        __root : 트리의 루트노드
        __size : 트리의 크기

    Operations:
        insert(key) : 키 값이 key인 노드를 트리에 삽입
        delete(key) : 키 값이 key인 노드를 트리에서 제거. 성공할 경우 True, 실패할 경우 False 반환
        get(key) : 키 값이 key 인 노드를 트리에서 탐색하여 해당 노드의 데이터를 반환.
        
RBTree.__Node:
    Datas:
    	key : 노드의 키 값
        color : 노드의 색상 (0: 검은색, 1: 붉은색)
        parent : 부모노드
        left : 좌측 자식노드
        right : 우측 자식노드
        IS_NIL : NIL 노드 여부
    Operations: -

 

 

2. 구현

# 레드블랙 트리 클래스
class RBTree:
    # 노드 클래스
    class __Node:
    	# 노드 생성자
        # 기본적으로 NIL 노드로 생성된다
        def __init__(self, p=None):
            # 키값은 None, 색은 0(검은색)
            self.key = None
            self.color = 0

            # 부모노드
            self.parent = p

            # 좌측 자식노드, 우측 자식노드는 None
            self.left = None
            self.right = None

            # NIL 여부 True
            self.IS_NIL = True

    # 트리 생성자
    def __init__(self):
        # 루트노드에 NIL 노드 세팅
        self.__root = self.__Node()

        # 트리의 크기 0으로 초기화
        self.__size = 0

    # len 함수의 결과를 구현
    def __len__(self):
        # 트리의 크기 반환
        return self.__size

    # 데이터 삽입 함수
    def insert(self, key):
        # 삽입할 위치 탐색
        cursor = self.__root
        while not cursor.IS_NIL:
            # 현재 노드보다 키 값이 크다면 우측 자식노드로 이동
            if cursor.key < key:
                cursor = cursor.right
            # 현재 노드보다 키 값이 작다면 좌측 자식노드로 이동
            elif cursor.key > key:
                cursor = cursor.left
            # 이미 키 값이 존재할 경우 삽입 종료(삽입안함)
            else:
                return False

        # 삽입 위치의 NIL 노드에 key, color, 좌측 자식노드, 우측 자식노드를 세팅하고 NIL 여부를 False 로 한다
        cursor.key = key
        cursor.color = 1
        cursor.left = self.__Node(cursor)
        cursor.right = self.__Node(cursor)
        cursor.IS_NIL = False

        # 트리 크기 1 증가
        self.__size += 1

        # 루트노드의 색은 검은색
        self.__root.color = 0

        # insert_fix 를 수행하여 RB 트리의 규칙을 유지
        self.__insert_fix(cursor)

    # 삽입 이후 규칙에 맞게 트리를 수정하는 함수
    def __insert_fix(self, node):
        parent = node.parent
        # 부모노드가 존재하고 붉은색인 동안 반복
        # 루트노드는 검은색이기 떄문에 부모노드가 붉은색이면 반드시 조부모 노드가 존재
        while parent and parent.color == 1:
            # 조부모노드
            grand_parent = parent.parent

            # 부모노드와 노드가 어느쪽 자식노드인지 확인
            # True: 좌측 / False: 우측
            parent_direction = (grand_parent.left == parent)
            node_direction = (parent.left == node)

            # 삼촌노드
            uncle_node = grand_parent.right if parent_direction else grand_parent.left

            # 케이스 1. Recoloring
            # 삼촌 노드가 붉은색인 경우
            if uncle_node.color == 1:
                # 삼촌노드와 부모노드를 모두 검은색으로 변경
                uncle_node.color = parent.color = 0

                # 조부모노드를 붉은색으로 변경
                grand_parent.color = 1

                # 조부모노드를 삽입노드로 하여 fix 를 다시 수행
                node = grand_parent
                parent = node.parent
                continue

            # 케이스 2. Restructuring
            # 삼촌 노드가 검은색인 경우
            else:
                # 부모노드와 노드가 서로 다른 방향의 자식노드인 경우(LR, RL 형태)
                if node_direction != parent_direction:
                    # LR 형태인 경우 LL 형태로 변형
                    if parent_direction:
                        self.__left_rotation(parent)

                    # RL 형태인 경우 RR 형태로 변형
                    else:
                        self.__right_rotation(parent)

                    # 회전에 의해 parent 와 node 가 뒤바뀜
                    node, parent = parent, node

                # LL 형태인 경우 조부모노드에 대해 right_rotation
                if parent_direction:
                    self.__right_rotation(grand_parent)
                # RR 형태인 경우 조부모노드에 대해 left_rotation
                else:
                    self.__left_rotation(grand_parent)

                # 부모노드가 된 parent 노드의 색을 검은색으로, 나머지 두 노드는 붉은색으로 한다
                parent.color = 0
                grand_parent.color = 1
                node.color = 1

                # Restructuring 은 추가작업을 필요로하지 않음
                break

        # 루트노드는 항상 검은색
        self.__root.color = 0

    # 좌측 회전 함수
    def __left_rotation(self, node):
        if node.IS_NIL or node.right.IS_NIL:
            return

        parent = node.parent
        right_tmp = node.right

        node.right = right_tmp.left
        right_tmp.left.parent = node

        right_tmp.left = node
        node.parent = right_tmp

        right_tmp.parent = parent
        if parent:
            if node == parent.left:
                parent.left = right_tmp
            else:
                parent.right = right_tmp
        else:
            self.__root = right_tmp

    # 우측 회전 함수
    def __right_rotation(self, node):
        if node.IS_NIL or node.left.IS_NIL:
            return

        parent = node.parent
        left_tmp = node.left

        node.left = left_tmp.right
        left_tmp.right.parent = node

        left_tmp.right = node
        node.parent = left_tmp

        left_tmp.parent = parent
        if parent:
            if node == parent.left:
                parent.left = left_tmp
            else:
                parent.right = left_tmp
        else:
            self.__root = left_tmp

    # 데이터 삭제 함수
    def delete(self, key):
        # 삭제할 노드 탐색
        target = self.__search(key)

        # 삭제할 노드를 찾지 못한 경우
        if not target:
            return False

        # 삭제 후 fix 를 위한 변수
        child, s_color = None, None

        # target 이 리프노드인 경우
        if target.left.IS_NIL and target.right.IS_NIL:
            child, s_color = target, target.color
            target.key = None
            target.left = target.right = None
            target.IS_NIL = True
            target.color = 0

        # 좌측 자식노드를 가진 경우
        elif not target.left.IS_NIL:
            # 좌측 서브트리중 가장 오른쪽의 노드를 구한다
            successor = target.left

            while not successor.right.IS_NIL:
                successor = successor.right

            # successor 의 좌측 자식노드와 색상 저장
            child, s_color = successor.left, successor.color

            # 삭제할 노드의 키값을 successor 의 키값으로 변경
            target.key = successor.key

            # successor 가 target 의 좌측 자식노드인 경우
            if successor == target.left:
                # successor 의 부모노드의 좌측 자식노드를 successor 의 좌측 자식노드로 설정
                successor.parent.left = successor.left

            # successor 가 target 의 좌측 자식노드가 아닌 경우
            else:
                # successor 의 부모노드의 우측 자식노드를 successor 의 좌측 자식노드로 설정
                successor.parent.right = successor.left

            # successor 의 좌측 자식노드의 부모노드를 successor 의 부모노드로 설정
            successor.left.parent = successor.parent

        # 우측 자식노드만 가진 경우
        else:
            # 우측 서브트리중 가장 왼쪽의 노드를 구한다
            successor = target.right
            while not successor.left.IS_NIL:
                successor = successor.left

            # successor 의 우측 자식노드와 색상 저장
            child, color = successor.right, successor.color

            # 삭제할 노드의 키값을 successor 의 키값으로 변경
            target.key = successor.key

            # successor 가 target 의 우측 자식노드인 경우
            if successor == target.right:
                # successor 의 부모노드의 우측 자식노드를 successor 의 우측 자식노드로 설정
                successor.parent.right = successor.right

            # successor 가 target 의 우측 자식노드가 아닌 경우
            else:
                # successor 의 부모노드의 좌측 자식노드를 successor 의 우측 자식노드로 설정
                successor.parent.left = successor.right

            # successor 의 우측 자식노드의 부모노드를 successor 의 부모노드로 설정
            successor.right.parent = successor.parent

        # 트리 크기 1 감소
        self.__size -= 1

        # 삭제이후 fix 과정
        # 트리가 비어있지 않은 경우
        if child.parent:
            # successor 가 검은색이었던 경우
            if s_color == 0:
                # child 는 붉은색인 경우
                if child.color == 1:
                    child.color = 0

                # child 도 검은색인 경우
                else:
                    self.__delete_fix(child)
        return True

    # 삭제 이후 규칙에 맞게 트리를 수정하는 함수
    def __delete_fix(self, child):
        # child 의 부모 노드
        parent = child.parent

        while parent:
            # True 일 경우 child 는 parent 의 좌측 자식노드 False 일 경우 우측 자식노드
            child_direction = (child == parent.left)

            # 형제노드
            sibling = parent.right if child_direction else parent.left

            # 조카노드
            n1, n2 = sibling.left, sibling.right

            # parent 가 붉은색인 경우
            if parent.color == 1:
                # 케이스 1. sibling, n1, n2 가 모두 검은색인 경우
                if sibling.color == n1.color == n2.color == 0:
                    # parent 와 sibling 의 색을 교환하고 종료
                    parent.color, sibling.color = sibling.color, parent.color
                    break

            # parent 가 검은색인 경우
            else:
                # 케이스 2. sibling, n1, n2도 모두 검은색인 경우
                if sibling.color == n1.color == n2.color == 0:
                    # sibling 의 색을 붉은색으로 바꾼 뒤 child 를 parent 로,
                    # parent 를 parent 의 부모노드로 하여 continue
                    sibling.color = 1
                    child, parent = parent, parent.parent
                    continue

                # 케이스 3. sibling 은 붉은색, n1, n2는 검은색인 경우
                elif sibling.color == 1 and n1.color == n2.color == 0:
                    # parent 와 sibling 의 색을 교환
                    parent.color, sibling.color = sibling.color, parent.color

                    # child 노드의 방향에 따라 회전 수행
                    if child_direction:
                        self.__left_rotation(parent)
                    else:
                        self.__right_rotation(parent)
                    continue

            # parent 의 색에 무관한 경우
            # sibling 의 색이 검은색인 경우
            if sibling.color == 0:
                # 가까운 조카노드가 n1, 먼 조카노드가 n2가 되도록 한다
                if not child_direction:
                    n1, n2 = n2, n1

                # 케이스 4. 먼 조카노드 n2가 붉은색인 경우
                if n2.color == 1:
                    # parent 와 sibling 의 색을 교환하고 n2의 색을 검은색으로 변경
                    parent.color, sibling.color = sibling.color, parent.color
                    n2.color = 0

                    # child 노드의 방향에 따라 회전 수행
                    if child_direction:
                        self.__left_rotation(parent)
                    else:
                        self.__right_rotation(parent)
                    break

                # 케이스 5. 가까운 조카노드 n1이 붉은색이고 먼 조카노드 n2가 검은색인 경우
                if n1.color == 1 and n2.color == 0:
                    # sibling 과 n1의 색을 교환
                    sibling.color, n1.color = n1.color, sibling.color

                    # child 노드의 방향에 따라 회전 수행
                    if child_direction:
                        self.__right_rotation(sibling)
                    else:
                        self.__left_rotation(sibling)
                    continue

        # 루트노드의 색은 항상 검은색
        self.__root.color = 0

    # 키 값이 key 인 노드의 데이터를 반환하는 함수
    # 여기서 노드에는 데이터 값이 따로 없기 때문에 키 값을 반환
    # 노드를 찾을 수 없다면 None 반환
    def get(self, key):
        target = self.__search(key)
        if target:
            return target.key
        else:
            return None

    # 키 값이 key인 노드를 반환하는 함수
    def __search(self, key):
        # 루트 노드부터 탐색 시작
        cursor = self.__root
        while not cursor.IS_NIL:
            # 현재 노드의 키값보다 key 가 더 크다면 우측 자식노드로 이동
            if cursor.key < key:
                cursor = cursor.right
            # 현재 노드의 키값보다 key 가 더 작다면 좌측 자식노드로 이동
            elif cursor.key > key:
                cursor = cursor.left
            # key 에 해당하는 노드를 찾았다면 노드반환
            else:
                return cursor

        # 찾지 못했을 경우 None 반환
        return None

    # 트리를 중위순회로 출력하는 함수. 
    # 붉은 노드가 연속으로 붙어있지 않은지 체크
    def in_order(self):
        self._dfs(self.__root, 0, 0)

    def __dfs(self, node, bcnt, pre):
        if node.color == 0:
            bcnt += 1
        if not node.left.IS_NIL:
            self._dfs(node.left, bcnt, node.color)
        print(node.key, ':', bcnt, ':color=', node.color, "invalid" if pre == node.color == 1 else "valid")
        if not node.right.IS_NIL:
            self._dfs(node.right, bcnt, node.color)
  • 최소한의 기능인 insert, delete, get 과 테스트용 inorder 함수만을 구현
  • 그 외의 함수나 멤버변수는 사용자측에선 볼 수 없도록 private 로 선언

'CS > 자료구조' 카테고리의 다른 글

#12 트리(Tree) 6 - 트라이(Trie)  (0) 2021.10.25
#11 트리(Tree) 5 - B-Tree  (0) 2021.10.18
#9 트리(Tree) 4 - 레드블랙 트리(Red-Black Tree)  (0) 2021.10.08
#8 트리(Tree) 3 - AVL 트리  (0) 2021.10.07
#7 트리(Tree) 2 - 힙(Heap)  (0) 2021.10.06

1. 레드블랙 트리(Red-Black Tree)

 레드블랙 트리는 지난번에 다루었던 AVL 트리와 같은 자가 균형 이진 탐색 트리의 일종이다. 레드블랙 트리는

다음과 같은 조건을 만족한다.

  • 모든 노드는 색을 가지고있으며 색은 붉은색 또는 검은색 중 하나이다.
  • 루트 노드는 검은색이다.
  • 모든 리프 노드(NIL)는 검은색이다.
  • 붉은색 노드의 자식 노드는 검은색이다. => 붉은색 노드는 연속해서 나올 수 없다.
  • 모든 리프노드에서 Black Depth가 같다. 
    => 리프 노드에서 루트 노드까지 거슬러올라가며 만나는 블랙노드의 갯수가 모두 동일하다.

위 조건들을 만족함으로서 레드블랙 트리는 아주 중요한 특성을 가지게 된다. 모든 리프노드의 Black Depth가

같다면 그 사이에 붉은색 노드를 아무리 많이 끼워넣는다 해도 붉은색 노드는 연속으로 나올 수 없기 때문에

넣을 수 있는 붉은색 노드의 갯수는 (검은색 노드의 갯수 - 1) 개가 한계이다. 즉, 모든 리프노드의 깊이는

가장 얕은 리프노드의 깊이의 두 배를 넘을 수 없다.  이 특성 덕분에 AVL트리만큼은 아니어도 레드 블랙 트리는

상당히 균형잡힌 이진 탐색 트리가 된다.

 

2. 레드블랙 트리의 특징

  • AVL 트리와 마찬가지로 어떤 경우에도 삽입, 삭제, 검색에 O(logN)의 시간복잡도를 보장한다.
  • 매 삽입/삭제마다 최악의 경우 많은 회전 연산이 발생하는 AVL 트리에 비해 삽입/삭제에 걸리는 시간이
    비교적 적다.
  • 많은 프로그래밍 언어의 해시맵이나 집합 등의 라이브러리를 구현하는데에 레드블랙 트리가 활용된다.

 

3. 삽입/삭제시 Double-Red 처리 알고리즘

 레드블랙 트리는 삽입, 삭제 결과 발생한 규칙의 어긋남을 회전과 색변경을 통해 바로잡는다.   회전의 경우 AVL 트리에

사용했던 LL회전(right_rotation), RR회전(left_rotation)을 그대로 사용한다.  

 

① 삽입

 삽입 연산의 경우 문제의 발생여부를 아는것은 굉장히 간단하다. 삽입되는 노드는 기본적으로 붉은색 노드이기 때문에

삽입된 노드의 부모노드도 붉은색이라면 Double-Red 문제가 발생한다. 그리고 이 상태에서 문제해결은 삽입된 노드의
삼촌노드(부모 노드의 형제노드)의 색에 따라 두 가지 케이스로 나누어 진행된다.

  • Recoloring
    • 삼촌노드의 색이 붉은색일 경우 발생
    • 삼촌노드와 부모노드의 색을 모두 검은색으로 변경해준 다음 조부모노드(부모노드의 부모노드)의 색을 붉은색으로 변경해준다. 부모노드와 삼촌노드쪽 모두 검은색노드가 하나 늘어난 동시에 조부모노드가 붉은색이 되며
      일괄적으로 하나씩 줄었기 때문에 balck depth에는 영향을 주지않는다.
    • 다만 조부모 노드가 붉은색으로 바뀌면서 추가적으로 Double-Red 문제가 발생할 수 있기 때문에 조부모노드를
      새로 삽입한 노드로 취급하여 DoubleRed 처리를 재차 실행한다.
    • 즉, Recoloring은 한번 수행하고나서도 추가작업이 필요할 수 있다.
  • Restructuring
    • 삼촌노드의 색이 검은색일 경우 발생
    • 조부모노드 - 부모노드 - 삽입된 노드의 형태에 따라 회전 연산을 수행
    • LL 상태라면 조부모노드에 대해 right_rotation 수행
      RR 상태라면 조부모노드에 대해 left_rotation 수행
      LR 상태라면 부모노드에 대해 left_rotation 을 수행한 뒤 조부모노드에 대해 right_rotation 수행
      RL 상태라면 부모노드에 대해 right_rotation 을 수행한 뒤 조부모노드에 대해 left_rotation 수행
    • Restructuring 의 경우 이 작업만으로 더이상의 추가적인 Double-Red 문제가 발생하지 않기 때문에
      여기서 작업이 종료된다.
  • 모든 작업이 종료되면 루트노드를 검은색으로 바꿔준다.

 

② 삭제

 삭제연산은 조금더 복잡하다. 일반적인 이진탐색의 삭제연산의 경우 삭제할 노드의 좌측 서브트리중 최댓값 또는 
우측 서브트리중 최솟값을 가져와 삭제된 노드를 대체하는 형태로 이뤄진다.  레드블랙트리는 그렇게 삭제가 이뤄진 후 

규칙을 유지하기 위해 추가작업을 수행한다.  먼저 삭제된 노드 부분에는 문제가 발생하지 않는다.  삭제된 노드를
대체할 후임자 노드의 색을 삭제된 노드의 색으로 바꿔주면 되기 때문이다.  문제는 후임자 노드의 자리에서 발생한다.

삭제된 노드가 리프노드일 경우에는 삭제된 노드 자리를 대체한 NIL 노드가 C 노드가 되고 그 부모노드가 P 노드가

된다. C노드의 부모노드가 없는 경우에는 트리가 비어있는 상태이기 때문에 그대로 삭제연산을 종료한다.)

  • 후임자 노드가 붉은색일 경우
    • 후임자 노드가 붉은색이라면 사라지더라도 규칙에 아무 영향을 주지않는다.
  • 후임자 노드가 검은색이고 후임자 노드의 한쪽 자식노드가 붉은색인 경우
    • 후임자 노드가 검은색이어도 후임자 노드의 자식노드가 붉은색이라면 그 노드를 검은색으로 바꿔주면
      문제가 간단히 해결된다.

  • 후임자 노드와 후임자 노드의 한쪽 자식노드 모두 검은색인 경우
    • 이 경우가 가장 복잡한 상황이다. 이 경우 후임자 노드의 한쪽 자식노드 C를 기준으로 그 부모노드 P,
      형제노드 S, 가까운 조카노드 N1먼 조카노드 N2 의 상태를 기준으로 다섯가지 케이스로 나누어
      해결해나가야 한다. 여기서는 C가 P의 좌측 자식노드이고 S가 P의 우측 자식노드인 경우를 상정하여
      설명한다. 만약 반대로 C가 P의 우측 자식노드인 경우에는 회전 방향을 반대로 해야한다.

    • 케이스 1. P는 붉은색, S, N1, N2는 모두 검은색인 경우
      • P와 S의 색을 서로 맞바꾸는 것만으로 더이상의 추가작업 없이 간단히 해결할 수 있다.
      • 다섯가지 케이스중 가장 간단한 케이스이다.

    • 케이스 2. P, S, N1, N2 가 모두 검은색인 경우
      • S의 색을 붉은색으로 변경하는 것으로 C쪽과 S쪽 모두 검은색 노드가 하나씩 부족하도록 한다.
      • 결과적으로 부모노드 P 기준으로 검은색노드가 하나 부족하게되어 P 노드에 문제를 떠넘길 수 있다.
      • C 를 P로, P를 P의 부모노드로 재설정하여 다시한번 해당하는 케이스를 찾아 작업을 진행하도록 한다

    • 케이스 3. P, N1, N2는 검은색이고 S는 붉은색인 경우
      • P를 기준으로 left_rotation 을 수행한 뒤 P와 S의 색을 맞바꾼다. P의 색이 바뀌었기 때문에 바뀐 색상에
        따라 다시한번 해당 케이스를 찾아 작업을 진행하도록 한다.

    • 케이스 4. P의 색은 무관, S가 검은색이고 먼 조카노드 N2가 붉은색인 경우
      • P를 기준으로 left_rotation 을 수행한 뒤 P와 S의 색을 맞바꾼 뒤 먼 조카노드 N2를 검은색으로 변경한다.

    • 케이스 5. P의 색은 무관, S가 검은색이고 가까운 조카노드 N1은 붉은색, 먼 조카노드 N2는 검은색인 경우
      • S를 기준으로 right_rotation 을 수행한 뒤 가까운 조카노드 N1과 S의 색을 맞바꾼다.
      • 이 결과 케이스 4와 동일한 형태가 되니 계속해서 작업을 진행한다.

    • 위 작업을 케이스 1 또는 케이스 4 작업을 수행하여 추가작업이 필요없어지거나 C가 루트노드에 도달하여
      parent 노드가 존재하지 않을 때 까지 반복한다.

    • 모든 작업이 끝나면 루트노드를 검은색으로 바꿔준다.

 

글을 작성하면서 레드블랙트리를 직접 구현해보았지만 적은 양의 데이터로 하나하나 삽입, 삭제를 수행했을 때는

정상적으로 작동하는 것으로 보였지만 대량의 데이터를 삽입/삭제 해보니 삭제연산중에 문제가 있어 오류가 발생하는

경우가 나타났다. 나중에 시간이 되면 처음부터 다시한번 구현해볼 필요가 있을 것 같다.

 

추가) 2021.10.13

 좀더 알아보니 모든 노드가 좌우 자식노드로 검은색 NIL 노드를 가지도록 설계해야 구현이 쉬울 것으로 보여 설계를

처음부터 다시해보았다. 노드를 삽입할 때 삽입위치인 NIL 노드에 key값과 색상을 설정하고 좌우에 NIL 노드를 생성하여 붙이도록 했더니 삭제기능도 문제없이 작동하였다. 

 

1. AVL 트리

 이진 탐색 트리를 활용한 데이터의 탐색은 분명 O(logN) 까지의 성능을 보일 수 있지만 트리가 한 방향으로 치우쳐

생성될 경우 최악의 경우 O(N) 까지 성능이 떨어질 수 있다.  반대로 이진 탐색 트리가 항상 균형 이진 트리가 되도록

할 수 있다면 항상 O(logN)의 성능을 보장할 수 있을 것이다.  AVL 트리는 삽입, 삭제가 이뤄져도 항상 균형 상태를

유지하는 자가 균형 이진 탐색 트리이다. 

 

 

2. AVL 트리의 특징

  • 어떤 노드를 기준으로 하더라도 좌, 우 서브트리의 높이(깊이)가 2 이상의 차이를 보이지 않는다.
  • 노드의 삽입/삭제가 발생할 때마다 매번 서브트리의 회전을 통해 균형을 맞춘다.
  • 균형을 거의 완벽하게 유지하기 때문에 탐색속도는 빠르지만 삽입/삭제의 속도가 이후에 설명할
    Red-black 트리에 비해 느린편이다.
  • 삽입/삭제/탐색 모두 O(logN)을 보장한다.

 

3. 회전 알고리즘

 ① LL 회전

  • 위 그림과 같이 기준이 되는 루트노드(1)의 좌측 서브트리와 우측 서브트리의 높이차이가 1보다 크고
    좌측 자식 노드 기준으로 좌측 서브트리의 높이가 우측 서브트리의 높이보다 큰 상태를 LL상태라고 한다.
  • LL 회전은 LL 상태에서 일어난다.

 

  • 먼저 루트 노드(1)의 왼쪽 자식노드를 왼쪽 자식노드(2)의 오른쪽 자식노드(null) 로 한다. 

 

  • 원래 왼쪽 자식노드였던 2번 노드의 오른쪽 자식노드를 루트노드였던 1로 한다.

 

 ② RR 회전

  • 위 그림과 같이 기준이 되는 루트노드(1)의 우측 서브트리와 좌측 서브트리의 높이차이가 1보다 크고
    우측 자식 노드 기준으로 우측 서브트리의 높이가 좌측 서브트리의 높이보다 큰 상태를 RR상태라고 한다.
  • RR 회전은 RR 상태에서 일어난다.

 

  • 먼저 루트 노드(1)의 오른쪽 자식노드를 오른쪽 자식노드(2)의 왼쪽 자식노드(null) 로 한다. 

 

  • 원래 오른쪽 자식노드였던 2번 노드의 왼쪽 자식노드를 루트노드였던 1로 한다.

 

 ③ LR 회전

  • 위 그림과 같이 루트노드 기준 좌측 서브트리 높이가 우측 서브트리보다 2이상 높고 좌측 자식노드 기준
    우측 서브트리의 높이가 좌측 서브트리보다 높은 상태를 LR 상태라고 한다.
  • LR 회전은 LR 상태에서 일어난다.
  • LL, RR 회전을 알고있다면 여기서부터는 간단하다. 루트노드(1)의 좌측 자식노드(2)를 기준으로 RR 회전을
    실행한 뒤, 루트 노드(1)를 기준으로 LL 회전을 실행해주면 된다.

 

 ④ RL 회전

  • 위 그림과 같이 루트노드 기준 우측 서브트리 높이가 좌측 서브트리보다 2이상 높고 우측 자식노드 기준
    좌측 서브트리의 높이가 우측 서브트리보다 높은 상태를 RL 상태라고 한다.
  • RL 회전은 RL 상태에서 일어난다.
  • LR 회전과 반대로 루트노드(1)의 우측 자식노드(2)를 기준으로 LL 회전을 실행한 뒤, 루트노드(1)를 기준으로
    RR 회전을 실행해주면 된다.

 

4. AVL 트리의 연산

  • 삽입/삭제(Insert, Delete)
    • 이진 탐색 트리의 방식대로 데이터를 삽입/삭제한다.
    • 루트 노드부터 시작하여 균형 재조정함수를 호출하여 균형을 재조정한다.
  • 균형 재조정(Rebalance)
    • 루트 노드로부터 시작
    • 좌측 서브트리에 대해 균현 재조정 함수 재귀호출
    • 우측 서브트리에 대해 균형 재조정 함수 재귀호출
    • 좌측 서브트리와 우측 서브트리의 높이를 구한다.
    • 만약 두 서브트리의 높이차이가 2 이상이라면 현재 루트노드를 기준으로 트리가 어느 상태인지 파악한다.
    • 각 상태에 맞는 회전(LL, RR, LR, RL)을 실행한다.
    • 루트 노드를 환한다.

1. 힙(Heap)

 힙은 최댓값, 최솟값의 탐색을 빠르게 하기 위해 고안된 완전 이진 트리를 기반으로 하는 자료구조이다.  

힙은 다음과 같은 조건을 만족한다.

  • 어떤 노드 A의 키 값은 부모노드 B의 키 값과 대소관계를 가진다
  • 형제노드 간에는 대소관계를 따지지 않는다.

 

2.  힙의 특징

  • 부모노드의 키 값이 자식노드의 키 값 보다 항상 크다면 최대 힙, 항상 작다면 최소 힙이라고 한다.
  • 최대 힙은 최댓값이, 최소 힙은 최솟값이 루트 노드가 되는 상태를 항상 유지한다.
  • 힙의 종류에 따라 트리의 차수가 2보다 큰 경우도 있지만 대부분의 경우 힙이라고 하면 이진 힙을 가리킨다.
  • 데이터의 삽입에 O(logN), 최댓값 혹은 최솟값 탐색에 O(1)의 시간복잡도를 보인다.
  • 그 특성상 우선순위 큐 등의 자료구조를 구현하는데 사용할 수 있다.
  • 정렬 알고리즘 중 하나인 힙 정렬에도 사용되는데, 내림차순 정렬에는 최대 힙을, 오름차순 정렬에는 최소힙을
    사용한다.
  • 힙은 완전이진트리이기 때문에 일반적으로 배열로 구현된다. 루트노드의 인덱스는 0이며 어떤 노드의 인덱스가
    i일 때 왼쪽 자식노드는 i * 2 + 1, 오른쪽 자식노드는 i * 2 + 2 가 된다.

 

3. 힙의 연산(최소 힙 기준)

  • 삽입(push)
    • 데이터를 배열의 맨 끝에 삽입한다.
    • 데이터가 삽입된 인덱스로부터 시작하여 부모노드가 존재하고 부모노드의 값이 자신보다 크다면
      부모 노드와 위치를 뒤바꾸는 작업을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
  • 삭제(pop)
    • 배열의 맨 끝의 데이터를 맨 처음의 데이터에 덮어씌운다.
    • 삽입과는 반대로 자신보다 값이 작은 자식노드가 있다면 자식노드와 위치를 뒤바꾼다.
      양측 자식노드 모두 자신보다 작다면 둘 중 보다 작은 쪽과 뒤바꾼다.
    • 위 작업을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
  • 힙 변환(heapify)
    • 루트노드가 0이고 배열의 길이가 n인 힙이 아닌 배열을 힙으로 변환
    •  i = n//2-1 부터 탐색시작, 좌측 자식노드인 i * 2 + 1, 우측 자식노드인 i * 2 + 2 와 비교
    • 만약 자식노드중 자신보다 작은 것이 있다면 자식노드와 위치를 뒤바꾼다.
    • 위치변경이 발생했다면 위치를 바꾼 대상 인덱스를 기준으로 다시 탐색
    • 위치변경이 발생하지 않았다면 i-1을 탐색
    • i >= 0 일 동안 위 작업을 반복
  • 힙 변환(heapify) 코드
from heapq import heappop


def heapify(arr, cur):
    # 좌, 우 자식노드
    left, right = cur * 2 + 1, cur * 2 + 2

    # 위치를 바꿀 대상 => 자기 자신으로 초기화
    target = cur

    # 좌측 자식노드가 존재하고 현재 위치 변경 대상보다 키 값이 작을 경우
    # 위치 변경 대상을 좌측 자식노드로 갱신
    if left < len(arr) and arr[left] < arr[target]:
        target = left

    # 우측 자식노드가 존재하고 현재 위치 변경 대상보다 키 값이 작을 경우
    # 위치 변경 대상을 우측 자식노드로 갱신
    if right < len(arr) and arr[right] < arr[target]:
        target = right

    # 자기 자신이 아닌 위치 변경 대상을 찾았다면
    # 위치를 변경하고 변경된 위치에 대해 heapify 재귀호출
    if cur != target:
        arr[cur], arr[target] = arr[target], arr[cur]
        heapify(arr, target)


# 힙이 아닌 배열
a = [1, 5, 2, 3, 7, 4, 6]

# len(a)//2-1 부터 0까지의 노드에 대해 heapify 호출
for i in range(len(a) // 2 - 1, -1, -1):
    heapify(a, i)

# 힙 출력
# 결과: [1, 3, 2, 5, 7, 4, 6]
print(a)

# 힙이 정상적으로 만들어졌는지 확인
# 결과: 1, 2, 3, 4, 5, 6, 7
for _ in range(len(a)):
    print(heappop(a), end=" ")

 => heapify 와 heappop 을 구현하는 것 만으로 힙 정렬을 구현할 수 있다.  heapify가 거의 O(N)에 가까운 성능을

      보이며 heappop 이 O(logN)의 성능을 보이기 때문에 힙 정렬은 N개의 데이터에 대해 O(NlogN)의 성능을 보인다.

'CS > 자료구조' 카테고리의 다른 글

#9 트리(Tree) 4 - 레드블랙 트리(Red-Black Tree)  (0) 2021.10.08
#8 트리(Tree) 3 - AVL 트리  (0) 2021.10.07
#6 트리(Tree) 1 - 트리의 개념/이진 트리  (0) 2021.10.04
#5 그래프(Graph)  (0) 2021.10.01
#4 큐(Queue)  (0) 2021.09.28

1. 트리(Tree)

 트리는 그래프(Graph)와 유사한 형태를 가지며 어떤 의미로는 그래프의 일종이라고 볼 수도 있다.  

다만 모든 노드가 동등한 관계였던 그래프와는 달리 트리의 노드는 서로 부모/자식의 관계를 가진다. 

아래 예시를 보며 좀더 자세히 알아보자.

 

  • 부모 노드를 가지지 않는 노드를 루트(root) 노드 라고 한다.

  • 루트 노드를 제외한 모든 노드는 한 개의 부모 노드를 가진다.(두 개 이상의 부모 노드를 가질 수 없다)

  • 자식 노드를 가지지 않는 노드들을 리프(leaf) 노드 라고 한다.

  • 리프 노드를 제외한 모든 노드는 한 개 이상의 자식 노드를 가진다.
  • 어떤 노드의 자식노드를 루트로 하는 트리를 그 노드의 서브 트리(subtree)라고 한다.

  • 어떤 노드가 가지는 자식 노드의 갯수(혹은 서브트리의 갯수)를 노드의 차수(degree) 라고 한다.
    트리 전체의 차수는 노드들의 차수 중 가장 큰 값이 된다.

  • 루트 노드로부터 어떤 노드 까지 거쳐야하는 간선의 갯수를 그 노드의 깊이(depth) 라고 한다.
    루트 노드의 깊이는 0이다.

  • 서로 깊이가 같은 노드들의 집합을 레벨(level) 이라고 한다. 위 트리에서의 레벨 1에 해당하는 노드는
    3, 2, 0 이 있다.

 

2. 트리의 표현

  • 배열을 사용한 트리의 표현
    • arr[0] 을 루트 노드로 한다
    • 노드 arr[i] 의 좌측 자식 노드는 arr[i * 2 + 1], 우측 자식 노드는 arr[i * 2 + 2] 에 저장된다.
    • 특수한 트리가 아니면 메모리의 낭비가 매우 심하다.
    • 완전 이진 트리를 나타내는 경우라면 빈 공간이 없고 자식 노드를 가리키기 위한 포인터가
      필요하지 않기 때문에 효율적이다.

  • 연결 리스트를 사용한 트리의 표현
    • 자기 자신의 데이터와 좌측, 우측 자식노드를 가리키는 포인터를 가지는 노드 간의 연결로 표현한다.
    • 정확히 노드의 수 만큼만 메모리를 차지하기 때문에 대부분의 경우 배열을 사용한 방식보다
      메모리 효율이 좋다.
    • 특정 노드에의 접근이나 트리의 순회 등은 배열을 사용한 방식에 비해 느리다.

 

3. 트리의 순회(Traversal)

 트리의 순회방법 네 가지에 대해 알아본다.  모든 순회는 루트 노드로부터 시작한다.

1) 전위 순회(Preorder Traversal)

  • 절차
    ① 현재 노드를 탐색
    ② 좌측 자식 노드로 이동하여 해당 절차를 수행
    ③ 우측 자식 노드로 이동하여 해당 절차를 수행

  • 결과
     4 - 2 - 3 - 5 - 7 - 1 - 9 - 8 - 6
  • 순서의 맨 앞이 항상 루트 노드를 가리킨다.
  • 일반적인 깊이 우선 탐색이 이와 같은 순서를 보인다.

 

2) 후위 순회(Postorder Traversal)

  • 절차
    ① 좌측 자식 노드로 이동하여 해당 절차를 수행
    ② 우측 자식 노드로 이동하여 해당 절차를 수행
    ③ 현재 노드를 탐색

  • 결과
     5 - 7 - 3 - 9 - 8 - 1 - 2 - 6 - 4
  • 순서의 맨 뒤가 항상 루트 노드를 가리킨다.

 

3) 중위 순회(Inorder Traversal)

  • 절차
     좌측 자식 노드로 이동하여 해당 절차를 수행
    현재 노드를 탐색
    우측 자식 노드로 이동하여 해당 절차를 수행

  • 결과
     5 - 3 - 7 - 2 - 9 - 1 - 8 - 4 - 6
  • 루트보다 먼저 방문한 쪽은 좌측 서브트리에, 나중에 방문한 쪽은 우측 서브트리에 속한다
  • 이진 탐색 트리를 중위 순회 할 경우 노드들을 오름차순 정렬한 순서로 방문하게 된다.

 

4) 레벨 순회(Level-order Traversal)

  • 절차
    현재 레벨의 모든 노드를 좌측부터 순서대로 순회
    다음 레벨로 이동하여 해당 절차를 수행

  • 결과
     4 - 2 - 6 - 3 - 1 - 5 - 7 - 9 - 8
  • 너비 우선 탐색이 이와 같은 순서를 보인다.
  • 큐(Queue) 를 사용하여 구현할 수 있다.

 

4. 트리의 종류 - 이진 트리

  1) 이진 트리(Binary Tree)

  • 차수가 2인 트리, 즉 노드가 가질 수 있는 자식 노드의 최대 갯수가 2인 트리를 의미한다.

 

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

  • 어떤 노드의 좌측 서브 트리에는 자신보다 작은 값을 가지는 노드만이, 우측 서브 트리에는 자신보다 큰 값을 
    가지는 노드만이 존재하는 상태의 이진 트리이다.

  • 균형이 잘 잡힌 이진 탐색 트리의 경우 트리 내의 특정 데이터를 탐색하는데 O(logN) 의 시간복잡도를 보인다.

 

  3) 완전 이진 트리(Complete Binary Tree)

         트리 A                                                     트리 B                                                         트리 C

  • 마지막 레벨을 제외한 레벨이 완전히 채워져있으며 마지막 레벨의 노드가 왼쪽에서부터 채워진 상태인
    이진 트리이다.

  • 배열로 표현했을 때 빈 칸이 생기지 않는 트리이다.

  • 위 그림에서 A는 완전 이진 트리지만 B는 레벨 2가 완전히 채워지지 않았기 때문에, C는 마지막 레벨의 노드 8, 9 가
    왼쪽에서부터 채워지지 않았기 때문에 완전 이진 트리가 아니다.

 

 4) 정 이진 트리(Full Binary Tree)

  • 모든 노드가 자식노드를 두 개 가지거나 아예 가지지 않는, 즉 자식 노드를 하나만 가지는 노드가 없는 트리이다.

 5) 포화 이진 트리(Perfect Binary Tree)

  • 마지막 레벨까지 빈 공간 없이 완전히 채워진 이진 트리이다.

 

 6) 균형 이진 트리(Balanced Binary Tree)

            트리 A                                                                                        트리 B

  • 명확한 정의가 있는 것은 아니지만 트리 B와 같이 치우친 상태가 아닌 A와 같이 균형을 이룬 상태의 
    이진 트리이다.
  • 균형의 기준을 어떻게 세우느냐에 따라 다른 형태가 될 수 있지만 일반적으로는 모든 노드에 대해
    좌측과 우측의 서브트리의 높이 차이가 일정이상 나지 않을 것을 기준으로 한다.

 

'CS > 자료구조' 카테고리의 다른 글

#8 트리(Tree) 3 - AVL 트리  (0) 2021.10.07
#7 트리(Tree) 2 - 힙(Heap)  (0) 2021.10.06
#5 그래프(Graph)  (0) 2021.10.01
#4 큐(Queue)  (0) 2021.09.28
#3 스택 (Stack)  (0) 2021.09.28

1. 그래프(Graph)

 그래프는 정점(Vertex)들과 그 정점들 사이를 연결하는 간선(Edge)으로 이루어진 비선형자료구조이다.  정점은 

노드(Node) 라고도 부른다.  또한 각 노드에 연결된 간선의 갯수를 그 노드의 차수(Degree) 라고 한다.

 

그래프의 예시

위의 예시는 0부터 5 까지의 숫자를 담고있는 6개의 노드와 그 사이를 잇는 8개의 간선으로 이루어진 그래프이다.

 

 

2. 그래프의 종류

  1) 유향 그래프(Directed Graph)

  • 위와 같이 간선에 방향성이 있는 그래프를 의미한다.  노드 사이의 경로가 왕복 불가능한 것이어야할 경우 사용된다.

 

  2) 무향 그래프(Undirected Graph)

  • 위와 같이 간선에 방향성이 없는 그래프를 의미한다.  단순히 두 노드가 연결되어있다는 정보만을 제공한다.

  • 일반적으로 그래프라고 하면 무향 그래프를 의미하는 경우가 많다.  두 노드 사이의 경로가 왕복 가능한 경로일
    경우 사용된다.

 

  3) 가중 그래프(Weighted Graph)

  • 위와 같이 간선에 가중치가 존재하는 그래프를 의미한다. 

  • 가중치의 의미는 노드 사이의 이동에 드는 비용이나 두 노드 사이의 거리 등 경우에 따라 다르다.

 

  4) 완전 그래프(Complete Graph)

  • 위와 같이 임의의 두 노드 사이에 반드시 하나의 간선이 존재하는 그래프를 의미한다. 

  • 이 경우 간선의 갯수는 (노드의 갯수 * (노드의 갯수 - 1)) / 2 개가 된다. 

 

 

  5) 부분 그래프(SubGraph)

그래프 A                                                      그래프 B                                                    그래프 C

  • 어떤 그래프 U 의 모든 노드와 간선이 다른 그래프 V 에 속한다고 할 때, 그래프 U는 그래프 V 의 부분 그래프이다.
    위 예시에서 그래프 B와 C는 모두 그래프 A의 부분그래프이다.
     
  • 그래프 C와 같이 임의의 두 노드간의 관계가 그래프 A의 두 노드간의 관계와 동일한 부분 그래프를 유도 부분
    그래프(Induced SubGraph) 라고 한다.
     그래프 B의 경우 노드 3과 5의 연결관계가 그래프 A와 다르기 때문에
    그래프 A의 유도 부분 그래프가 아니다.

  • 그래프 B와 같이 노드의 집합(Node Set)이 그래프 A와 동일한 부분 그래프를 신장 부분 그래프(Spanning
    SubGraph) 라고 한다.
    그래프 C의 경우 노드 0이 빠져있기 때문에 그래프 A의 신장 부분 그래프가 아니다.

 

  6) 유향 비순환 그래프(Directed Acyclic Graph)

  • 위와 같이 유향 그래프 중에서도 한번 지나친 노드를 다시 방문할 수 없는, 즉 순환(Cycle)이 존재하지 않는
    유향 그래프를 유향 비순환 그래프(DAG)라고 한다.  위상 정렬이 존재하는 그래프라고 생각하면 편하다.

  • 선후 관계가 정의된 데이터를 그래프화 하여 표현하기에 좋다.  대표적인 예시로 스프레드 시트에서 셀 간의
    참조관계를 표현하는데 활용할 수 있다.

 

3. 그래프의 표현

 그래프를 표현하는 두 가지 대표적인 방법을 알아본다.  여기서는 무향 그래프를 기준으로 설명한다.

  

  1) 인접 행렬

 

  • 위와 같이 노드간의 연결관계를 행렬로 나타내는 방식이다.  mat[i][j] = 1이라면 노드 i와 j가 연결되어있음을,
    0이라면 연결되어있지 않음을 의미한다.  가중 그래프를 나타낼 경우 1 대신 가중치를 사용하면 된다.

  • 예시와 같이 무향 그래프일 경우에 한해서 인접행렬은 대각 성분을 기준으로 대칭을 이루는 성질을 가진다.

  • 구현이 간단하고 임의의 두 노드간의 연결여부를 확인에 O(1) 의 시간복잡도를 보인다는 장점이 있다.
  • 특정 노드와 연결된 모든 노드를 탐색하기 위해 반드시 노드의 총 갯수만큼의 탐색이 필요하다는 단점이 있다.
    노드 갯수가 V인 그래프에서 한 노드에 연결된 노드를 탐색하는데 O(V)의 시간복잡도를 보인다.

  • 위의 특성으로 인해 노드 갯수에 비해 간선의 갯수가 적은 희소 그래프(Sparse Graph)일 경우 메모리와 시간낭비가
    심해진다.

 

  2) 인접 리스트

  • 위와 같이 노드간의 연결관계를 각 노드에 연결된 노드들의 리스트로 나타내는 방식이다.  가중 그래프를 나타낼
    경우 노드 번호와 가중치를 함께 리스트의 요소로 넣어주면 된다.

  • 한 노드에 연결된 모든 노드를 탐색하기 위해 그 노드에 연결된 노드의 갯수만큼의 탐색만이 필요하며
    간선의 갯수만큼의 메모리만 차지하기 때문에 메모리와 시간을 절약 가능하다는 장점이 있다.

  • 임의의 두 노드 u, v 간의 연결 여부를 알기 위해 list[u] 또는 list[v] 의 길이만큼의 탐색이 필요하다는 단점이 있다.

'CS > 자료구조' 카테고리의 다른 글

#7 트리(Tree) 2 - 힙(Heap)  (0) 2021.10.06
#6 트리(Tree) 1 - 트리의 개념/이진 트리  (0) 2021.10.04
#4 큐(Queue)  (0) 2021.09.28
#3 스택 (Stack)  (0) 2021.09.28
#2 양방향 연결 리스트(Doubly Linked List) 구현  (0) 2021.09.27

+ Recent posts