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

Algorithm

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

빠쿤 2021. 12. 15. 08:58

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)의 복잡도를 가짐.

코틀린에서의 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에는 큰 값을 가지지는 않는다.