[자료구조/알고리즘] - 트리, 힙

janjanee·2021년 4월 7일
0

자료구조/알고리즘

목록 보기
8/10

1. 트리(tree)


데이터 사이의 계층 관계노드로 나타낸 자료구조

1-1. 트리 - 관련 용어

  • 루트

    트리의 가장 윗부분에 위치하는 노드를 루트(root)라고 한다. 하나의 트리에는 하나의 루트가 존재한다.

  • 리프

    트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라고 한다.
    가장 아랫부분의 의미는 물리적으로 가장 아래가 아닌 더 이상 뻗어나갈 수 없는 마지막 노드의 위치를 의미

  • 안쪽 노드

    루트를 포함하여 리프를 제외한 노드를 안쪽 노드라고 한다.

  • 자식

    어떤 노드로부터 가지로 연결된 아래쪽 노드를 자식(child)이라고 한다.

    노드는 자식을 여러개 가질 수 있다. 예를 들어 X는 2개의 자식, Y는 3개의 자식을 가지고 있다.

  • 부모

    어떤 노드에서 가지로 연결된 위쪽 노드를 부모(parent)라고 한다.

    노드는 1개의 부모를 가진다. 예를 들어 Y의 부모는 X이다.

  • 형제

    같은 부모를 가지는 노드를 형제(sibling)라고 한다.

  • 조상

    어떤 노드에서 가지로 연결된 위쪽 노드를 모두를 조상(ancestor)이라고 한다.

  • 자손

    어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손(desendant)이라고 한다.

  • 레벨

    루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨(level)이라고 한다.

    루트의 레벨은 0이고 루트로부터 가지가 하나씩 아래로 뻗어나갈 때 마다 레벨이 1씩 증가한다.

  • 차수

    노드가 갖는 자식의 수를 차수(degree)라고 한다.

    예를 들어 X의 차수는 2, Y의 차수는 3이다. 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 한다.

    예제 트리는 모든 노드의자식이 3개 이하이므로 3진 트리이다.

  • 높이

    루트로부터 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)를 높이(height)라고 한다.

    예제 트리의 높이는 3이다.

  • 서브 트리

    트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브 트리(subtree)라고한다.

  • 널 트리

    노드, 가지가 없는 트리를 널 트리(null tree)라고 한다.

  • 순서 트리와 무순서 트리

    형제 노드의 순서가 있는지 없는지에 따라 트리를 두 종류로 분류한다.

    형제 노드의 순서를 따지면 → 순서 트리(ordered tree)

    형제 노드의 순서를 따지지 않으면 → 무순서 트리(unordered tree)

1-2. 순서 트리 탐색

순서 트리의 노드를 스캔하는 방법은 두 가지가 존재한다. 이진트리를 예로 살펴보자.

  • 낮은 레벨에서 시작해 왼쪽 → 오른쪽 방향으로 검색한다.
  • 한 레벨에서의 검색이 끝나면 다음 레벨로 내려간다.
  • 검색 순서는 다음과 같다.

A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L

  • 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법
  • 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우 부모에게 돌아간다.
  • 그 다음 다시 자식 노드로 내려간다.

깊이 우선 탐색의 경우 '언제 노드를 방문할지' 는 다음과 같이 세 종류로 구분한다.

전위 순회(Preorder)

  • 노드 방문 → 왼쪽 자식 → 오른쪽 자식

A -> B -> C -> H -> E-> I -> J -> C -> F -> K -> L -> G

중위 순회(Inorder)

  • 왼쪽 자식 → 노드 방문 → 오른쪽 자식

H -> D -> B -> I -> E -> J -> A -> K -> F -> L -> C -> G

후위 순회(Postorder)

  • 왼쪽 자식 → 오른쪽 자식 → (돌아와) 노드 방문

H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A

1-3. 이진트리와 이진검색트리

이진트리

노드가 왼쪽 자식오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다.

  • 각 노드의 자식은 2개 이하여야 한다.

완전이진트리

루트부터 노드가 채워져 있으면서 같은 레벨에서 왼쪽 → 오른쪽 순으로 노드가 채워져 있는
이진트리를 완전이진트리(complete binary tree)라고 한다.

  • 마지막 레벨을 제외한 레벨은 노드를 가득 채운다.
  • 마지막 레벨은 왼쪽 → 오른쪽 방향으로 노드를 채운다. 반드시 끝까지 채울 필요는 없다.
  • 완전이진트리에서 너비 우선 탐색을 하며 각 노드에 0, 1, 2 ... 값을 주면 배열에 저장하는 인덱스와
    일대일로 대응한다.
  • n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n 이다.

이진검색트리(binary search tree)

