들어가기에 앞서

해당 Post는 이진 트리에 대한 기초 지식을 요구합니다.

만약 이진트리를 모른다면 이 글을 읽고 난 이후 봐주시기 바랍니다.

이진 탐색 트리 값 삽입

이진트리 중 중복 값은 허용하지 않고, 왼쪽은 부모 노드보다 작은 값을 오른쪽 자식노드는 부모노드 보다 큰 조건을 충족하는 트리를 이진 탐색 트리라고 합니다.

위와 같이 데이터가 삽입되며, 왼쪽은 currnet보다 작은 값, 오른쪽은 큰 값을 배치하게 됩니다.

public class BinaryTree {
    TreeNode<Integer> root;

    public void add(Integer value) {
        root = add(root, value);
    }

    private TreeNode<Integer> add(TreeNode<Integer> current, Integer value) {
        if(current == null) {
            return new TreeNode<>(value);
        }

        if(current.getValue() < value) {
            current.setRight(add(current.getRight(), value));
        } else {
            current.setLeft(add(current.getLeft(), value));
        }

        return current;
    }
}

이진 탐색 트리의 삭제

이진 탐색 트리의 삭제는 어떤 상태를 가진 노드를 삭제하느냐로 3가지로 나눠볼 수 있습니다.

Leaf Node 삭제

가장 생각할 게 없는 단순한 삭제입니다.

자식 노드가 존재하지 않기 때문에 균형 이진트리가 아니라면 따로 큰 작업이 이뤄지지 않는 삭제입니다.

자식이 1개인 부모 Node 삭제

Leaf Node삭제보다 살짝 작업이 추가된 삭제라고 생각합니다.

자식이 1개일 경우 삭제할 노드의 부모 노드에 자식 노드의 Instance정보를 연결해 주고, 본인은 참조되지 않는 방법으로 간단하게 삭제처리할 수 있습니다.

자식이 2개인 부모 Node 삭제

자식이 2개인 경우 어떤 정책을 통해 부모 노드를 대체할 것인지를 고민해야 합니다.

