[Kotlin] 자료구조 : Hash, Tree, Binary Search Tree, Heap, Priority Queue

---

package com.samclarke.android.util      // playHash()

import java.security.MessageDigest      // playHash()
import java.security.DigestException    // playHash()
import java.util.*                      // playPriorityQueue()

fun main() {  
    println("Hello kotlin.....")
    // playHash()
    // playTree()
    // playBST()
    // playHeap()
    // playPriorityQueue()
}

private fun playHash() {
    /**
     * Hash : 해쉬
     * 해쉬란, 해쉬 함수를 통해 매핑된 고정된 길이의 데이터를 의미.
     * 
     * Hash Function : 해쉬 함수
     * 임의의 데이터를 고정된 길이의 데이터로 매핑 시키는 함수.
     * 
     * Hash Table : 해쉬 테이블
     * 해쉬값을 index로 사용하여 key, value 형태의 데이터 값을 저장하는 자료구조
     * 
     * Hash Collision : 해쉬 충돌
     * 해쉬의 한계점 -> 고정된 길이의 데이터로 변환 따라서 서로 다른 두 개의 key가 동일함 value 값을 가지는 경우가 발생할 수 있음.
     * 이걸 해쉬 Hash Collision이라고 한다.
     * 
     * 해쉬함수를 통해 데이터를 매핑 시킬 수 있으며, 이를통한 결과값이 중복될 가능성이 적다. 
     * 입력과 결과값에 대해 보호할 수 있다. (서로 유추가 불가능)
     * 
     * [해쉬 충돌의 해결 방법]
     * - Chanining
     *  : 충돌이 일어난 해쉬 키를 Linked List를 이용해서 기존의 자료 뒤에 새로운 값을 연결 시켜 준다.
     *  > 효율적으로 공간 관리가 가능하고, 적은 메모리를 사용함 (공간 확보가 필요 없음)
     *  > 한 해쉬 키에 여러개의 데이터가 물릴 수 있고, 이런 경우, 검색에 대한 효율성이 하락할 수 있다.
     *    외부 공간을 사용해야 하며, 해당 공간에 대한 작업이 발생
     *  [시간복잡도]
     *   - 추가, 삭제, 검색 : (최악의 경우)O(n)
     * 
     * - Linear Probing
     *  : 충돌이 일어난 해쉬 키의 Address의 다음 index부터 검색하면서 비어있는 공간에 데이터를 저장한다.
     *  > 외부 공간을 사용하지 않고 테이블 내에서 처리가 가능.
     *  > 테이블 내부의 공간 사용이 증가하고, 해쉬 함수 성능에 따라서 전체 해쉬 테이블의 효율성이 변화함.
     *  [시간복잡도]
     *   - 추가, 삭제, 검색 : (최악의 경우)O(n)
     */

     /**
      * Hashing Algorithmn
      */
    var item = "해시 값 얻기"
    println("Hashing Algorithmn [$item : ${hashSHA256(item)}]")
}

private fun hashSHA256(message: String): String {
    val hashValue: ByteArray
    try {
        val mMessageDigest = MessageDigest.getInstance("SHA-256")
        mMessageDigest.update(message.toByteArray())
        hashValue = mMessageDigest.digest()
    } catch (e: CloneNotSupportedException) {
        throw DigestException("couldn't make digest of partial content");
    }

    return bytesToHex(hashValue)
}

private fun bytesToHex(byteArray: ByteArray): String {
    val digits = "0123456789ABCDEF"
    val hexChars = CharArray(byteArray.size * 2)
    for (i in byteArray.indices) {
        val v = byteArray[i].toInt() and 0xff
        hexChars[i * 2] = digits[v shr 4]
        hexChars[i * 2 + 1] = digits[v and 0xf]
    }
    return String(hexChars)
}


/* -------------------------------------------------------------- */

private fun playTree() {
    /**
     * Tree : 트리
     * Tree란, 각 Node를 연결한 자료구조로 Edge를 통하여 Cycle이 생기지 않도록 구성
     * 
     * Binary Tree : 이진 트리
     * Node의 자식을 최대 2개까지만 가지는 Tree 구조
     * 
     * Binary Search Tree : 이진 탐색 트리
     * Node의 왼쪽 자식은 부모보다 작은 값, Node의 오른쪽 자식은 부모보다 큰 값을 가지도록 하는 Tree 구조
     * 
     * [시간복잡도]
     * - n개의 노드에 대한 시간 복잡도 : O(log n)
     * - height에 대한 시간 복잡도 : O(h)
     * - 최악의 경우(편향트리 : Skew Tree) : O(n)
     * 
     * [Dictionary]
     * - edge : 노드와 노드를 연결하는 선
     * - root : 최상위 노드 (부모가 없음)
     * - parent : 상위 노드 (자식을 가짐)
     * - child : 하위 노드 (부모를 가짐)
     * - sibling : 같은 부모를 가진 노드
     * - leaf : 최하위 노드 (자식을 가지지 않음)
     * - depth (=level) : root 노트부터 특정 노드 까지의 edge의 개수
     * - height : 특정 노드부터 leaf 노드 까지의 가장 긴 edge의 개수
     */

    val node1 = TreeNode("one")
    val node2 = TreeNode("two")

    TreeNode("tree").run {
        addNode(node1)
        addNode(node2)
    }

}

