[자료구조] 자바 트리 소개 및 구현

https://www.youtube.com/playlist?list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk

Data Structures

 

Rob Edwards 교수님의 CS310 Data Structures in Java를 공부하고 정리한 내용입니다.

 

부스트 코스 자바로 구현하고 배우는 자료구조에서도 학습할 수 있습니다.

 

트리를 순회하는 방법을 알아보고, add, remove, contain 등 트리의 메서드를 구현합니다. 특히 remove는 리프 노드인지, 자식노드를 가지고 있는지에 따라 다양한 경우가 있습니다.

---

트리 순회 및 표현

순회는 노드에 숫자를 매기는 방법이다. 전위 순회, 중위 순회, 후위 순회가 있다.

 

전위 순회

1. 루트 노드

2. 왼쪽 자식 노드

3. 오른쪽 자식 노드

 

전위 순회

중위 순회

1. 왼쪽 자식 노드

2. 루트 노드

3. 오른쪽 자식 노드

 

중위 순회

후위 순회

1. 왼쪽 자식 노드

2. 오른쪽 자식 노드

3. 루트 노드

 

후위 순회

수식을 트리 형태로 표현

 

트리 형태 식

 

중위 표기식 : ((22/11) + 3)*(6+5))-50

후위 표기식 : 22 11 / 3 + 6 5 * 50 -

 

사람이 사용하는 중위 표기식은 괄호와 연산자 우선순위를 고려해야하지만, 후위표기식은 수식을 왼쪽부터 차례대로 계산할 수 있기 때문에, 컴퓨터가 연산하기에 더 적절하다.

 

관련 문제 - https://www.acmicpc.net/problem/1918

---

노드 클래스

힙에 데이터를 추가할 때 규칙은 최대힙은 부모 노드가 자식 노드보다 커야하는 것이고 최소 힙은 부모 노드가 자식 노드보다 작아야한다는 것이다.

트리의 규칙은 힙과는 다른데, 작은 데이터는 왼쪽 자식 노드로, 큰 데이터는 오른쪽 자식 노드에 추가해야 한다.

 

linked List는 next pointer와 data를 가지고 있는데, tree도 비슷한 컨셉으로 left, right라는 자식 노드 pointer와 data를 갖는다.

 

class Node<E> {
    E data;
    Node<E> left, right;
    public Node(E obj) {
        this.data = obj;
        left = right = null;
    }
}

---

Add 메서드 구현

재귀 함수를 사용해서 구현하는데, 새로 추가하는 노드가 왼쪽 노드인지, 오른쪽 노드인지, 어느 level에 추가할지 모르기 때문에 반복해서 자기 자신을 호출한다.

 

1. 루트에서 시작한다.

2. 트리의 규칙을 따라 내려간다.

3. null인 부분에 노드를 추가한다.

 

add 메서드 구현

public void add(E obj, Node<E> node) {
    if (((Comparable<E>) obj).compareTo(node.data) > 0) {
        //go to the right
        if (node.right == null) {
            node.right = new Node<E>(obj);
            return;
        }
        return add(obj, node.right);
    }
    //go to the left
    if (node.left == null) {
        node.left = new Node<E>(obj);
        return;
    }
    return add(obj,node.left);
}

public void add(E obj) {
    if (root == null) 
        root = new Node<E>(obj);
    else
        add(obj, root);
    currentSize++
}

---

Contains 메서드 구현

add와 마찬가지로, 재귀로 구현한다. 

public boolean contains(E obj) {
    return contains(obj, root);
}
private boolean contains(E obj, Node<E> node) {
    if (node == null)
        return false;
    if (((Comparable<E>)obj).compareTo(node.data) == 0)
        return true;
    if (((Comparable<E>)obj).compareTo(node.data) > 0)
        return contains(obj, node.right);
    return contains(obj, node.left);
}

---

Remove 메서드 구현

1. 하나의 리프 노드를 제거

부모 포인터를 null을 가리키게 한다.

 

 

2.  하나의 자식 노드를 갖는 노드를 제거

부모 포인터를 자식노드를 가리키게 한다.

 

3.  자식 노드가 두 개인 노드를 제거

inorder successor : 제거하고자 하는 노드보다 작은 노드 중 가장 큰 노드

inorder predessor : 제거하고자 하는 노드보다 큰 노드 중 가장 작은 노드

 

 

inorder successor 혹은 inorder predessor와 swap한 뒤 1번 remove 호출