• 중위 전임자(In-order Predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드.
• 중위 후속자(In-order Successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드.

위와 같이 정책을 정하여 삭제를 진행할 경우 데이터의 쏠림 현상으로 인해 시간복잡도가 차이 날 수 있는데,

평균적으로 O(log n)의 시간복잡도를 가지며, 최악의 경우 O(n)의 시간복잡도를 가지게 됩니다.

중위 전임자 정책을 사용하여 삭제하였을 경우

public class BinaryTree {
    TreeNode<Integer> root;

    private TreeNode<Integer> add(TreeNode<Integer> current, TreeNode<Integer> prevNode) {
        if(current == null) {
            return prevNode;
        }

        if(current.getValue() < prevNode.getValue()) {
            current.setRight(add(current.getRight(), prevNode));
        } else {
            current.setLeft(add(current.getLeft(), prevNode));
        }

        return current;
    }

    public void remove(Integer value) {
        root = remove(root, value);
    }

    private TreeNode<Integer> remove(TreeNode<Integer> current, Integer value) {
        if(current == null) return null;
        // 중위 전임자(In-order Predecessor)
        if(Objects.equals(current.getValue(), value)) {
            TreeNode<Integer> predecessor = predecessor(current.getLeft());
            predecessor.setRight(current.getRight());
            if(current.getLeft() != null)
                add(predecessor, current.getLeft());
            return predecessor;
        }

        current.setLeft(remove(current.getLeft(), value));
        current.setRight(remove(current.getRight(), value));

        return current;
    }

    // 중위 전임자(In-order Predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드.
    private TreeNode<Integer> predecessor(TreeNode<Integer> current) {
        if(current.getRight() == null)
            return current;

        TreeNode<Integer> predecessor =  predecessor(current.getRight());
        if(Objects.equals(current.getRight().getValue(), predecessor.getValue()))
            current.setRight(null);

        return predecessor;
    }
}

중위 후속자 정책을 사용하여 삭제하였을 경우

public class BinaryTree {
    TreeNode<Integer> root;

    private TreeNode<Integer> add(TreeNode<Integer> current, TreeNode<Integer> prevNode) {
        if(current == null) {
            return prevNode;
        }

        if(current.getValue() < prevNode.getValue()) {
            current.setRight(add(current.getRight(), prevNode));
        } else {
            current.setLeft(add(current.getLeft(), prevNode));
        }

        return current;
    }

    public void remove(Integer value) {
        root = remove(root, value);
    }

    private TreeNode<Integer> remove(TreeNode<Integer> current, Integer value) {
        if(current == null) return null;

        // 중위 후속자(In-order Successor)
        if(Objects.equals(current.getValue(), value)) {
            TreeNode<Integer> successor = successor(current.getRight());
            successor.setLeft(current.getLeft());
            if(current.getRight() != null)
                add(successor, current.getRight());
            return successor;
        }

        current.setLeft(remove(current.getLeft(), value));
        current.setRight(remove(current.getRight(), value));

        return current;
    }

    // 중위 후속자(In-order Successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드.
    private TreeNode<Integer> successor(TreeNode<Integer> current) {
        if(current.getLeft() == null)
            return current;

        TreeNode<Integer> successor =  successor(current.getLeft());
        if(Objects.equals(current.getLeft().getValue(), successor.getValue()))
            current.setLeft(null);
        return successor;
    }
}

최종 코드

public class BinaryTree {
    TreeNode<Integer> root;

    public BinaryTree() {
        root = null;
    }

    public void add(Integer value) {
        root = add(root, value);
    }

    private TreeNode<Integer> add(TreeNode<Integer> current, Integer value) {
        if(current == null) {
            return new TreeNode<>(value);
        }

        if(current.getValue() < value) {
            current.setRight(add(current.getRight(), value));
        } else {
            current.setLeft(add(current.getLeft(), value));
        }

        return current;
    }

    private TreeNode<Integer> add(TreeNode<Integer> current, TreeNode<Integer> prevNode) {
        if(current == null) {
            return prevNode;
        }

        if(current.getValue() < prevNode.getValue()) {
            current.setRight(add(current.getRight(), prevNode));
        } else {
            current.setLeft(add(current.getLeft(), prevNode));
        }

        return current;
    }

    public void remove(Integer value) {
        root = remove(root, value);
    }

    private TreeNode<Integer> remove(TreeNode<Integer> current, Integer value) {
        if(current == null) return null;

        if(!Objects.equals(current.getValue(), value)) {
            current.setLeft(remove(current.getLeft(), value));
            current.setRight(remove(current.getRight(), value));
            return current;
        }

        // Leaf일 때 삭제
        if(current.getRight() == null && current.getLeft() == null)
            return null;

        if(current.getLeft() == null) return current.getRight();
        if(current.getRight() == null) return current.getLeft();

//        // 중위 전임자(In-order Predecessor)
//        TreeNode<Integer> predecessor = predecessor(current.getLeft());
//        predecessor.setRight(current.getRight());
//        if(current.getLeft() != null)
//           add(predecessor, current.getLeft());
//        return predecessor;

        // 중위 후속자(In-order Successor)
        TreeNode<Integer> successor = successor(current.getRight());
        successor.setLeft(current.getLeft());
        if(current.getRight() != null)
            add(successor, current.getRight());

        return successor;

    }

    // 중위 전임자(In-order Predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드.
    private TreeNode<Integer> predecessor(TreeNode<Integer> current) {
        if(current.getRight() == null)
            return current;

        TreeNode<Integer> predecessor =  predecessor(current.getRight());
        if(Objects.equals(current.getRight().getValue(), predecessor.getValue()))
            current.setRight(null);

        return predecessor;
    }

    // 중위 후속자(In-order Successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드.
    private TreeNode<Integer> successor(TreeNode<Integer> current) {
        if(current.getLeft() == null)
            return current;

        TreeNode<Integer> successor =  successor(current.getLeft());
        if(Objects.equals(current.getLeft().getValue(), successor.getValue()))
            current.setLeft(null);
        return successor;
    }


    // 전위 순회 (Pre-order Traversal) 출력 메서드
    public void traversePreOrder(TreeNode<Integer> node) {
        if (node != null) {
            System.out.print(" " + node.getValue());
            traversePreOrder(node.getLeft());
            traversePreOrder(node.getRight());
        }
    }

    // 중위 순회 (In-order Traversal) 출력 메서드
    public void traverseInOrder(TreeNode<Integer> node) {
        if (node != null) {
            traverseInOrder(node.getLeft());
            System.out.print(" " + node.getValue());
            traverseInOrder(node.getRight());
        }
    }

    // 후위 순회 (Post-order Traversal) 출력 메서드
    public void traversePostOrder(TreeNode node) {
        if (node != null) {
            traversePostOrder(node.getLeft());
            traversePostOrder(node.getRight());
            System.out.print(" " + node.getValue());
        }
    }

    // 레벨 순회 (Level-order Traversal) 출력 메서드
    public void traverseLevelOrder(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(" " + node.getValue());

            if (node.getLeft() != null) queue.add(node.getLeft());
            if (node.getRight() != null) queue.add(node.getRight());
        }
    }

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.add(5);
        bt.add(2);
        bt.add(3);
        bt.add(1);
        bt.add(0);
        bt.add(7);
        bt.add(8);
        bt.add(6);

        bt.remove(5);

        // 순회 결과 출력
        System.out.print("Pre-order traversal:");
        bt.traversePreOrder(bt.root);
        System.out.println();

        System.out.print("In-order traversal:");
        bt.traverseInOrder(bt.root);
        System.out.println();

        System.out.print("Post-order traversal:");
        bt.traversePostOrder(bt.root);
        System.out.println();

        System.out.print("Level-order traversal:");
        bt.traverseLevelOrder(bt.root);
        System.out.println();
    }
}

