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

lnacles 2023. 7. 22. 00:59

오늘은 자료구조 이진 탐색 트리에 대해 정리해 보겠습니다.

다음 그림과 같이 데이터를 저장하는 자료구조를 Tree라고 합니다.

각각 데이터를 저장하고 있는 것을 Node라 할 때, 위와 같이 각 Node에 두 개의 Node가 저장되는 트리를 이진 트리라고 합니다. 이때 4,5,6,7 Node처럼 맨 아래에 있는 노드를 리프 노드라 합니다. 위와 같은 트리는 포화 이진트리 (리프노드를 제외한 노드가 두개의 노드를 가지는 트리) 또는 이진 트리(모든 노드가 두개의 노드를 가짐, 단 리프노드는 왼쪽에서부터 존재해야 함)라 합니다.

이진 탐색 트리는 부모노드의 왼쪽에 부모노드보다 작은 값, 오른쪽에는 큰 값을 저장합니다. add 하는 값의 순서에 따라 시간복잡도가 최악 O(N)이지만 O(logN)으로 값을 찾을 수 있습니다. 아래에 두 트리에서 12를 찾을 때 걸리는 시간복잡도를 보면 이진 탐색트리의 특징을 이해할 수 있습니다.

다음은 이진 탐색트리를 구현할 수 있는데. 크게 삽입, 삭제, 중위 순회를 구현했습니다.

Node 객체

static class Node{
    int data;
    Node left,right;
    public Node() {
        super();
    }
    public Node(int data) {
        super();
        this.data = data;
    }
}

BinaryTree 객체

static class BinaryTree{
    Node root;
    public BinaryTree() {
        super();
    }
}

BinaryTree에서 add 메서드

// 루트가 없을 때
void add(int data) {
    Node temp = new Node();
    temp.data = data;
    if(root == null) {
        root = temp;
    }else {
        root = addNode(root,temp);
    }
}
// 루트의 data와 비교하면서 add할 자리를 재귀적으로 찾아갑니다.
private Node addNode(Node root, Node temp) {
    if(root == null)return temp;
    else if(root.data>temp.data)root.left = addNode(root.left, temp);
    else root.right = addNode(root.right, temp);
    return root;
}

BinaryTree에서 remove 메서드

remove는 꽤 복잡하기 때문에 추가적인 설명을 하겠습니다.

전체적인 삭제 메커니즘은 삭제 대상을 리프노드로 보낸 뒤 참조를 끊어버리는 메커니즘입니다.

remove는 삭제할 Node까지 찾아 내려갑니다. 삭제 대상이 트리 부분의 루트가 되게 합니다.

예를 들어 7번 노드를 삭제하고자 했을 때를 가정하겠습니다.

루트 7번이 지워지게 된다면 7번 자리를 대신할 Node가 필요합니다. 7보다 작은 6 또는 8번이 대체 대상이고 둘 중 오른쪽 노드로 대체하겠습니다. 7번의 오른쪽에서 가장 작은 대상 8과 SWAP 합니다.

위의 그림은 루트 7번에서 오른쪽 노드 10에서 가장 왼쪽에 있는 노드 8번과 교체를 한 상태입니다. 여기서 주의해야 할 것은 삭제 대상 노드가 리프노드가 아닐 경우도 있기에 삭제 대상 노드에서 오른쪽 노드가 있는지 확인해야 합니다.

삭제 대상을 리프노드로 보내고 참조를 끊어주면 삭제를 구현할 수 있습니다. 아래는 자바 코드입니다.

void remove(int data) {
    root = removeNode(root,data);
}

private Node removeNode(Node node, int data) {
    if(node==null) throw new RuntimeException("해당값없음");
    if(node.data<data) {
        // 루트에서 오른쪽 탐색
        node.right = removeNode(node.right, data);
    }else if(node.data>data) {
        // 루트에서 왼쪽 탐색
        node.left = removeNode(node.left, data);
    }else {
        // 해당 노드가 삭제 대상일때
        // 해당 노드가 리프노드인지 확인
        if(node.right !=null) {
            /* 오른쪽에 값이 존재한다면 
             * 삭제대상보다 큰 노드(최종 목표 : 리프노드)를 찾아서
             * 삭제대상과 큰 노드를 swap 하고 
             * 큰 노드가 리프노트가 아닐수도 있으니 
             * 왼쪽을 대상으로 removeNode실행
             */
            Node child = findMin(node.right);
            int remove = data;
            node.data = child.data;
            child.data = remove;
            node.right = removeNode(node.right, data);
        }else if(node.left != null) {
            Node child = findMax(node.left);
            int remove =data;
            node.data = child.data;
            child.data = remove;
            node.left = removeNode(node.left, data);
        }else {
            node = null;
        }
    }
    return node;
}

private Node findMax(Node left) {
    if(left.right == null)return left;
    return findMax(left.right);
}

private Node findMin(Node right) {
    if(right.left == null)return right;
    return findMin(right.left);
}

마지막으로 중위 순회입니다.

void Inorderprint() {
    leftInorder(root);
    System.out.println();
}

private void leftInorder(Node root2) {
    if(root2 == null)return;
    leftInorder(root2.left);
    System.out.print(root2.data+ " ");
    leftInorder(root2.right);
}

이로써 이진탐색트리를 마치겠습니다.