이진검색트리는 이진트리가 다음 조건을 만족하면 된다.

  1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
  2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
  3. 같은 키 값을 갖는 노드는 없다.

이진검색트리를 구현한 예시이다.

  • 노드 5를 기준으로 보면 왼쪽 서브 트리 노드(4, 1)은 모두 5보다 작다.
  • 오른쪽 서브 트리 노드(7, 6, 9)는 모두 5보다 크다.

이때 이진검색트리를 중위순회(Inorder)하면 다음과 같이 키 값의 오름차순으로 노드를 얻을 수 있다.

1 -> 4 -> 5 -> 6 -> 7 -> 9 -> 11 -> 12 -> 13 -> 14 -> 15 -> 18

1-4. 이진검색트리 구현 - Java 코드

public class BinTree <K, V> {
    private Node<K, V> root;
    private Comparator<? super K> comparator = null;

    public BinTree() {
        root = null;
    }

    public BinTree(Comparator<? super K> c) {
        this();
        comparator = c;
    }

    /** 두 키 값을 비교 */
    private int comp(K key1, K key2) {
        return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2)
                                : comparator.compare(key1, key2);
    }

    /** 키에 의한 검색 */
    public V search(K key) {
        Node<K, V> p = root;

        while (true) {
            if (p == null)
                return null;
            int cond = comp(key, p.getKey());
            if (cond == 0)
                return p.getValue();
            else if (cond < 0)
                p = p.getLeft();
            else
                p = p.getRight();
        }
    }

    /** node를 루트로 하는 서브 트리에 노드 <K, V>를 삽입 */
    private void addNode(Node<K, V> node, K key, V value) {
        int cond = comp(key, node.getKey());
        if (cond == 0)
            return;     //  key가 이진검색트리에 이미 있음
        else if(cond < 0) {
            if (node.getLeft() == null)
                node.setLeft(new Node<>(key, value, null, null));
            else
                addNode(node.getLeft(), key, value);     //  왼쪽 서브트리에 주목
        } else {
            if (node.getRight() == null)
                node.setRight(new Node<>(key, value, null, null));
            else
            addNode(node.getRight(), key, value);        //  오른쪽 서브트리에 주목
        }
    }

    public void add(K key, V value) {
        if (root == null)
            root = new Node<>(key, value, null, null);
        else
            addNode(root, key, value);
    }

    /** 키 값이 key인 노드를 삭제 */
    public boolean remove(K key) {
        Node<K, V> p = root;        //  스캔 중인 노드
        Node<K, V> parent = null;   //  스캔 중인 노드의 부모 노드
        boolean isLeftChild = true; //  p는 부모의 왼쪽 자식 노드인가?

        while (true) {
            if (p == null)
                return false;
            int cond = comp(key, p.getKey());
            if (cond == 0)
                break;
            else {
                parent = p;
                if (cond < 0) {
                    isLeftChild = true;
                    p = p.getLeft();
                } else {
                    isLeftChild = false;
                    p = p.getRight();
                }
            }
        }

        if (p.getLeft() == null) {              //  p에 왼쪽 자식이 없음
            if (p == root)
                root = p.getRight();
            else if (isLeftChild)
                parent.setLeft(p.getRight());
            else
                parent.setRight(p.getRight());
        } else if (p.getRight() == null) {      //  p에 오른쪽 자식이 없음
            if (p == root)
                root = p.getLeft();
            else if (isLeftChild)
                parent.setLeft(p.getLeft());
            else
                parent.setRight(p.getLeft());
        } else {
            parent = p;
            Node<K, V> left = p.getLeft();  //  서브 트리 가운데 가장 큰 노드
            isLeftChild = true;
            while(left.getRight() != null){
                parent = left;
                left = left.getRight();
                isLeftChild = false;
            }

            p.setKey(left.getKey());
            p.setValue(left.getValue());
            if (isLeftChild)
                parent.setLeft(left.getLeft());
            else
                parent.setRight(left.getLeft());
        }

        return true;

    }

    // node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력
    private void printSubTree(Node node) {
        if (node != null) {
            printSubTree(node.getLeft());   //  왼쪽 서브 트리를 키 값의 오른차순으로 출력
            System.out.println(node.getKey() + " " + node.getValue());  //  node 출력
            printSubTree(node.getRight());  //  오른쪽 서브 트리를 키 값의 오름차순으로 출력
        }
    }

    // 모든 노드를 키 값의 오름차순으로 출력
    public void print() {
        printSubTree(root);
    }
}
public class Node<K, V> {
    private K key;
    private V value;
    private Node<K, V> left;
    private Node<K, V> right;

    public Node(K key, V value, Node<K, V> left, Node<K, V> right) {
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }

    // getter, setter
}

