트리(Tree)

1. 트리(Tree)란?

- 트리는 계층적 구조를 갖는 자료구조로 노드(Node)와 간선(Edge)으로 구성되는 비선형 자료구조이다.

- 한 노드는 부모(Parent)와 여러 자식(Child) 노드를 가질 수 있으며, 최상위 노드는 루트(Root)라고 부른다.

- 트리 순회, 계층적 데이터 표현  알고리즘에 활용된다.

 

1-1. 주요 용어

- 노드(Node): 트리의 기본 구성 요소로 하나의 데이터를 담고있다.

- 루트(Root): 트리의 최상위 노드

- 자식(Child) 특정 노드 아래에 연결된 노

- 리프(Leaf): 자식이 없는 단말 노드

- 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리

- 깊이(Depth): 루트로부터의 거리 또는 트리의 최대 레벨

 

 

2. 트리의 종류

- 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가지는 트리

- 이진 탐색 트리(BST, Binary Search Tree): 왼쪽 서브트리에는 현재 노드보다 작은 값, 오른쪽 서브트리에는 큰 값이 저장되는 특성을 가지는 트리

- 균형 이진 트리: 모든 노드의 좌우 서브트리 높이가 제한된(보통 1이하) 트리, 노드의 빈번한 삽입/삭제가 많이 있어도 높이가 제한되느 특성이 있어 성능상 유리하다.

 

3. 트리 구현

- 일반적인 이진 트리를 구성하고 삽입/삭제와 순회 방식을 구현하였다.

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left = right = null;
    }
}

public class Tree {
    TreeNode root;

    public Tree() {
        root = null;
    }

    // 재귀적 삽입 메소드
    private TreeNode insertRecursive(TreeNode node, int key) {
        if(node == null) {
            return new TreeNode(key);
        }

        // 왼쪽 자식이 없으면 왼쪽에 삽입
        if(node.left == null) {
            node.left = new TreeNode(key);
        }
        // 오른쪽 자식이 없으면 오른쪽에 삽입
        else if(node.right == null) {
            node.right = new TreeNode(key);
        }
        // 둘다 존재하면 왼쪽 서브트리에 재귀적으로 삽입
        else {
            node.left = insertRecursive(node.left, key);
        }
        return node;
    }

    // 외부에서 호출하는 삽입 메소드
    public void insert(int key) {
        root = insertRecursive(root, key);
    }

    // 재귀적 삭제 메소드, 첫번째로 만난 key의 노드를 삭제한다.
    private TreeNode deleteRecursive(TreeNode node, int key) {
        if(node == null) return null;

        if(node.value == key) {
            // 삭제할 노드가 리프인 경우
            if(node.left == null && node.right == null) {
                return null;
            }

            // 자식이 한 개만 있는 경우
            if(node.left == null) {
                return node.right;
            }
            if(node.right == null) {
                return node.left;
            }

            // 두 자식이 모두 있는 경우 왼쪽 서브트리에서 오른쪽 끝 노드를 찾아 대체
            TreeNode search = search(node.left);
            node.value = search.value;
            node.left = deleteRecursive(node.left, key);
            return node;
        }

        node.left = deleteRecursive(node.left, key);
        node.right = deleteRecursive(node.right, key);
        return node;
    }

    // 왼쪽 서브트리의 오른쪽 끝 노드를 찾는 헬퍼 메소드
    private TreeNode search(TreeNode node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    // 외부에서 호출하는 삭제 메소드
    public void delete(int key) {
        root = deleteRecursive(root, key);
    }

    // 전위 순회: 루트 -> 왼쪽 -> 오른쪽
    public void preOrder(TreeNode node) {
        if(node == null) return;
        System.out.print(node.value + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    // 중위 순회: 왼쪽 -> 루트 -> 오른쪽
    public void inOrder(TreeNode node) {
        if(node == null) return;
        inOrder(node.left);
        System.out.print(node.value + " ");
        inOrder(node.right);
    }

    // 후위 순회: 왼쪽 -> 오른쪽 -> 루트
    public void postOrder(TreeNode node) {
        if(node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value + " ");
    }

    public static void main(String[] args) {
        Tree tree = new Tree();

        // 삽입
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(5);
        tree.insert(6);
        tree.insert(7);

        System.out.print("전위 순회: ");
        tree.preOrder(tree.root);   // 출력: 1 2 4 5 3 6 7
        System.out.println();
        System.out.print("중위 순회: ");
        tree.inOrder(tree.root);    // 출력: 4 2 5 1 6 3 7
        System.out.println();
        System.out.print("후위 순회: ");
        tree.postOrder(tree.root);  // 출력: 4 5 2 6 7 3 1
        System.out.println();

        // 삭제: 값 3인 노드 삭제
        System.out.println("값 3인 노드를 삭제합니다.");
        tree.delete(3);
        System.out.print("전위 순회 (삭제 후): ");
        tree.preOrder(tree.root);
        System.out.println();
    }
}