Tree

---

• Tree는 계층적 구조를 표현하는 데 사용되는 자료구조입니다.

• 루트 노드root node와 그 하위에 여러 개의 자식 노드child node를 가질 수 있습니다.

• 각 노드는 데이터와 그 노드와 연결된 다른 노드들의 참조를 가지고 있습니다.

---

Tree의 구성

---

• 루트노드 root node : 가장 상위에 있는 노드로, 다른 모든 노드들의 조상이 됩니다.

• 자식노드 child node : 루트 노드를 제외한 모든 노드는 부모 노드에 의해 생성되는 자식 노드를 가질 수 있습니다.

• 부모노드 parent node : 자식 노드를 생성한 노드를 부모 노드라고 합니다.

• 형제노드 sibling node : 같은 부모 노드를 가진 자식 노드를 형제 노드라고 합니다.

• 깊이 depth : 루트 노드에서 어떤 노드까지의 경로의 길이를 깊이(depth)라고 합니다.

• 레벨 level : 루트 노드부터 어떤 노드까지의 깊이+1을 레벨(level)이라고 합니다.

---

Tree의 종류

---

• 이진 트리Binary Tree : 자식 노드가 최대 2개인 트리를 이진 트리라고 합니다.

• 완전 이진 트리Complete Binary Tree : 마지막 레벨을 제외한 모든 노드가 최대 2개의 자식 노드를 가지고, 마지막 레벨의 모든 노드가 왼쪽에서부터 채워져있는 이진 트리를 완전 이진 트리라고 합니다.

• 균형 트리Balanced Tree : 트리의 모든 노드들의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1 이하인 트리를 균형 트리라고 합니다.

• 이진 탐색 트리Binary Search Tree : 왼쪽 서브 트리에는 부모 노드보다 작은 값의 노드들을, 오른쪽 서브 트리에는 부모 노드보다 큰 값의 노드들을 저장하는 이진 트리를 이진 탐색 트리라고 합니다.

---

Tree의 사용 예시

---

• 파일 시스템 : 파일 시스템은 Tree 구조로 되어있으며, 루트 디렉토리에서 시작하여 하위 디렉토리들이 Tree의 자식 노드로 표현됩니다.

• 계층적 데이터 : 계층적 데이터를 저장하는 데 매우 효과적입니다. 예를 들어, 조직도는 부서와 부서 내 직원들의 Tree로 표현됩니다.

• 네트워크 토폴로지 : 네트워크 토폴로지는 컴퓨터나 장치들의 연결 상태를 Tree로 표현합니다.

---

Tree에서 사용되는 알고리즘

---

• 전위 순회Preorder Traversal : 루트 노드를 먼저 방문한 후, 왼쪽 서브 트리를 전위 순회하고, 오른쪽 서브 트리를 전위 순회하는 방식입니다.

• 중위 순회Inorder Traversal : 왼쪽 서브 트리를 중위 순회한 후, 루트 노드를 방문하고, 오른쪽 서브 트리를 중위 순회하는 방식입니다.

• 후위 순회Postorder Traversal : 왼쪽 서브 트리를 후위 순회한 후, 오른쪽 서브 트리를 후위 순회하고, 마지막으로 루트 노드를 방문하는 방식입니다.

• 레벨 순회Level Order Traversal : Tree의 레벨별로 노드를 방문하는 방식입니다. 루트 노드부터 시작하여 각 레벨의 노드를 왼쪽에서 오른쪽으로 방문합니다.

---

Tree의 구현

---

• 포인터를 이용한 구현 : Tree는 포인터를 이용하여 구현하는 것이 가장 일반적입니다. 각 노드는 자신의 부모 노드와 자식 노드들을 가리키는 포인터를 갖고 있습니다.

• 배열을 이용한 구현 : Tree의 레벨별 순서대로 노드를 배열에 저장하는 방식입니다. 부모 노드의 인덱스와 자식 노드들의 인덱스를 계산하여 배열 상에서 연결 관계를 유지합니다.

• 포인터를 이용한 이진탐색트리 구현

class Node {
    int key;
    Node left;
    Node right;

    public Node(int key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    Node root;

    public BinarySearchTree() {
        this.root = null;
    }

    public void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) { // 만약 루트가 null인 경우 새 노드를 만들어서 리턴합니다.
            root = new Node(key);
            return root;
        }
        if (key < root.key) // 만약 새로 삽입할 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동합니다.
            root.left = insertRec(root.left, key);
        else if (key > root.key) // 만약 새로 삽입할 값이 현재 노드의 값보다 크면 오른쪽 서브트리로 이동합니다.
            root.right = insertRec(root.right, key);
        return root;
    }

    public boolean search(int key) {
        Node result = searchRec(root, key); // 루트부터 검색을 시작합니다.
        return result != null;
    }

    Node searchRec(Node root, int key) {
        if (root == null || root.key == key) // 만약 루트가 null이거나 찾고자 하는 값과 루트의 값이 일치하면 해당 노드를 리턴합니다.
            return root;
        if (root.key > key) // 만약 찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동합니다.
            return searchRec(root.left, key);
        return searchRec(root.right, key); // 만약 찾고자 하는 값이 현재 노드의 값보다 크면 오른쪽 서브트리로 이동합니다.
    }
}

• 구현한 코드 Test

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

    // 노드 삽입
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);

    // 노드 검색
    if (tree.search(60))
        System.out.println("Found 60");
    else
        System.out.println("Not found 60");
}

---

Tree에서 주로 사용되는 연산

---

• 삽입 : 새로운 노드를 Tree에 추가합니다.

• 삭제 : 특정 노드를 Tree에서 삭제합니다.

• 검색 : 특정 값을 갖는 노드를 Tree에서 검색합니다.

• 수정 : 특정 노드의 값을 수정합니다.

• 이러한 연산들은 Tree의 종류나 상황에 따라 다르게 구현될 수 있습니다.

---

결론

---

Tree는 계층적인 구조를 표현하기 위한 자료구조로, 많은 문제를 해결하기 위해 사용됩니다. 이진 트리, 완전 이진 트리, 균형 트리, 이진 탐색 트리 등의 종류가 있으며, 이들 각각의 특징과 사용되는 상황에 대해 이해하는 것이 중요합니다. 또한, Tree에서 사용되는 알고리즘들을 이해하고 활용하는 것도 중요합니다.

Tree는 다양한 분야에서 사용되고 있으며, 컴퓨터 과학 분야에서 자료구조를 공부하는 데 있어서 가장 기본적이면서 중요한 개념 중 하나입니다. 따라서, Tree에 대한 이해는 프로그래밍 기초를 다지는 데 매우 중요합니다.

그러나 Tree는 자료구조 중에서도 복잡한 편에 속하므로, 초기 학습 과정에서는 이해하기 어려울 수 있습니다. 이 때는 개념을 이해하는 데 충분한 시간을 투자하고, 문제를 푸는 과정에서 많이 연습하면서 익숙해지는 것이 좋습니다.

또한, Tree는 연결 리스트나 배열과는 다른 특성을 가지고 있기 때문에, Tree의 구현과 연산들을 구현하는 것도 중요합니다. 이를 통해 Tree가 어떻게 작동하는지를 더욱 명확하게 이해할 수 있습니다.

---