들어가기에 앞서

해당 글을 작성하기에 앞서 이진트리는 어떤 것인지에 대한 사전 지식이 있어야 이해할 수 있는 글입니다.

만약 이진트리가 무엇인지 모른다면 이 글을 읽고 오시기 바랍니다.

이진 트리 순회

이진 트리를 순회하는 방법에는 어디서부터 확인하느냐로 4가지로 나눌 수 있습니다.

순회 방법에 따라 사용처가 다르게 나오게 되고, 이를 학습함으로써 좀 더 본인이 사용하고자 하는 목적에 알맞은 방법으로 알고리즘을 작성할 수 있습니다.

아래 보이는 이진 트리를 통해 각각의 순회 결과에 대해 알려드리겠습니다.

아래 이진 트리는 이 곳에서 코드로 확인해 보실 수 있습니다.

전위 순회 ( Pre-order Traversal )

전위 순회는 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 재귀하며 출력하는 방법입니다.

즉 가장 왼쪽부터 라인부터 탐색하며, 가장 깊은 Level의 오른쪽 노드부터 차근차근 탐색할 수 있게 해줍니다.

public void traversePreOrder(TreeNode<Integer> node) {
    if (node != null) {
        System.out.print(" " + node.getValue());
        traversePreOrder(node.getLeft());
        traversePreOrder(node.getRight());
    }
}

결과

사용처

• DFS 탐색
• 트리 복사

중위 순회 ( In-order Traversal )

중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식노드 순으로 순회하는 방법입니다.

public void traverseInOrder(TreeNode<Integer> node) {
    if (node != null) {
        traverseInOrder(node.getLeft());
        System.out.print(" " + node.getValue());
        traverseInOrder(node.getRight());
    }
}

결과

사용처

• 오름차순 정렬
• 정렬된 데이터 탐색

후위 순회 ( Post-order Traversal )

후위 순회는 왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모 노드 순으로 순회하는 방법입니다.

