트리(Tree) & 이진탐색트리(BST) & 힙(Heap)

트리

트리(Tree)란 그래프(Graph)의 일종으로, 여러 노드가 한노드를 가리킬 수 없는 구조이다.

즉, 회로(Cycle)가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

데이터를 순차적으로 저장하지 않으므로 비선형 자료구조다.

연결된 무방향 그래프 구조이다.

 

용어

용어가 많아 시간이 지나면 헷갈릴 수 있다.

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node, terminal node, external node): 자식이 없는 노드, ‘외부 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부 노드(internal node, non-terminal node, branch node): 단말 노드가 아닌 노드, '가지 노드' 또는 '비 단말 노드'라고도 부른다.
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
  
  

트리는 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어져있다.

그림 상 데이터 1을 가진 노드가 루트(Root) 노드다.

모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부른다.

컴퓨터에서 사용되는 트리 자료구조는 대부분 이진 트리(Binary Tree) 형태이다.

트리 순회 방식(Tree Traversal)

트리 순회 방식은 총 4가지가 있다. 이 역시 이진 트리에서 순회하는 방식이다.

1. 전위 순회(Preorder) : 각 루트(Root)를 순차적으로 먼저 방문. (부모 → 왼쪽 → 오른쪽)

1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

2. 중위 순회(Inorder) : 왼쪽 하위 트리 방문 후 루트(Root)를 방문. (왼쪽 → 부모 → 오른쪽)

8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

3. 후위순회(Postorder) : 왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문. (왼쪽 → 오른쪽 → 부모)

8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

4. 레벨순회(Levelorder) : 루트(Root)부터 계층 별로 방문.

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

---

이진탐색트리(BST; Binary Search Tree)

이진탐색트리(BST)는 데이터 탐색에 소요되는 시간복잡도가 O(log N)인 트리(Tree)와 삽입/삭제의 시간복잡도가 O(1)인 연결 리스트(LinkedList)의 장점을 합하여 만든 것이다.

단, 편향된 트리의 경우 시간 복잡도가 O(N)으로 증가하는데, 이를 방지하기 위해 자가 균형 이진 트리(Self-balancing BST)를 사용하여 구현한다.

(자세한 것은 추후 기본적인 자료구조를 다 다루면 포스팅하겠습니다.)

 

특징

• 각 노드의 자식이 2개 이하 (이진 트리)
• 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼
• 중복된 노드가 없어야 함
• 중위 순회 방식을 통해 정렬된 순서로 읽을 수 있음

중복이 없어야 하는 이유는 검색이 주 목적이기 때문에, 중복이 많은 경우 트리를 사용하여 검색 속도를 느리게 할 필요가 없기 때문이다. (이 경우 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적이다.)

 

삭제 연산의 3가지 경우

1. 자식이 없는 leaf 노드일 때 : 그냥 삭제

2. 자식이 1개인 노드일 때 : 지워진 노드 위치에 자식 노드 올리기

3. 자식이 2개인 노드일 때 : 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기

BST 소스코드 : BinarySearchTree.java

---

힙(Heap)

힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로 반정렬 상태를 가지며 중복값을 허용하는 비선형 자료구조이다.

반정렬 상태인 이유는 전체 트리에서 정렬되는 것이 아니라, 서브트리를 기준으로 정렬이 일어나기 때문이다.

힙은 우선순위 큐(Priority Queue)를 위해 만들어진 자료구조인데, 우선순위 큐는 큐(Queue)에 우선순위 개념을 도입한 자료구조이다.

시뮬레이션 시스템이나 작업 스케줄링, 수치해석 계산을 할때 주로 사용한다.

탐색의 시간 복잡도는 BST와 같이 O(log N)이나, 삽입/삭제는 정렬 연산이 추가로 발생되므로 O(log N)이다.

힙 종류

최대 힙(Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

최소 힙(Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

힙의 삽입

1.힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입

2.새로운 노드를 부모 노드들과 교환

void insert_max_heap(int x) {
    // 힙 크기를 하나 증가하고, 마지막 노드에 x를 넣음   
    maxHeap[++heapSize] = x; 

    for (int i = heapSize; i > 1; i /= 2) {
        // 마지막 노드가 자신의 부모 노드보다 크면 swap
        if (maxHeap[i / 2] < maxHeap[i]) {
            swap(i / 2, i);
        } else {
            break;
        }
    }
}

 

힙의 삭제

1.최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제됨 (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)

2.삭제된 루트 노드에는 힙의 마지막 노드를 가져옴

3.힙을 재구성

int delete_max_heap() {
    if(heapSize == 0) // 배열이 비어있으면 리턴
        return 0;
    
    int item = maxHeap[1]; // 루트 노드의 값을 저장
    maxHeap[1] = maxHeap[heapSize]; // 마지막 노드 값을 루트로 이동
    maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드 0 초기화
    
    for(int i = 1; i * 2 <= heapSize;) {
        
        // 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 끝
        if(maxHeap[i] > maxHeap[i * 2] && maxHeap[i] > maxHeap[i * 2 + 1]) {
            break;
        }
        
        // 왼쪽 노드가 더 큰 경우, swap
        else if (maxHeap[i * 2] > maxHeap[i * 2 + 1]) {
            swap(i, i * 2);
            i = i * 2;
        }
        
        // 오른쪽 노드가 더 큰 경우
        else {
            swap(i, i * 2 + 1);
            i = i * 2 + 1;
        }
    }
    
    return item;
    
}

PriorityQueue.java

Java의 우선순위 큐는 Comparator를 통해 결정되기 때문에 단순한 타입뿐만 아니라 복잡한 타입도 우선순위를 결정해 반정렬할 수 있다.

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    
    transient Object[] queue;
    
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size; //실제 요소 개수
        if (i >= queue.length) //개수가 queue 사이즈 보다 같거나 클때 큐 사이즈 증가
            grow(i + 1);
        siftUp(i, e); //등록된 Comparator 기준으로 우선순위를 결정해 부모 노드와 swap
        size = i + 1;
        return true;
    }
    
    public E peek() { //루트 노드에 최대값이 있기 때문에 0번째 요소 가져옴
        return (E) queue[0];
    }
    
    public E poll() { //루트 노드 제거 후 자식 노드 올리기
        final Object[] es;
        final E result;

        if ((result = (E) ((es = queue)[0])) != null) {
            modCount++;
            final int n;
            final E x = (E) es[(n = --size)];
            es[n] = null;
            if (n > 0) {
                final Comparator<? super E> cmp;
                if ((cmp = comparator) == null)
                    siftDownComparable(0, x, es, n);
                else
                    siftDownUsingComparator(0, x, es, n, cmp);
            }
        }
        return result;
    }
    
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // 기존 용량이 64보다 작으면 두배, 아니면 1.5배
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }
}

---

Ref.

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

https://yoongrammer.tistory.com/68