2. 힙 (heap)


최대값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조

2-1. 우선순위 큐

  • 우선순위의 개념을 큐에 도입한 자료구조
  • 데이터들이 우선순위를 가지며, 우선순위가 높은 데이터가 먼저 나간다.
  • 우선순위 큐의 이용 사례
    • 시뮬레이션 시스템
    • 네트워크 트래픽 제어
    • 운영체제에서의 작업 스케쥴링
  • 우선순위 큐는 배열, 연결리스트, 으로 구현이 가능하다. 이 중 힙으로 구현하는 것이 가장 효율적이다.

2-2. 힙 이란?

  • 완전이진트리의 일종이며, 우선순위 큐를 위하여 만들어진 자료구조
  • 여러 개의 값 중 최대값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조
  • 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않음
  • 힙 트리에서는 중복된 값을 허용 (이진탐색트리에서는 중복된 값을 허용하지 않음)
  • 힙에서 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트에 위치

2-3. 힙의 종류

  • 최대 힙(max heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전이진트리
    • key(부모노드) ≥ key(자식노드)
  • 최소 힙(min heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전이진트리
    • key(부모노드) ≤ key(자식노드)

2-4. 힙 연산

  • 배열을 이용하여 힙을 저장한다.
  • 부모 노드와 자식 노드의 관계
    • 부모 인덱스 = (자식 인덱스 - 1) / 2
    • 왼쪽 자식 인덱스 = (부모 인덱스 * 2) + 1
    • 오른쪽 자식 인덱스 = (부모 인덱스 * 2) + 2

힙의 삽입

  • 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 가장 마지막 노드에 이어 삽입한다.
  • 새로운 노드를 부모 노드와 비교 후, 교환해서 힙의 성질을 만족시킨다.

  1. 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 가장 마지막 노드에 이어서 삽입한다.

  1. 새로운 요소 10을 가장 마지막 위치에 삽입

  1. 10과 부모인 6을 비교, 10 > 6 이므로 자리교환이 일어난다.

  1. 10과 그 위의 부모인 8을 비교, 10 > 8 이므로 자리교환이 일어난다.

  1. 10과 그 위의 부모인 9를 비교, 10 > 9 이므로 자리교환이 일어난다.

  1. 더 이상 비교할 대상이 없으므로 종료.

힙의 삭제

  • 최대 힙에서 최대값은 루트 이므로, 루트 노드를 삭제한다.
  • 삭제된 루트 노드에 힙의 가장 마지막 노드를 가져온다.
  • 힙을 재구성한다.


1. 최대값인 루트 노드 10을 삭제.
2. 빈 자리에 가장 마지막 노드인 6을 가져온다.


3. 6과 두 자식 노드 중 더 큰 값인 9를 비교, 9 > 6 이므로 자리교환이 일어난다.

  1. 6과 두 자식 노드 중 더 큰 값인 8을 비교, 8 > 6 이므로 자리교환이 일어난다.

  1. 6보다 큰 자식 노드가 없으므로 종료한다.

2-5. 힙 구현 - Java 코드

public class Heap<T extends Comparable<T>> {

    private ArrayList<T> items;

    public Heap() {
        this.items = new ArrayList<>();
    }

    /** 데이터 삽입 */
    private void siftUp() {
        int k = items.size() - 1;
        while (k > 0) {
            int p = (k - 1) / 2;
            T item = items.get(k);
            T parent = items.get(p);
            if (item.compareTo(parent) > 0) {
                //  swap
                items.set(k, parent);
                items.set(p, item);

                // move up one level
                k = p;
            } else {
                break;
            }
        }
    }

    public void insert(T item) {
        items.add(item);
        siftUp();
    }

    /** 데이터 삭제 */
    private void siftDown() {
        int k = 0;
        int l = 1;
        while (l < items.size()) {
            int max = l, r = l + 1;
            if (r < items.size()) {
                if (items.get(r).compareTo(items.get(l)) > 0) {
                    max++;
                }
            }

            if (items.get(k).compareTo(items.get(max)) < 0) {
                // switch
                T tmp = items.get(k);
                items.set(k, items.get(max));
                items.set(max, tmp);
                k = max;
                l = 2 * k + 1;
            } else {
                break;
            }
        }
    }

    public T delete() throws NoSuchElementException {
        if (items.size() == 0)
            throw new NoSuchElementException();
        if (items.size() == 1)
            return items.remove(0);
        T hold = items.get(0);
        items.set(0, items.remove(items.size() - 1));
        siftDown();
        return hold;
    }

    public int size() {
        return items.size();
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public String toString() {
        return items.toString();
    }
}

References


profile
얍얍 개발 펀치

0개의 댓글