class TreeNode<T>(val value: T) {
    private val children: MutableList<TreeNode<T>> = mutableListOf()

    fun addNode(child: TreeNode<T>) = children.add(child)
}

private fun playBST() {
    /**
     * BST : Binary Search Tree
     */

    val tree = BSTManagement()
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)

    println("tree.search(3) : ${tree.search(3)}")
    println("tree.delete(4) : ${tree.delete(4)}")
    /**
     * tree.search(3) : Node(left=null, right=Node(left=null, right=Node(left=null, right=Node(left=null, right=Node(left=null, right=null, value=7), value=6), value=5), value=4), value=3)
     * tree.delete(4) : true
     */
}

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

class BSTManagement() {
    var head: Node? = null

    /** 추가 */
    fun add(inputValue: Int) {
        if (head == null) {
            head = Node(value = inputValue)
            return
        }

        var nParent = head
        while (true) {
            if (nParent!!.value < inputValue) {
                if (nParent.right != null) {
                    nParent = nParent.right
                } else {
                    nParent.right = Node(value = inputValue)
                    break;
                }
            } else {
                if (nParent.left != null) {
                    nParent = nParent.left
                } else {
                    nParent.left = Node(value = inputValue)
                    break;
                }
            }
        }

    }

    /** 탐색 */
    fun search(searchValue: Int) : Node? {
        if (head == null) {
            println("Tree's Root Node is null.")
            return null
        }

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

    /** 삭제 */
    fun delete(deleteValue: Int) : Boolean {
        if (head == null) {
            return false
        }

        if (head!!.value == deleteValue && 
            head!!.left == null && 
            head!!.right == null) 
        {
            head = null
            return true
        }

        var nParent = head!!
        var nCurrent = head
        while (nCurrent != null) {
            if (nCurrent.value == deleteValue) {
                break
            } else if (nCurrent.value < deleteValue) {
                nParent = nCurrent
                nCurrent = nCurrent.right
            } else {
                nParent = nCurrent
                nCurrent = nCurrent.left
            }
        }

        if (nCurrent == null) return false

        if (nCurrent.left == null 
            && nCurrent.right == null) 
        {
            if (nParent.value > nCurrent.value) {
                nParent.left = null
            } else {
                nParent.right = null
            }
        }

        if (nCurrent.left != null && 
            nCurrent.right == null) 
        {
            if (nParent.value > nCurrent.value) {
                nParent.left = nCurrent.left
            } else {
                nParent.right = nCurrent.left
            }
        } else {
            if (nParent.value > nCurrent.value) {
                nParent.left = nCurrent.right
            } else {
                nParent.right = nCurrent.right
            }
        }

        var changeParent = nCurrent.right!!
        var change = nCurrent.right!!

        while (change.left != null) {
            changeParent = change
            change = change.left!!
        }

        if (nParent.value > nCurrent.value) {
            if (change.right == null) {
                  nParent.left = change
                changeParent.left = null
                change.left = nCurrent.left
                change.right = nCurrent.right
            } else {
                nParent.left = change
                changeParent.left = change.right
                change.left = nCurrent.left
                change.right = nCurrent.right
            }
        } else {
            if (change.right == null) {
                nParent.right = change
                changeParent.left = null
                change.left = nCurrent.left
                change.right = nCurrent.right
            } else {
                nParent.right = change
                changeParent.left = change.right
                change.left = nCurrent.left
                change.right = nCurrent.right
            }
        }
        return true
    }
}

/* -------------------------------------------------------------- */

private fun playHeap() {

    /**
     * Heap : 힙
     * 힙이란, Complete Binary Tree 기반의 자료구조로 최소힙과 최대힙을 가지며 해당 힙에 다른 특정 특징을 가지는 트리를 뜻함
     * 
     * 최대힙의 경우, 모든 자식들 중 가장 커야하고 각각의 자식 node에 대하여 재귀적으로 같은 규칙이 적용되어야 함.
     * 최소힘은 이와 반대의 경우.
     * 
     * 그러나 Kotlin에서는 Heap을 별도로 제공하지 않으며 PriorityQueue를 통해 다른 방식의 Heap을 제공한다.
     */
}

private fun playPriorityQueue() {

    /**
     * Priority Qurur : 우선순위 큐
     * 일반적인 Queue는 FIFO의 형태를 가지나 Priority Queue에서는 우선순위가 가장 높은 순위부터 제공된다.
     * 
     * 이 우선순위 쿠는 Heap을 기반으로 구현되어 제공됨.
     */

    val hPriorityQueue = PriorityQueue<Int>() 

    hPriorityQueue.addAll(arrayOf(1,2,3,4,5))
    hPriorityQueue.offer(11)

    println("hPriorityQueue.peek() : ${hPriorityQueue.peek()}")
    println("hPriorityQueue.poll() : ${hPriorityQueue.poll()}")
    println("hPriorityQueue : ${hPriorityQueue}")


    val h2PriorityQueue = PriorityQueue<String>() { a, b -> 
        a.length.compareTo(b.length)
    }

    h2PriorityQueue.addAll(arrayOf("abcd", "123", "efg", "456"))
    println("h2PriorityQueue : ${h2PriorityQueue}")

    /**
     * hPriorityQueue.peek() : 1
     * hPriorityQueue.poll() : 1
     * hPriorityQueue : [2, 4, 3, 11, 5]
     * h2PriorityQueue : [123, 456, efg, abcd]
     */
}