8.1 트리의 개념

트리는 계층적인 구조(hierarchical structure)를 표현하는데 적합한 자료구조이다.

트리의 용어들

용어	설명
노드 (Node)	트리의 기본 단위. 데이터와 다른 노드와의 연결(자식)을 가짐
루트 노드 (Root Node)	트리의 최상위 노드, 부모가 없음
부모 노드 (Parent Node)	자식 노드를 가지는 노드
자식 노드 (Child Node)	특정 노드의 하위 노드, 부모를 가짐
형제 노드 (Sibling Node)	같은 부모를 공유하는 노드들
잎 노드 / 리프 노드 (Leaf Node)	자식이 없는 노드 (말단 노드)
내부 노드 (Internal Node)	최소한 하나 이상의 자식을 가진 노드 (리프가 아닌 노드)
루트 외 노드 (Non-root Node)	루트를 제외한 모든 노드
단말 노드 (Terminal Node)	리프 노드와 동일한 개념 (자식 없음)
비단말 노드 (Non-terminal Node)	내부 노드와 동일 (자식 있음)
조상 노드 (Ancestor)	자신부터 루트까지 경로에 있는 모든 상위 노드
자손 노드 (Descendant)	자신을 루트로 하는 서브트리에 있는 모든 하위 노드
레벨 (Level)	루트 기준으로 층을 나타냄. 일반적으로 루트는 레벨 0
깊이 (Depth)	루트에서 해당 노드까지의 경로 길이 (간선 수). 루트의 깊이는 0
높이 (Height)	해당 노드를 루트로 하는 서브트리의 최대 깊이
차수 (Degree)	특정 노드가 가진 자식 노드의 수
트리의 차수	트리 내 노드 중 최대 차수를 가진 노드의 차수
서브트리 (Subtree)	특정 노드를 루트로 하는 트리 구조

---

항목	공집합 트리 (노드 없음)	노드 1개 트리 (루트만 존재)	노드 2개 트리 (루트 + 자식 1명)
레벨	정의 불가	루트 노드: 0	루트: 0 자식: 1
높이 (Height)	보통 -1로 정의	루트 노드: 0 (리프이기도 함)	루트: 1 자식: 0

대부분의 자료구조 교재, 알고리즘 구현에서는 루트를 레벨 0, 깊이 0으로 처리합니다.

8.2 이진 트리 소개

이진 트리의 정의

트리 중에서 가장 많이 쓰이는 트리가 이진 트리이다.
모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라고 한다.
서브 트리는 공집합일 수 있다. 따라서 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다.
공집합도 이진 트리라는 점에 주의하라.
이진 트리에는 서브 트리간의 순서가 존재한다. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별된다.

이진 트리의 성질

• n개의 노드를 가진 이진 트리는 정확하게 n-1의 간선을 가진다. 그 이유는 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가지기 때문이다.
• 루트 노드의 높이가 h인 이진트리의 경우, 최소 h+1개의 노드를 가지며 최대 2^(h+1)-1개의 노드를 가진다.
  • 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진트리는 적어도 h+1개의 노드를 가진다.
  • 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 2^i가 된다. 따라서 전체 노드 개수는 2^(h+1) - 1이 된다.
• n개의 노드를 가지는 이진 트리의 루트 노드의 높이는 최대 n이거나 최소 log2(n+1) - 1이 된다.
  • 레벨 당 최소한 하나의 노드는 있어야 하므로 높이가 n을 넘을 수 없다.
  • 앞의 성질에서 높이 h의 이진트리가 가질 수 있는 노드의 최댓값은 2^(h+1) - 1이다. 따라서 n <= 2^(h+1) - 1의 부등식이 성립하고 양변에 log를 취하여 정리하면 h>=log2(n+1) - 1이 된다. h는 정수이어야 하므로 h>=⌈log2(n+1)⌉ - 1이 된다. ⌈...⌉은 올림 연산으로 ⌈2.4⌉는 3이 된다.

이진 트리의 분류

포화 이진 트리(full binary tree)

포화 이진 트리는 용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진 트리를 의미한다.
높이 k인 포화 이진 트리는 정확하게 2^(k+1) - 1개의 노드를 가진다.

완전 이진 트리(complete binary tree)

완전 이진 트리는 높이가 k일 때 레벨 0부터 k - 1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리이다.
포화 이진 트리는 항상 완전 이진 트리다.