public void traversePostOrder(TreeNode node) {
    if (node != null) {
        traversePostOrder(node.getLeft());
        traversePostOrder(node.getRight());
        System.out.print(" " + node.getValue());
    }
}

결과

사용처

• 메모리 해제
• 파일 구조 삭제
• 후위 표기법을 통한 연산

레벨 순회 ( Level-order Traveral )

레벨 순회는 root 부터 각 레벨마다 순차적으로 왼쪽부터 오른쪽으로 순회하는 방법입니다.

public void traverseLevelOrder(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(" " + node.getValue());

        if (node.getLeft() != null) queue.add(node.getLeft());
        if (node.getRight() != null) queue.add(node.getRight());
    }
}

결과

사용처

• 최단 경로 탐색
• Bfs 탐색

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php

이진 트리란?

이진 트리는 트리 자료구조의 한 종류로, 각 노드가 최대 2개의 자식노드를 가질 수 있는 구조입니다.

이진 트리를 구성하는 노드들은 3가지로 분리할 수 있습니다.

• 루트 노드 ( Root Node ): 트리의 시작점으로, 부모 노드가 존재하지 않고 이진트리에서 하나만 존재합니다.
• 자식 노드 ( Child Node ): 부모 노드에 속한 노드로써 Left Child와 Right Child로 구분.
• 잎 노드 (Leaf Node): 트리의 마지막에 존재하는 노드로써 자식이 존재하지 않는 노드를 의미합니다.

위와 같이 3가지로 분류할 수 있지만 때에 따라 하나의 노드가 의미하는 바가 겹칠 수 있습니다.

이진 트리 유형

이진 트리는 속한 노드들의 상태에 따라 아래와 같은 유형들로 분류할 수 있습니다.

균형 이진 트리 ( Balanced Binary Tree )

모든 자식 노드들의 Level차이가 최대 1 이하 차이나는 트리입니다.

즉, 한 노드에 쏠림 현상이 발생하지 않고 아래와 같이 규형 잡힌 상태를 의미합니다.

포화 이진 트리 ( Full Binary Tree )

모든 자식 노드가 0개 혹은 2개씩 채워진 상태를 의미합니다. 

완전 이진 트리 ( Complete Binary Tree )

완전 이진트리는 마지막 레벨을 제외 모든 노드들이 채워져 있는 상태를 의미합니다.

이때 자식 노드는 왼쪽부터 차 있어야 합니다.

이진 트리 표현

이진 트리는 배열과 링크드 리스트를 통해 표현할 수 있습니다.

Array 표현

배열을 통해 이진트리를 표현할 경우 아래와 같은 규칙을 통해 표현할 수 있습니다.

• 루트는 배열의 0번째 인덱스 혹은 1번째 인덱스에 존재한다.
• 왼쪽 자식인덱스 = 루트 인덱스 == 0 ? 부모 인덱스 * 2 + 1 : 부모 인덱스 * 2;
• 오른쪽 자식 인덱스 = 루트 인덱스 == 0 ? 부모인덱스 * 2 + 2; 부모 인덱스 * 2 + 1;

위와 같은 규칙을 가지고 이진트리를 표현하였을 때 단점이 존재하는데,

이는 배열로 구현하다 보니 초기 이진트리의 크기가 특정된다는 점이고, 이는 이진트리 내 데이터가 골고루 분포되지 않다면 메모리 자원을 비효율 적으로 사용한다는 단점이 존재합니다.

public static void main(String[] args) {
        int[] arr = new int[7];
        // Root
        arr[0] = 1;
        // Level 1
        arr[1] = 2;
        arr[2] = 3;
        // Level 2
        arr[3] = 4;
        // Level 3
        arr[5] = 6;
        arr[6] = 7;
        printTree(arr);
}

코드로 작성하면 위와 같이 작성을 할 수 있고, Terminal에 출력할 경우 위와 같이 출력해 볼 수 있습니다.

