[자료구조] 이진탐색트리

이진 탐색트리 (Binary Search Tree)

앞서 스터디를 통해 배운 내용들은 아래 글 참조

https://blog.naver.com/taemin1104/222832546775

트리 (Tree)

 

이진 탐색트리는 부모 노드를 기준으로 자식 노드를 생성할때

 

작은 값은 왼쪽 큰 값은 오른 쪽으로 배치하여

 

탐색 할 때의 논리구조를 단순하게 가져갈 수 있다.

 

https://yoongrammer.tistory.com/71

예를 들어 30이란 값을 검색하게 된다면

 

이진탐색트리에서는 먼저 Root의 값을 호출하고

이보다 작은 값인 자식노드의 왼쪽을 먼저 검색하게 되므로,

하나의 단계에서 탐색이 가능하지만

분균형 상태의 트리에서는 30이 나올 때까지 계속 탐색을 진행하게 된다

 

상대적으로 

이러한 효율성은 수치로 검증을 할 수 있는데

 

https://noahlogs.tistory.com/27

빅오 표기법 (big-O notation) 이란

 

설명은 위 링크로 대체한다. 

 

값을 탐색하는 과정은 흔히 술자리 up&down게임과 비슷한데

https://namu.wiki/w/%EC%97%85%20%EC%95%A4%20%EB%8B%A4%EC%9A%B4

 

나무위키의 설명으로 빌려오자면 밑이 2인 logN (N은 대충 배열의 길이로 생각하면된다)으로

 

계산해보면 대충 몇회만에 검색이 가능한지 알수가 있다.

 

물론 index로 바로 값을 뽑아 내는 것보다는 느리지만

 

순차적으로 배열을 검색하는 방법보다 논리적으로 빠르다.

 

단순한 배열과 달리 BST는 배열 생성시 조건이 따른 다.

 

BST 생성 조건

• 각 노드에 값이 있다.
• 각 노드의 키값은 모두 달라야 한다.
• 값들은 전순서가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
• 중복된 노드가 없어야 한다.

노드 삽입 규칙

public void addNode(int key) {
    if (findNode(key) != null) return;  // 이미 존재하면 그냥 리턴

    Node newNode = new Node(key);

    if (root == null) {
        root = newNode; // 트리가 비어있으면 root 에 삽입
    } else {
        Node focusNode = root;  //  탐색용 노드
        Node parent;            //  탐색용 노드의 부모 노드

        while(true) {
            parent = focusNode; //  이동

            if (key < parent.key) {             //  삽입하려는 키가 현재 노드보다 작으면
                focusNode = parent.leftChild;   //  왼쪽으로 이동

                if (focusNode == null) {        //  왼쪽 노드가 비어있으면
                    parent.leftChild = newNode; //  왼쪽 노드에 삽입
                    return;
                }
            } else {                            //  삽입하려는 키가 현재 노드와 같거나 크다면
                focusNode = parent.rightChild;  //  오른쪽으로 이동

                if (focusNode == null) {        //  오른쪽 노드가 비어있으면
                    parent.rightChild = newNode;//  오른쪽 노드에 삽입
                    return;
                }
            }
        }
    }
}

https://yoongrammer.tistory.com/71

노드의 삭제

1. 삭제할 노드가 리프인 경우

 

https://yoongrammer.tistory.com/71

리프인 노드만 삭제하면 된다.

 

2. 삭제할 노드가 자식노드를 가지고 있을 때.

 

2-1 자식 노드가 하나 일 때.

삭제하고 자식노드를 삭제하는 노드의 부모와 연결한다.

 

2-2 자식 노드가 둘 일 때.

 

Bst delete from Yebon You

삭제과정은 위와 같다.

 

public boolean deleteNode(int key) {
    // focusNode 와 parent 가 같을 수 있는 경우는 찾으려는 key 가 root 인 경우
    Node focusNode = root;
    Node parent = root;

    boolean isLeftChild = true;

    // while 문이 끝나고 나면 focusNode 는 삭제될 노드를 가리키고, parent 는 삭제될 노드의 부모노드를 가리키게 되고, 삭제될 노드가 부모노드의 left 인지 right 인지에 대한 정보를 가지게 된다
    while(focusNode.key != key) {
        parent = focusNode; // 삭제할 노드를 찾는 과정중(while문)에서 focusNode 는 계속해서 바뀌고 parent 노드는 여기서 기억해둔다

        if(key < focusNode.key) {
            isLeftChild = true;             // 지우려는 노드가 왼쪽에 있는 노드냐 기록용
            focusNode = parent.leftChild;
        } else {
            isLeftChild = false;            // 지우려는 노드가 오른쪽에 있는 노드냐 기록용
            focusNode = parent.rightChild;
        }

        // 찾으려는 노드가 없는 경우
        if(focusNode == null) {
            return false;
        }
    }


    Node replacementNode;
    // 지우려는 노드의 자식 노드가 없는 경우
    if(focusNode.leftChild == null && focusNode.rightChild == null) {
        if (focusNode == root)
            root = null;
        else if (isLeftChild)
            parent.leftChild = null;
        else
            parent.rightChild = null;
    }
    // 지우려는 노드의 오른쪽 자식노드가 없는 경우 (왼쪽 자식 노드만 있는 경우)
    else if(focusNode.rightChild == null) {
        replacementNode = focusNode.leftChild;

        if (focusNode == root)
            root = replacementNode;
        else if (isLeftChild)
            parent.leftChild = replacementNode;
        else
            parent.rightChild = replacementNode;
    }
    // 지우려는 노드의 왼쪽 자식노드가 없는 경우 (오른쪽 자식 노드만 있는 경우)
    else if (focusNode.leftChild == null) {
        replacementNode = focusNode.rightChild;
        if (focusNode == root)
            root = replacementNode;
        else if (isLeftChild)
            parent.leftChild = replacementNode;
        else
            parent.rightChild = replacementNode;
    }
    // 지우려는 노드의 양쪽 자식노드가 모두 있는 경우
    // 오른쪽 자식 노드의 sub tree 에서 가장 작은 노드를 찾아서 지우려는 노드가 있던 자리에 위치시킨다
    else {
        // 삭제될 노드의 오른쪽 sub tree 를 저장해둔다
        Node rightSubTree = focusNode.rightChild;

        // 삭제될 노드 자리에 오게 될 새로운 노드 (오른쪽 sub tree 에서 가장 작은 값을 가진 노드)
        // 이 노드는 왼쪽 child 가 없어야 한다 (가장 작은 값이기 때문에)
        replacementNode = getRightMinNode(focusNode.rightChild);

        if (focusNode == root)
            root = replacementNode;
        else if (isLeftChild)
            parent.leftChild = replacementNode;
        else
            parent.rightChild = replacementNode;

        replacementNode.rightChild = rightSubTree;
        // 지우려는 노드의 오른쪽 sub tree 에 노드가 하나밖에 없는 경우
        if (replacementNode == rightSubTree) 
            replacementNode.rightChild = null;

        replacementNode.leftChild = focusNode.leftChild; // 지우려는 노드의 왼쪽 sub tree 를 연결시킨다
    }

    return true;
}

private Node getRightMinNode(Node rightChildRoot) {
    Node parent = rightChildRoot;
    Node focusNode = rightChildRoot;

    while (focusNode.leftChild != null) {
        parent = focusNode;
        focusNode = focusNode.leftChild;
    }

    parent.leftChild = null;
    return focusNode;
}

 

• https://yaboong.github.io/data-structures/2018/02/12/binary-search-tree/

Binary Search Tree (BST) - Java

• https://yoongrammer.tistory.com/71

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)