기타 이진 트리

8.3 이진 트리의 표현

노드 기반 객체 트리 (재귀적 구조)

• 가장 전통적이고 직관적인 방식
• 트리 노드가 자기 자신 타입의 자식 노드들을 포함

예시: 일반 트리 (자식 개수 제한 없음)

class TreeNode<T> {
    T data;
    List<TreeNode<T>> children = new ArrayList<>();

    TreeNode(T data) {
        this.data = data;
    }

    void addChild(TreeNode<T> child) {
        children.add(child);
    }

    boolean isLeaf() {
        return children.isEmpty();
    }

    int getChildCount() {
        return children.size();
    }

    void traverseDFS() {
        System.out.println(data);
        for (TreeNode<T> child : children) {
            child.traverseDFS();
        }
    }
}

예시: 이진 트리 (자식 2개 제한)

class BinaryTreeNode<T> {
    T data;
    BinaryTreeNode<T> left;
    BinaryTreeNode<T> right;

    BinaryTreeNode(T data) {
        this.data = data;
    }

    boolean isLeaf() {
        return left == null && right == null;
    }

    int height() {
        int leftHeight = (left != null) ? left.height() : 0;
        int rightHeight = (right != null) ? right.height() : 0;
        return Math.max(leftHeight, rightHeight) + 1;
    }

    void inorder() {
        if (left != null) left.inorder();
        System.out.println(data);
        if (right != null) right.inorder();
    }

    void preorder() {
        System.out.println(data);
        if (left != null) left.preorder();
        if (right != null) right.preorder();
    }

    void postorder() {
        if (left != null) left.postorder();
        if (right != null) right.postorder();
        System.out.println(data);
    }
}

배열 기반 표현 (Complete Binary Tree 전용)

• 인덱스를 통한 부모/자식 계산
• 완전 이진 트리나 힙(Heap)에 적합
• 인덱스 규칙
  • 부모 인덱스 i일 때:
    • 왼쪽 자식 = 2*i + 1
    • 오른쪽 자식 = 2*i + 2
  • 자식 인덱스 i일 때:
    • 부모 = (i - 1) / 2

class ArrayBinaryTree {
    int[] tree;

    ArrayBinaryTree(int size) {
        tree = new int[size];
    }

    int getLeft(int index) {
        return tree[2 * index + 1];
    }

    int getRight(int index) {
        return tree[2 * index + 2];
    }

    int getParent(int index) {
        return tree[(index - 1) / 2];
    }

    void setValue(int index, int value) {
        tree[index] = value;
    }

    void traversePreOrder(int index) {
        if (index >= tree.length || tree[index] == 0) return;
        System.out.println(tree[index]);
        traversePreOrder(2 * index + 1);
        traversePreOrder(2 * index + 2);
    }
}

8.4 이진 트리의 순회(traversal)

이진 트리를 순회한다는 것은 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.

• 전위 순회(preorder traversal) : VLR
  • 트리 복사 / 직렬화
• 중위 순회(inorder traversal) : LVR
  • 이진 탐색 트리 정렬 출력
• 후위 순회(postorder traversal): LRV
  • 하위부터 삭제 (폴더 삭제, 메모리 해제)

8.10 스레드 이진 트리

스레드 이진 트리(Threaded Binary Tree)는 이진 트리의 순회를 빠르고 메모리 효율적으로 하기 위해,
빈 포인터(null)를 선행(predecessor) 또는 후속(successor) 노드를 가리키도록 만든 트리다.

일반 이진 트리에서 중위 순회를 하려면 보통 재귀 호출이나 스택이 필요하다.

• 하지만 스레드 이진 트리는 null 포인터 자리에 순회 정보를 저장하여 스택/재귀 없이 중위 순회가 가능하다.

용어	설명
Left Thread	왼쪽 자식 포인터가 null이면 → 중위 순회 시 이전 노드를 가리킴
Right Thread	오른쪽 자식 포인터가 null이면 → 중위 순회 시 다음 노드를 가리킴

class ThreadedNode {
    int data;
    ThreadedNode left, right;
    boolean isLeftThread;   // true이면 left는 스레드 (선행자)
    boolean isRightThread;  // true이면 right는 스레드 (후속자)