public static void printTree(int[] arr) {
        int level = 0;
        int index = 0;
        while (index < arr.length) {
            int nodesInLevel = (int) Math.pow(2, level); // 해당 레벨의 노드 개수
            for (int i = 0; i < nodesInLevel && index < arr.length; i++) {
                System.out.print(arr[index] + " ");
                index++;
            }
            System.out.println(); // 각 레벨 출력 후 줄바꿈
            level++;
        }
 }

Linked List 표현

Linked List로 표현할 경우 좀더 효율적으로 생성이 가능하다는 장점이 있지만, 균형 이진 트리인 경우 배열로 구현하는 것이 더욱 효율적이라 생각합니다.

우선 우리가 알고 있는 java.util.LinkedList 구현체로 구현하는 것은 아닙니다.

LinkedList의 구현체 중 데이터 저장 클래스인 Node를 확인해보면 Node안은 아래 필드들로 구현되어있습니다.

• E item
• Node<E> next
• Node<E> prev

위와 같이 이전과 이후에 대한 주소를 얻을 수 있지만 우리가 원하는 이진트리를 구현하기 위해서는 next가 leftNext와 rightNext로 나눠져야합니다.

그리하여 직접 구현한다면 아래와 같이 구현할 수 있습니다.

public static class TreeNode<E> {
        private E item;
        private TreeNode<E> left;
        private TreeNode<E> right;

        public TreeNode(E item) {
            this.item = item;
        }

    }

    public static class BinaryTree {
        TreeNode<Integer> root;

        public void add(Integer item) {
            root = addRecursive(root, item);
        }
        private TreeNode<Integer> addRecursive(TreeNode<Integer> current, Integer item) {
            if (current == null) {
                return new TreeNode<>(item);
            }

            if(current.item > item) {
                current.left = addRecursive(current.left, item);
            } else {
                current.right = addRecursive(current.right, item);
            }

            return current;
        }
}

root를 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 셋팅되게 구현하였습니다.

검색의 성능을 높이기 위해 최소 힙, 최대 힙, 탐색 이진 트리 등등 다양한 방법으로 구성될 수 있으며,

해당 내용들은 다음 글에 작성하도록 하겠습니다.

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php

Stack이란?

Stack은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO( Last In First Out ) 자료구조입니다.

추상자료형( abstract data type, ADT )이며, 이는 논리적인 기능을 명시해 놓은 것이라 볼 수 있고, 이는 구현체가 이를 상속받아 구현하는 방식으로 자료형은 Stack이지만 구현은 여러 방법으로 구현할 수 있음을 의미합니다.

Stack은 Vector를 상속받아 구현을 하고 있는데 이는 Vector를 구현되 LIFO방식으로 데이터를 다룰 수 있게 다루기 위해 Stack이란 자료형이 존재한다 생각해 볼 수 있습니다.

우선 기본적인 기능을 확인해 보겠습니다.

Stack은 Vector를 상속한 ADT이기 때문에 기본적으로 Object []인 elementData로 데이터를 관리하고 있습니다.

배열의 크기는  기본적으로 10의 크기로 생성하고 있으며, resizing을 통해 많은 데이터가 들어오더라도 수용할 수 있습니다. 이렇듯 대부분의 기능은 동일하지만, 외부에서 접근할 수 있는 pop메서드를 확인해 보면 elemtnData의 Size를 확인하여 맨 마지막 데이터만을 추출할 수 있도록 구현되어 있는 것을 확인할 수 있습니다.

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

제공하는 기능

사용처

그럼 Stack은 어떤 곳에서 사용하게 될까요??

웹브라우저 History 즉 뒤로가기 앞으로가기 와 같은 기능처럼 history를 쌓아두고 이를 최신 것부터 접근하는 상황이 있다면 이럴때는 Stack을 사용함으로써 편하게 관리할 수 있습니다.

또한 재귀함수와 같이 연산이 루프를 도는 방향의 알고리즘을 구현을 한다면,

최근 접근 한 것들을 접근 할 수 있는 Stack을 통해 쉽게 최근에 넣은 데이터를 꺼내 연산을 하면서 손쉽게 구현할 수 있습니다. 백준 코딩 테스트

References

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html