170810(목) - 알고리즘 for Java (BST)

자료구조 for Java (BST)

Binary Search Tree: BST

- 주 용도는 검색

- 최악의 경우 O(logn)

- skew tree 일때 약점을 보인다.

Declaration

- binary tree와의 차이점은 구조에 있지않고 data에 있다.

class Node<T>(var data: T) {
    private var left: Node<T>? = null
    private var right: Node<T>? = null
}

Calculate

- main

ㆍ항목 찾기

ㆍ최소값, 최대값 찾기

ㆍ항목 삽입, 삭제

- sub

ㆍ이진검색트리인가 아닌가

ㆍk번째 작은 항목 찾기

ㆍ항목 정렬하기 등

Note

- inorder 탐색을 수해아면 정렬된 리스트가 만들어 진다.

- 대부분 LDR 순으로 처리

- 항목을 검색할때 left, right중 하나만 검색하지 둘 다 검색하진 않는다.

항목 찾기

// recursive way
// O(n)
fun find(root: Node<Int>, data: Int): Node<Int> {
    // if (root == null) return null

    if (data < root.data) {
        return find(root.left!!, data)
    } else if (data > root.data) {
        return find(root.right!!, data)
    } else {
        return root
    }
}

// non-recursive way
// O(n)
fun find(rootNode: Node<Int>, data: Int): Node<Int>? {
    // if (root == null) return null

    var root = rootNode

    while (root != null) {
        if (data == root.data) {
            return root
        } else if (data < root.data) {
            root = root.left!!
        } else {
            root = root.right!!
        }
    }

    return null
}

최소 항목 찾기

// recursive way
// O(n)
fun findMin(root: Node<Int>): Node<Int>? {
    if (root.left == null) 
        return root 
    else 
        return findMin(root.left!!)
}

// non-recursive way
// O(n)
fun findMin(rootNode: Node<Int>): Node<Int>? {
    var root = rootNode
    
    while (root.left != null) {
        root = root.left!!
    }
    
    return root
}

최대 항목 찾기

// recursive way
// O(n)
fun findMax(root: Node<Int>): Node<Int>? {
    if (root.right == null) 
        return root 
    else 
        return findMax(root.right!!)
}

// non-recursive way
// O(n)
fun findMax(rootNode: Node<Int>): Node<Int>? {
    var root = rootNode

    while (root.right != null) {
        root = root.right!!
    }

    return root
}

항목 삽입하기

// O(n)
fun insert(rootNode: Node<Int>?, data: Int): Node<Int> {
    var root = rootNode

    if (root == null) {
        root = Node(data)
    } else {
        if (data < root.data) {
            root.left = insert(root.left, data)
        } else if (data > root.data) {
            root.right = insert(root.right, data)
        }
    }

    return root
}

항목 삭제하기

- 다른 연산에 비해서 복잡

(삭제되는 항목이 leaf node 가 아닐 수도 있기 때문)

1. 삭제할 노드를 찾는다.

2. 아래의 경우 중 하나를 고려

① 삭제할 항목이 leaf node

- null을 부모 노드에게 리턴한다. (해당 child node를 null로)

② 삭제할 항목이 하나의 child node를 가진다.

- 현재 노드의 자식을 부모노드에게 보낸다.

③ 삭제할 항목이 두개의 child node를 가진다.

- 노드의 키값을 왼쪽 sub tree의 최대 항목과 바꾸고 재귀적으로 그 노드를 삭제

// O(n)
fun delete(rootNode: Node<Int>?, data: Int): Node<Int>? {
    var root = rootNode

    if (root == null) {
        // elemet not exist.
    } else if (data < root.data) {
        root.left = delete(root.left, data)
    } else if (data > root.data) {
        root.right = delete(root.right, data)
    } else {

        // child node가 2개 이상일 경우
        if (root.left != null && root.right != null) {
            root.data = findMax(root.left).data
            root.left = delete(root.left, root.data)
        }

        // child node가 1개일 경우
        else {
            if (root.left == null) {
                root = root.right
            }
            
            if (root.right == null) {
                root = root.left
            }
        }
    }

    return root
}