이진트리란?? 이진트리 데이터구조를 java로 구현하기 with 치우친 트리

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 자료 구조입니다. 트리는 계층적인 구조로, 루트(root)라고 불리는 최상위 노드에서 시작하여 그 아래로 연결된 노드들로 이루어집니다. 이진 트리는 데이터의 효율적인 탐색과 관리에 자주 사용되는 자료 구조입니다.

이진 트리의 주요 구성 요소

1. 노드(Node): 트리의 각 요소를 나타냅니다. 각 노드는 세 가지 주요 부분으로 이루어집니다:
   • 데이터: 노드가 저장하는 값
   • 왼쪽 자식: 노드의 왼쪽에 연결된 하위 노드
   • 오른쪽 자식: 노드의 오른쪽에 연결된 하위 노드
2. 루트(Root): 트리의 최상단 노드. 트리의 시작점입니다.
3. 자식(Child): 다른 노드에 의해 가리켜지는 노드. 트리의 하위 요소로, 왼쪽 자식과 오른쪽 자식으로 구분됩니다.
4. 부모(Parent): 특정 자식을 가지는 노드. 자식이 있는 노드를 가리킵니다.
5. 잎(Leaf, 리프 노드): 자식이 없는 노드. 트리의 가장 아래쪽에 위치하며, 끝 노드를 의미합니다.

이진 트리의 유형

이진 트리는 여러 가지 특성에 따라 다양한 유형으로 나눌 수 있습니다.

1. 포화 이진 트리(Full Binary Tree): 모든 노드가 자식 노드를 두 개씩 가지거나(내부 노드), 자식 노드가 전혀 없는 경우(리프 노드)로 구성된 트리입니다.
2. 완전 이진 트리(Complete Binary Tree): 트리의 모든 레벨에서 노드들이 왼쪽부터 오른쪽 순서대로 꽉 차 있는 트리입니다. 마지막 레벨을 제외하고는 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽에서부터 노드가 차례대로 채워집니다.
3. 균형 이진 트리(Balanced Binary Tree): 모든 노드에서 왼쪽과 오른쪽 하위 트리의 높이 차이가 1 이하인 트리입니다. 이진 탐색 트리에서 균형을 맞추기 위해 자주 사용됩니다.
4. 이진 탐색 트리(Binary Search Tree, BST): 이진 트리의 한 종류로, 모든 왼쪽 자식의 값은 부모의 값보다 작고, 모든 오른쪽 자식의 값은 부모의 값보다 큽니다. 이진 탐색 트리는 효율적인 탐색, 삽입, 삭제 연산이 가능하도록 설계된 트리입니다.

이진 트리의 연산

이진 트리에서 자주 사용하는 연산은 다음과 같습니다:

1. 삽입(Insertion): 새로운 노드를 트리에 추가합니다. 일반적으로 특정 규칙을 따라 새로운 노드를 적절한 위치에 삽입합니다.
2. 탐색(Search): 특정 값이 트리 안에 존재하는지 확인합니다. 이진 탐색 트리에서는 O(log n)의 시간 복잡도로 탐색이 가능합니다.
3. 삭제(Deletion): 트리에서 특정 노드를 제거합니다. 노드의 자식 여부에 따라 삭제 알고리즘이 달라집니다.
4. 순회(Traversal): 트리의 노드를 특정한 순서로 방문하는 연산입니다. 대표적인 트리 순회 방식은 다음과 같습니다:
   • 전위 순회(Preorder Traversal): 현재 노드를 먼저 방문한 후 왼쪽 자식, 오른쪽 자식 순으로 방문.
   • 중위 순회(Inorder Traversal): 왼쪽 자식을 먼저 방문한 후 현재 노드, 그 다음 오른쪽 자식을 방문.
   • 후위 순회(Postorder Traversal): 왼쪽 자식과 오른쪽 자식을 먼저 방문한 후 현재 노드를 방문.

이진 트리의 장점

• 탐색, 삽입, 삭제 연산을 효율적으로 처리할 수 있습니다.
• 특히 이진 탐색 트리는 O(log n)의 시간 복잡도를 가지기 때문에 큰 데이터 집합에서 빠르게 값을 찾거나 추가, 삭제할 수 있습니다.

이진 트리의 단점

• 이진 트리는 삽입하는 순서에 따라 한쪽으로 치우친 트리가 될 수 있으며, 이 경우 시간 복잡도가 O(n)으로 증가해 탐색, 삽입, 삭제 성능이 저하될 수 있습니다. 이를 방지하기 위해서는 균형 잡힌 이진 트리를 사용하는 것이 중요합니다.

이진 트리의 활용 예

• 이진 탐색 트리(BST): 데이터를 효율적으로 탐색하는 데 자주 사용됩니다.
• 힙(Heap): 완전 이진 트리의 일종으로, 우선순위 큐와 같은 자료 구조에 활용됩니다.
• 허프만 트리: 데이터 압축 알고리즘에서 사용하는 트리입니다.

이진 트리는 컴퓨터 과학에서 매우 중요한 자료 구조로, 다양한 알고리즘과 데이터 구조의 기반이 됩니다.

 

 

이진 트리를 자바로 구현하는 방법을 단계별로 설명하겠습니다. 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 자료 구조입니다. 기본적으로 다음과 같은 구성 요소가 필요합니다:

1. 노드 클래스: 트리의 각 노드를 정의합니다. 각 노드는 데이터를 저장하고 왼쪽과 오른쪽 자식에 대한 참조를 가집니다.
2. 트리 클래스: 트리 전체를 관리하며, 삽입, 탐색, 삭제 등의 연산을 처리합니다.

1. 노드 클래스 구현

먼저, 이진 트리의 각 노드를 나타내는 Node 클래스를 구현하겠습니다.

 

class Node {
    int data;       // 노드에 저장할 데이터
    Node left;      // 왼쪽 자식 노드
    Node right;     // 오른쪽 자식 노드

    // 생성자: 노드를 초기화
    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

 

 

2. 이진 트리 클래스 구현

이제 이진 트리 구조를 나타내는 BinaryTree 클래스를 구현합니다. 이 클래스에는 노드를 삽입하고, 중위 순회(inorder traversal)를 구현해 볼 수 있습니다.

 

class BinaryTree {
    Node root;  // 트리의 루트 노드

    // 트리 생성자: 초기에는 트리가 비어 있음
    public BinaryTree() {
        root = null;
    }

    // 새로운 데이터를 트리에 삽입
    public void insert(int data) {
        root = insertRec(root, data);
    }

    // 노드를 삽입하는 재귀 함수
    private Node insertRec(Node root, int data) {
        // 기저 사례: 비어 있는 곳에 새로운 노드 삽입
        if (root == null) {
            root = new Node(data);
            return root;
        }

        // 데이터에 따라 왼쪽 또는 오른쪽으로 재귀 호출
        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    // 중위 순회 (왼쪽 -> 현재 노드 -> 오른쪽)
    public void inorderTraversal() {
        inorderRec(root);
    }

    // 중위 순회 재귀 함수
    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }
}

 

 

3. 메인 클래스에서 테스트

이제 이진 트리를 생성하고, 데이터를 삽입하고, 순회를 하는 코드를 작성해 보겠습니다.

 

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        // 트리에 데이터 삽입
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // 중위 순회 출력 (오름차순으로 출력됨)
        System.out.println("Inorder traversal of the binary tree:");
        tree.inorderTraversal();
    }
}

 

결과

위의 코드에서 데이터를 삽입하고 중위 순회를 실행하면, 이진 탐색 트리의 특성에 따라 오름차순으로 정렬된 값이 출력됩니다.

 

Inorder traversal of the binary tree:
20 30 40 50 60 70 80

 

최악의경우가 존재한다 탐색성능이 O(logN) 이 아닌 O(N)?

 

만약 계속해서 작은 숫자를 삽입한다면, 트리가 **한쪽(왼쪽)**으로만 치우친 형태가 됩니다. 즉, 이진 트리의 왼쪽 자식에만 노드들이 추가되는 상황이 발생하게 됩니다. 예를 들어, 트리에 30, 20, 10 순으로 삽입하면 트리는 다음과 같이 됩니다:

     30
    /
   20
  /
 10

 

이렇게 트리가 한쪽으로만 치우치면 사실상 연결 리스트와 비슷해지게 되며, 이진 트리의 장점인 탐색의 효율성이 사라집니다. 이진 트리에서 탐색은 일반적으로 O(log n) 시간 복잡도를 갖지만, 트리가 한쪽으로만 치우치면 최악의 경우 O(n)이 되어 탐색 성능이 떨어지게 됩니다.

해결 방법: 균형 이진 트리 (예: AVL 트리, 레드-블랙 트리)

이 문제를 해결하기 위해 트리를 자동으로 균형 잡는 알고리즘을 사용하는 것이 일반적입니다. 대표적인 예로:

1. AVL 트리: 삽입 및 삭제 시 트리가 자동으로 균형을 맞추도록 회전 연산을 사용하여 트리의 높이를 균형 있게 유지합니다.
2. 레드-블랙 트리: 삽입 및 삭제 시 노드의 색깔과 회전을 이용하여 트리의 균형을 유지합니다.

단순한 이진 트리의 경우 해결책

만약 균형 잡힌 트리로 구현할 필요가 없다면, 현재 이진 트리에서는 삽입되는 데이터의 순서에 따라 치우침 현상이 발생하는 것을 감수할 수 있습니다. 하지만 데이터가 무작위로 들어오는 상황에서는 평균적으로 트리가 균형 잡힌 형태가 될 가능성이 높습니다.

균형 잡힌 트리를 사용하려면, AVL 트리나 레드-블랙 트리와 같은 자료 구조를 구현하거나 Java에서 제공하는 TreeSet(내부적으로 레드-블랙 트리로 구현됨)을 사용하는 방법도 있습니다.

참고: AVL 트리 개념 설명

AVL 트리는 트리의 높이 차이를 1 이하로 유지하기 위해 삽입과 삭제 시 노드 회전을 통해 트리의 균형을 맞추는 이진 탐색 트리입니다. 이 트리에서는 다음 규칙을 지킵니다:

• 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 1 이하로 유지합니다.
• 트리의 불균형이 감지되면 회전 연산을 통해 균형을 맞춥니다.

AVL 트리와 같은 균형 트리는 데이터가 삽입될 때 트리의 구조를 유지하기 때문에 탐색, 삽입, 삭제 모두 O(log n)의 시간 복잡도를 보장합니다.

이렇게 하면 이진 트리가 왼쪽 또는 오른쪽으로 한쪽에만 치우치는 문제를 방지할 수 있습니다