[Kotlin] 자료구조 2 (해쉬 , 트리, 힙)

1. 해쉬 (Hash)

해쉬 함수 (Hash function) : 임의의 데이터를 고정된 길이의 데이터로 매핑시키는 함수.

해쉬 (Hash) : 해쉬 함수를 통해 매핑된 고정된 길이의 데이터

해쉬의 특징은 다음과 같다.

1. 결과값이 중복될 가능성의 거의 없다.

2. 입력값을 알 수 없으며, 결과값을 알아도 이를 통해 입력값을 유추할 수 없다.

해쉬 테이블 (Hash table) : 해쉬값을 index로 사용하여 key, value 형태로 값을 저장하는 자료구조.

해쉬 충돌 (Hash Collision) : 고정된 길이의 데이터로 변환하는 해쉬의 한계로 인해, 서로 다른 두 개의 key가 동일한 hash 값을 갖게 되는 것.

 

이러한 해쉬 충돌을 해결하기 위한 방법으로는 두 가지가 존재한다.

1. Chaining 

같은(충돌한) 해쉬 키에 대해 Linked List를 이용하여 기존의 자료 뒤에 새로운 값을 연결시키는 방식.

 

장점 :

- 제한된 크기에 대한 효율적인 공간 관리

- 미리 공간을 보장할 필요가 없으므로 적은 메모리를 사용

단점 : 

- 하나의 해쉬 키에 데이터가 몰리게 된다면 검색에 대한 효율성 하락

- 외부 공간 사용, 외부 공간에 대한 작업 추가

 

시간 복잡도 : 

추가, 삭제, 탐색 : 최악의 경우 O(n) [하나의 해쉬에 모든 값이 몰려있을 경우] 

 

 

 

2. Linear Probing

같은(충돌한) 해쉬 키에 대해 해당 address의 다음 index부터 순회하여 비어있는 공간에 데이터를 저장하는 방식.

 

장점 :

- 외부 공간 사용 없이 테이블 내에서 충돌 처리 가능

단점 : 

- 테이블 공간 사용 증가

- 해쉬 함수의 성능에 따른 전체 해쉬 테이블의 효율성 변화

 

시간 복잡도 : 

추가, 삭제, 탐색 : 최악의 경우 O(n) [테이블을 순회하며 일치하는 해쉬 값을 탐색하고 추가, 삭제해야 하므로] 

 

 

2. 트리 (Tree)

Edge를 통해 사이클이 생기지 않도록 각 Node를 연결한 자료구조.

 

용어 : 

Edge : 노드와 노드를 연결하는 간선

Root : 부모를 가지지 않는 최상위 노드

Parent : 자식을 가지는 상위 노드

Child : 부모를 가지는 하위 노드

Sibling : 같은 부모를 가지는 노드

Leaf : 자식을 가지지 않는 최하위 노드

Depth(=Level) : 트리의 Root부터 특정 노드까지의 Edge 수. 본 그림에서 D의 Depth는 2이다.

Height : 특정 노드에서 Leaf 노드까지 가장 긴 Edge 수. 본 그림에서 A의 Height은 3이다.

 

 

 

이진 트리(Binary Tree) : 각 노드의 자식이 최대 2개의 노드만을 가지는 Tree.

 

이진 탐색 트리(Binary Search Tree, BST) : 노드의 왼쪽 자식은 부모보다 작은 값을 가지고, 노드의 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리. 

 

 

이러한 조건을 가지는 트리를 통해, 데이터 검색(탐색)의 용이성을 증대시킬 수 있음.

 

시간 복잡도 : 

좌측은 부모보다 작은 값, 우측은 부모보다 큰 값이므로 한 번의 연산 마다 탐색 할 데이터가 1/2로 감소하므로

n개의 노드에 대해 O(log n) , 높이 h에 대해 O(h).

그러나, 다음과 같은 최악의 경우인 skew tree(편향 트리)에 대해서는 O(n)의 복잡도를 가짐.

 

Skew Tree. O(n)의 복잡도를 가짐

 

코틀린에서의 BST의 구현

 

// Node
data class Node(
    var left: Node? = null,
    var right: Node? = null,
    var value: Int,
)

left child, right child, value를 가지는 Node Data Class

 