    ThreadedNode(int data) {
        this.data = data;
        isLeftThread = true;
        isRightThread = true;
    }
}

void inorder(ThreadedNode root) {
    ThreadedNode current = leftMost(root);
    while (current != null) {
        System.out.print(current.data + " ");
        
        // 다음 노드가 스레드면 right를 따라간다
        if (current.isRightThread) {
            current = current.right;
        } else {
            current = leftMost(current.right);
        }
    }
}

ThreadedNode leftMost(ThreadedNode node) {
    if (node == null) return null;
    while (!node.isLeftThread) {
        node = node.left;
    }
    return node;
}

8.11 이진 탐색 트리

이진 탐색 트리의 정의

• 모든 원소의 키는 유일한 키를 가진다.
• 왼쪽 서브 트리 키들은 루트 키보다 작다.
• 오른쪽 서브 트리의 키들은 루트의 키보다 크다
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

순환적인 탐색

public boolean search(T value) {
    return searchRecursive(root, value);
}

private boolean searchRecursive(BinaryTreeNode<T> node, T value) {
    if (node == null) return false;

    int cmp = value.compareTo(node.data);
    if (cmp == 0) return true;
    else if (cmp < 0) return searchRecursive(node.left, value);
    else return searchRecursive(node.right, value);
}

반복적인 탐색

public boolean search(T value) {
    BinaryTreeNode<T> current = root;

    while (current != null) {
        int cmp = value.compareTo(current.data);
        if (cmp == 0) {
            return true;  // 찾음
        } else if (cmp < 0) {
            current = current.left;  // 더 작은 값 → 왼쪽 이동
        } else {
            current = current.right; // 더 큰 값 → 오른쪽 이동
        }
    }

    return false; // 못 찾음
}

• 공간 효율성이 좋음

순환적인 삽입

public void insert(T value) {
	root = insertRecursive(root, value);
}

private BinaryTreeNode<T> insertRecursive(BinaryTreeNode<T> node, T value) {
	if (node == null) return new BinaryTreeNode<>(value);

	int cmp = value.compareTo(node.data);
    if (cmp < 0) {
    	node.left = insertRecursive(node.left, value);
	} else if (cmp > 0) {
    	node.right = insertRecursive(node.right, value);
	}
	// 중복 값은 무시 (또는 허용하려면 정책 추가)
	return node;
}

반복적인 삽입

public void insert(T value) {
    BinaryTreeNode<T> newNode = new BinaryTreeNode<>(value);

    if (root == null) {
        root = newNode;
        return;
    }

    BinaryTreeNode<T> current = root;
    BinaryTreeNode<T> parent = null;

    while (current != null) {
        parent = current;
        int cmp = value.compareTo(current.data);
        if (cmp < 0) {
            current = current.left;
        } else if (cmp > 0) {
            current = current.right;
        } else {
            return; // 중복 값 무시
        }
    }

    if (value.compareTo(parent.data) < 0) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
}

순환적인 삭제

public BinaryTreeNode<T> deleteRecursive(BinaryTreeNode<T> node, T value) {
    if (node == null) return null;

    int cmp = value.compareTo(node.data);
    if (cmp < 0) {
        node.left = deleteRecursive(node.left, value);
    } else if (cmp > 0) {
        node.right = deleteRecursive(node.right, value);
    } else {
        // 삭제 대상 찾음
        if (node.left == null) return node.right;
        else if (node.right == null) return node.left;

        // 양쪽 자식이 있는 경우: 후계자 대체
        BinaryTreeNode<T> successor = findMin(node.right);
        node.data = successor.data;
        node.right = deleteRecursive(node.right, successor.data);
    }

    return node;
}

private BinaryTreeNode<T> findMin(BinaryTreeNode<T> node) {
    while (node.left != null) node = node.left;
    return node;
}

반복적인 삭제