class TreeManager {
    var head: Node? = null
    ...
}

구현 class에는 탐색의 시작점이 되는 root를 선언한다.

 

fun put(value: Int) {
    // CASE 1 : Tree가 비었을 때 (head = null)
    if (head == null) {
        head = Node(value = value)
        return
    }

    var parentNode = head
    while (true) {
        if (parentNode!!.value < value) {
            if (parentNode.right != null) {
                parentNode = parentNode.right
            } else {
                // CASE 2 : Tree가 비어있지 않고, 찾은 parent 노드의 오른쪽에 삽입
                parentNode.right = Node(value = value)
                break
            }
        } else {
            if (parentNode.left != null) {
                parentNode = parentNode.left
            } else {
                // CASE 3 : Tree가 비어있지 않고, 찾은 parent 노드의 오른쪽에 삽입
                parentNode.left = Node(value = value)
                break
            }
        }
    }
}

 

삽입에 대한 코드이다.

head가 null일 경우 트리 내에 노드가 없는 경우이므로 head에 새로운 노드를 그대로 삽입한다.

트리가 비어있지 않다면 root부터 삽입할 값과 노드의 값을 비교하여 삽입할 값이 작을 경우 left, 클 경우 right로 이동하여 leaf node에 도달했을 때 해당 노드를 삽입한다.

 

fun get(value: Int) : Node? {
    // CASE 1 : Tree가 비었을 때 (head = null)
    if (head == null) {
        return null
    }

    var node = head
    while (node != null) {
        if (node.value == value) {
            return node
        }
        node = if (node.value < value) {
            node.right
        } else {
            node.left
        }
    }
    return null
}

 

탐색에 대한 코드이다.

삽입과 마찬가지로, head == null일 경우 트리가 비어있는 경우이므로 null을 return한다.

트리가 비어있지 않을 경우, 현재 위치의 node 값과 탐색하고자 하는 값을 비교하여 left, right로 이동하며 값을 탐색한다.

 

fun delete(value: Int) : Boolean {
    // Case 1 : Tree가 비었을 때 (head = null)
    if (head == null) {
        return false
    }

    // Case 2 : Node가 1개이고, 삭제해야 할 노드일 때
    if (head!!.value == value && head!!.left == null && head!!.right == null) {
        head = null
        return true
    }

    // 삭제 할 Node와 Parent Node 탐색
    var parent = head!!
    var current = head
    while (current != null) {
        if (current.value == value) {
            break
        } else if (current.value < value) {
            parent = current
            current = current.right
        } else {
            parent = current
            current = current.left
        }
    }

    // Case 3 : 삭제할 Node가 존재하지 않을 때
    if (current == null) return false

    // Case 4 : 삭제할 Node가 Leaf Node일 때
    if (current.left == null && current.right == null) {
        if (parent.value > current.value) {
            parent.left = null
        } else {
            parent.right = null
        }
    }

    // Case 5 : 삭제할 Node가 Child Node를 1개만 가지고 있을 때
    if (current.left != null && current.right == null) {
        // Case 5-1 : Left Child Node를 가지고 있을 때
        if (parent.value > current.value) {
            parent.left = current.left
        } else {
            parent.right = current.left
        }
    } else {
        // Case 5-2 : Right Child Node를 가지고 있을 때
        if (parent.value > current.value) {
            parent.left = current.right
        } else {
            parent.right = current.right
        }
    }

    // Case 6 : 삭제할 Node가 Child Node를 2개 가지고 있을 때
    // 1. 삭제할 Node의 Right Child Node 중 Most Left Child Node으로 교체 (해당 방법 사용)
    // 2. 삭제할 Node의 Left Child Node 중 Most Right Child Node으로 교체

    var changeParent = current.right!!
    var change = current.right!!

    // change node 및 change node의 parent 탐색
    while (change.left != null) {
        changeParent = change
        change = change.left!!
    }

    if (parent.value > current.value) {
        if (change.right == null) {
            // Case 6-1 : change node가 leaf node 일 때
            parent.left = change
            changeParent.left = null
            change.left = current.left
            change.right = current.right
        } else {
            // Case 6-2 : change node가 right child node를 가질 때 (왼쪽 자식은 가질 수 없음)
            parent.left = change
            changeParent.left = change.right
            change.left = current.left
            change.right = current.right
        }
    } else {
        if (change.right == null) {
            // Case 6-1 : change node가 leaf node 일 때
            parent.right = change
            changeParent.left = null
            change.left = current.left
            change.right = current.right
        } else {
            // Case 6-2 : change node가 right child node를 가질 때 (왼쪽 자식은 가질 수 없음)
            parent.right = change
            changeParent.left = change.right
            change.left = current.left
            change.right = current.right
        }
    }
    return true
}

 

삭제에 대한 코드이다. 케이스가 상당히 많다..

Case 1 : 트리가 비었을 때 - 마찬가지로 트리가 비었을 때는 삭제가 불가능하므로 false를 반환한다.

Case 2 : Node가 1개이고, 삭제할 노드일 때 - head = null로 삭제하고 true를 반환한다.

Case 3 : 삭제할 Node가 트리 내에 없을 때 - get, put과 같은 형태로 탐색하고, 삭제하고자 할 노드가 없을 시 false를 반환한다.

Case 4 : 삭제할 Node가 Leaf 노드일 때 - 노드가 부모의 left child일 시 부모의 left child = null로 삭제하고 true를 반환한다.

노드가 부모의 right child일 시 부모의 right child = null로 삭제하고 true를 반환한다.

Case 5-1: 삭제할 Node가 left child를 가질 때 - 노드가 부모의 left child일 시 부모의 left child = 현재노드.left 로 삭제하고 true를 반환한다. 노드가 부모의 right child일 시 부모의 right child = 현재노드.left 로 삭제하고 true를 반환한다.

Case 5-2: 삭제할 Node가 right child를 가질 때 - 노드가 부모의 left child일 시 부모의 left child = 현재노드.right 로 삭제하고 true를 반환한다. 노드가 부모의 right child일 시 부모의 right child = 현재노드.right 로 삭제하고 true를 반환한다.

Case 6 : 삭제할 Node가 left, right child를 모두 가질 때 - 두 가지 방법 중 하나의 방법을 사용한다.

1. 삭제할 Node의 Right Child Node 중 Most Left Child Node으로 교체 (해당 방법 사용)
2. 삭제할 Node의 Left Child Node 중 Most Right Child Node으로 교체

 

 

 

3. 힙 (Heap)

최대값과 최소값을 효율적으로 찾기 위한 완전 이진 트리 형태.

완전 이진 트리 (Complete Binary Tree) : 마지막 Level을 제외한 모든 Level이 모두 채워져 있으며, 마지막 Level의 노드들은 왼쪽부터 순서대로 채워져 있는 형태의 이진트리. *이진 탐색 트리와 같이 left에는 작은 값, right에는 큰 값을 가지지는 않는다.

 

완전 이진 트리 (Complete Binary Tree)

우선순위 큐 (Priority Queue)와 같이 최대, 최소값을 효율적으로 찾기 위한 자료구조, 알고리즘 구현에 활용한다.

 

 

최대 힙 (Max Heap) : 각 노드의 값이 자식 노드가 가진 값보다 항상 크거나 같은 힙. Root의 값은 항상 최댓값이다.

최소 힙 (Min Heap) : 각 노드의 값이 자식 노드가 가진 값보다 항상 작거나 같은 힙. Root의 값은 항상 최솟값이다.

최소힙(Min Heap)과 최대힙(Max Heap)

 

시간 복잡도 : 

최소, 최대 힙에서 각각 최소, 최댓값을 구할 때는 O(1)

삽입, 삭제 시 최악의 경우 root부터 leaf까지 비교 후 삽입하므로 O(log n). 완전 이진 트리이므로 skew tree의 구조를 가지지 않음.

 

 

 

참고 : 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=mage7th&logNo=221494489570

[ 해시알고리즘 ] 해시함수의 특성 및 개념 이해 - 블록체인을 중심으로

 

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94

해시 테이블 - 위키백과, 우리 모두의 백과사전

 

https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

 

https://yoongrammer.tistory.com/68

[자료구조] 트리 (Tree)

 

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap

[자료구조] 그림으로 알아보는 힙(Heap)

 

https://doorrock.tistory.com/13

[코테를 위한 압축 개념] C++ STL 힙(Heap), 우선순위 큐(Priority queue)