public void deleteIterative(T value) {
    BinaryTreeNode<T> parent = null;
    BinaryTreeNode<T> current = root;

    // 삭제할 노드 찾기
    while (current != null && !current.data.equals(value)) {
        parent = current;
        if (value.compareTo(current.data) < 0) {
            current = current.left;
        } else {
            current = current.right;
        }
    }

    if (current == null) return; // 값 없음

    // ✅ Case 1: 자식 없음 (leaf node)
    if (current.left == null && current.right == null) {
        if (current == root) root = null;
        else if (parent.left == current) parent.left = null;
        else parent.right = null;
    }

    // ✅ Case 2: 자식 1개
    else if (current.left == null || current.right == null) {
        BinaryTreeNode<T> child = (current.left != null) ? current.left : current.right;
        if (current == root) root = child;
        else if (parent.left == current) parent.left = child;
        else parent.right = child;
    }

    // ✅ Case 3: 자식 2개
    else {
        // 오른쪽 서브트리의 최소값 찾기
        BinaryTreeNode<T> successorParent = current;
        BinaryTreeNode<T> successor = current.right;

        while (successor.left != null) {
            successorParent = successor;
            successor = successor.left;
        }

        current.data = successor.data; // 후계자 값 복사

        // 후계자 노드 삭제
        if (successorParent.left == successor) {
            successorParent.left = successor.right;
        } else {
            successorParent.right = successor.right;
        }
    }
}

전체

public class BinarySearchTree<T extends Comparable<T>> {
    // 노드 정의
    static class BinaryTreeNode<T> {
        T data;
        BinaryTreeNode<T> left, right;

        BinaryTreeNode(T data) {
            this.data = data;
        }
    }

    private BinaryTreeNode<T> root;

    // 반복 삽입
    public void insert(T value) {
        BinaryTreeNode<T> newNode = new BinaryTreeNode<>(value);

        if (root == null) {
            root = newNode;
            return;
        }

        BinaryTreeNode<T> current = root;
        BinaryTreeNode<T> parent = null;

        while (current != null) {
            parent = current;
            int cmp = value.compareTo(current.data);
            if (cmp < 0) {
                current = current.left;
            } else if (cmp > 0) {
                current = current.right;
            } else {
                return; // 중복은 무시
            }
        }

        if (value.compareTo(parent.data) < 0) parent.left = newNode;
        else parent.right = newNode;
    }

    // 반복 탐색
    public boolean search(T value) {
        BinaryTreeNode<T> current = root;
        while (current != null) {
            int cmp = value.compareTo(current.data);
            if (cmp == 0) return true;
            else if (cmp < 0) current = current.left;
            else current = current.right;
        }
        return false;
    }

    // 반복 삭제
    public void delete(T value) {
        BinaryTreeNode<T> current = root;
        BinaryTreeNode<T> parent = null;

        // 삭제할 노드 탐색
        while (current != null && !current.data.equals(value)) {
            parent = current;
            if (value.compareTo(current.data) < 0) current = current.left;
            else current = current.right;
        }

        if (current == null) return; // 찾지 못함

        // case 1: 자식 없음
        if (current.left == null && current.right == null) {
            if (current == root) root = null;
            else if (parent.left == current) parent.left = null;
            else parent.right = null;
        }

        // case 2: 자식 1개
        else if (current.left == null || current.right == null) {
            BinaryTreeNode<T> child = (current.left != null) ? current.left : current.right;
            if (current == root) root = child;
            else if (parent.left == current) parent.left = child;
            else parent.right = child;
        }

        // case 3: 자식 2개
        else {
            BinaryTreeNode<T> successorParent = current;
            BinaryTreeNode<T> successor = current.right;

            // 오른쪽 서브트리에서 가장 작은 노드 찾기
            while (successor.left != null) {
                successorParent = successor;
                successor = successor.left;
            }

            // 후계자 값 복사
            current.data = successor.data;

            // 후계자 제거
            if (successorParent.left == successor) {
                successorParent.left = successor.right;
            } else {
                successorParent.right = successor.right;
            }
        }
    }

    // 중위 순회 출력
    public void printInOrder() {
        System.out.print("In-order: ");
        inOrder(root);
        System.out.println();
    }

    private void inOrder(BinaryTreeNode<T> node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }
}

기본 시간복잡도

연산	평균 시간복잡도	최악 시간복잡도
search	O(log n)	O(n)
insert	O(log n)	O(n)
delete	O(log n)	O(n)

• n: 노드 수
• log n: 트리가 균형일 때의 높이 (예: 완전/포화 이진 트리)
• n: 트리가 한쪽으로 편향되어 있을 때의 높이
• 편향 트리 문제를 해결하기 위해 AVL Tree, Rde-Black Tree, B-Tree 등을 사용
  • AVL Tree
  • Red-Black Tree